akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=1e9+7;
int h,w,a,b,fac[N],ifac[N],ans=0,up;
inline int C(int n,int m){return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
	scanf("%d%d%d%d",&h,&w,&a,&b),up=max(w,h),fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	for(ri i=2;i<=up<<1;++i)fac[i]=(ll)fac[i-1]*i%mod,ifac[i]=(ll)ifac[mod%i]*(mod-mod/i)%mod;
	for(ri i=2;i<=up<<1;++i)ifac[i]=(ll)ifac[i]*ifac[i-1]%mod;
	for(ri i=1;i<=h-a;++i)(ans+=(ll)C(b+i-2,b-1)*C(h+w-b-i-1,w-b-1)%mod)%=mod;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

const int inf = 1e17 + 7;
const int MOD = 1e7 + 9;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n,k;
	cin>>n>>k;
	int h[n];
	for(int i=0;i<n;i++) cin>>h[i];
	vector<int> dp(n);
	fill(dp.begin(),dp.end(),inf);
	dp[0] = 0;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=i+k && j<n;j++)
			dp[j] = min(dp[j],dp[i] + abs(h[i]-h[j]));
	}
	cout<<dp[n-1]<<endl;
	return 0;
}



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

int main(){
  int N;
  cin >> N;
  
  vector<int> d(N);
  for(int i=0; i<N; ++i){
    cin >> d.at(i);
  }
  int64_t vit=0;
  for(int i=0; i<N-1; ++i){
    for(int j=i+1; j<N; ++j){
      vit += d.at(i)*d.at(j);
    }
  }
  cout << vit << endl;  
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n;
	while(cin >> n , n){
		int dp[100000] = {0};
		int pos = 0;
		rep(i,n){
			int c; cin >> c;
			if((i+1)%2 == 1){ //odd
				if(dp[pos] == 0){
					if(c)dp[pos]++; else dp[pos]--;
					continue;
				}
				if(c == 1 && dp[pos] > 0){
					dp[pos]++;
				}else if(c == 0 && dp[pos] < 0){
					dp[pos]--;
				}else{
					pos++;
					if(c == 1)dp[pos]++;
					else dp[pos]--;
				}
			}else{
				if(c == 1 && dp[pos] > 0){
					dp[pos]++;
				}else if(c == 0 && dp[pos] < 0){
					dp[pos]--;
				}else{
					if(pos == 0){
						dp[pos] *= -1;
					}else{
						dp[pos-1] -= dp[pos];
						dp[pos] = 0;
						pos--;
					}
					if(c == 1) dp[pos]++;
					else dp[pos]--;
				}
			}
		}
		int sum = 0;
		rep(i,100000){
			if(dp[i] < 0)sum += dp[i];
		}
		cout << -sum << endl;
	}
}

Measured memory_bytes: 0
n,k=map(int,input().split())
p=list(map(int,input().split()))
p=[(i+1)/2 for i in p]
ans=0
cur_sum=0
for i in range(0,k):
  cur_sum+=p[i]
ans=cur_sum
for i in range(k,n):
  cur_sum+=p[i]
  cur_sum-=p[i-k]
  ans=max(ans,cur_sum)
print(ans)


Measured memory_bytes: 25060
# -*- coding: utf-8 -*-
import sys
from fractions import gcd
from string import ascii_uppercase as ABC
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

from itertools import permutations
N, M = inpl()
C = 0
P = 0
ac = [False]*N
pe = [0]*N

for _ in range(M):
    p, s = input().split()
    p = int(p) - 1
    if s == "AC":
        ac[p] = True
    else:
        if ac[p] == False:
            pe[p] += 1
C = sum(ac)
P = sum([ac[i]*pe[i] for i in range(N)])
print(C, P)

Measured memory_bytes: 77524
import sys

temp = []
largest = 1

for line in sys.stdin:
    a,b = [int(x) for x in line.split()]
    if a > b:
        x,y = a,b
    else:
        x,y = b,a
    while y:
        x,y = y,x%y
    smallest = x * (a/x) * (b/x)
    print('%d %d' % (x, smallest))

Measured memory_bytes: 7704
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;
const int INF = 1001001001;

struct wari {
    int x;
    int y;
    int c;
    wari(int x=0, int y=0, int c=0): x(x), y(y), c(c) {}
    int goukei(){
        return x+y-c;
    }
};

int main(){
    int a, b, m;
    cin >> a >> b >> m;
    int ans = INF;
    vector<int> ap(a);
    vector<int> bp(b);
    vector<wari> wp(m);
    int wari_min = INF;
    rep(i, a) {
        cin >> ap[i];
    }
    rep(i, b) {
        cin >> bp[i];
    }
    rep(i, m) {
        int x, y, c;
        cin >> x >> y >> c;
        x--;
        y--;
        wp[i] = wari(ap[x], bp[y], c);
        int temp = wp[i].goukei();
        if (temp<wari_min) {
            wari_min = temp;
        }
    }
    sort(ap.begin(), ap.end());
    sort(bp.begin(), bp.end());
    if (ap[0]+bp[0]<wari_min) {
        wari_min = ap[0] + bp[0];
    }
    
    
    
    cout << wari_min << endl;
    return 0;
}


Measured memory_bytes: 2304
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

/*
a b c
 */
int a[3];

int main(){
  REP(i,3)
    cin>>a[i];

  sort(a,a+3);
  if(a[0]+a[1]==a[2])
    cout <<"Yes\n";
  else
    cout<<"No\n";

  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(long long &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(long long x){
  char f[20];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int main(){
  long long N, res;
  rd(N);
  res = (N-1) * N / 2;
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190830-1

// --- original code ---
// {
//   ll N, res;
//   rd(N);
//   res = (N-1) * N / 2;
//   wt(res);
// }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
#define fil(x) memset(x, 0, sizeof(x))
#define fillb(x) memset(x,false,sizeof(x))
#define fillm(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define pll pair<int, int>
#define pf printf
#define sf scanf
#define all(x) x.begin(),x.end()
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<n;i++)
#define fof(i,a,b) for(int i=a;i<=b;i++)
#define off(i,a,b) for(int i=a;i>=b;i--)
#define of(i,n) for(int i=n-1;i>=0;i--)
#define stl(i,x) for(auto i=x.begin(); i!=x.end();i++)
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
#define nl endl

typedef unsigned long long lll;
typedef long long ll;
int knigtx8[] = {2, 2, -2, -2, 1, 1, -1, -1}; ///knight move in chess
int knigty8[] = {1, -1, 1, -1, 2, -2, 2, -2}; ///knight move in chess
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}; ///for 8 directions
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1}; ///for 8 directions
int dx4[] = {0, 0, 1, -1}; ///for 4 directions
int dy4[] = {1, -1, 0, 0}; ///for 4 directions
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}
ll pw(ll a, ll b)
{
    ll ans = 1;
    for(ll i = 1; i <= b; ++i)
        ans = (ans * a);
    return ans;
}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

int main()
{
    IOS;
    int n;
    cin>>n;
    if(n>=400 and n<=599)cout<<8<<endl;
    else if(n>=600 and n<=799)cout<<7<<endl;
    else if(n>=800 and n<=999)cout<<6<<endl;
    else if(n>=1000 and n<=1199)cout<<5<<endl;
    else if(n>=1200 and n<=1399)cout<<4<<endl;
    else if(n>=1400 and n<=1599)cout<<3<<endl;
    else if(n>=1600 and n<=1799)cout<<2<<endl;
    else if(n>=1800 and n<=1999)cout<<1<<endl;
    return 0;
}

///Alhamdulillah


Measured memory_bytes: 3644
import heapq

x,y,z,k=map(int,input().split())

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q=[(-1*(A[0]+B[0]+C[0]),0,0,0)]

heapq.heapify(q)

used=[[0,0,0]]

a=0
b=0
c=0
cnt=0
while cnt<k:
    p,a,b,c=heapq.heappop(q)
    cnt+=1
    print(p*-1)
    a+=1
    if (not [a,b,c] in used) and a<x:
        heapq.heappush(q,(-A[a]-B[b]-C[c],a,b,c))
        used.append([a,b,c])
    a-=1
    b+=1
    if (not [a,b,c] in used) and b<y:
        heapq.heappush(q,(-A[a]-B[b]-C[c],a,b,c))
        used.append([a,b,c])
    b-=1
    c+=1
    if (not [a,b,c] in used) and c<z:
        heapq.heappush(q,(-A[a]-B[b]-C[c],a,b,c))
        used.append([a,b,c])

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

using namespace std;

const int N = 3'000;

double p[N];
double dp[N][N];

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

    cout << fixed << setprecision(9);

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

    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = (1 - p[i - 1]) * dp[i - 1][0];
        for (int j = 1; j <= i; ++j) {
            dp[i][j] =
                p[i - 1] * dp[i - 1][j - 1] + (1 - p[i - 1]) * dp[i - 1][j];
        }
    }

    int k = (n + 1) / 2;

    double ans = accumulate(dp[n] + k, dp[n] + n + 1, 0.0);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 68992
import java.io.File;
import java.io.IOException;
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		int D = sc.nextInt();
		int G = sc.nextInt();
		int[] p = new int[D];
		int[] sumP = new int[D];
		int min = 0;
		int ans = 0;
		
		for(int i = 0; i < D; i++){
			p[i] = sc.nextInt();
			sumP[i] = sc.nextInt() + (i + 1) * 100 * p[i];
			min += p[i];
		}
		
		int bitMax = ((1 << D) - 1);
		//System.out.printf(Integer.toBinaryString(bit));
		
		for(int bit = 0; bit <= bitMax; bit++){
			//System.out.println(Integer.toBinaryString(bit));
			int sumPoint = 0;
			int sumProblem = 0;
			int index = D;
			for(int j = 0; j < D; j++){
				if((1&(bit>>j)) == 1){
					sumPoint += sumP[j];
					sumProblem += p[j];
				}
				else index = j;
			}
			
			//System.out.println(Integer.toBinaryString(bit) + " " + sumPoint + " " + sumProblem + " " + index);
			
			if(index != D){
				for(int j = 0; j < p[index]; j++){
					if(sumPoint + (index + 1) * 100 * j >= G && sumProblem + j < min){
						min = sumProblem + j;
						ans = sumPoint + (index + 1) * 100 * j;
						break;
					}
				}
			}else{
				if(sumPoint >= G && sumProblem < min){
					min = sumProblem;
				}
			}
		}
		
		System.out.println(min);
	}
}

Measured memory_bytes: 23124
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String A = sc.next();
    String B = sc.next();
    String ans = "GREATER";
    if(A.length() < B.length()) {
      ans = "LESS";
    } else if(A.length() == B.length()) {
      if(A.compareTo(B) < 0) {
        ans = "LESS";
      } else if(A.compareTo(B) == 0) {
        ans = "EQUAL";
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <stdio.h>

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

  scanf("%d%d",&a,&b);

  if(a < b){
    c = a;
    a = b;
    b = c;
  }

  while(b>0){
    c = b;
    b = a%b;
    a = c;
  }

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

  return 0;
}

Measured memory_bytes: 592
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def check(a, b):
    global uf
    global ans_list
    if uf.same(a,b):
        ans_list.append(0)
    else:
        ans_list.append(uf.size(a)*uf.size(b))
        uf.union(a,b)
    return 0




n,m = [int(_) for _ in input().split()]
l = []
for i in range(m):
    l.append([int(_) for _ in input().split()])
l.reverse()

ans_list = []
uf = UnionFind(n+1)
for i in range(m):
    a,b = l[i]
    check(a, b)
ans_list.reverse()
s = [0] * m
s[0] = ans_list[0]
for i in range(1, len(ans_list)):
    s[i] = s[i-1] + ans_list[i]
for i in range(len(s)):
    print(s[i])

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

int main()
{
	int64_t A, B, C, K;
  	cin >> A >> B >> C >> K;
  	
  	if(K % 2 == 0) cout << A-B << endl;
  	else cout << B-A  << endl;
  
  	
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		String[] list = str.split(" ");
		int a = Integer.parseInt(list[0]);
		int b = Integer.parseInt(list[1]);
		int c = Integer.parseInt(list[2]);
		
		if(a<=c && c<=b){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		
	}

}


Measured memory_bytes: 21204
primes = [0, 0] + [1]*9999
for i in range(2, 101):
    if primes[i]:
        for j in range(i*i, 10001, i):
            primes[j] = 0

while True:
    try:
        n = int(input())
        print(sum([1 for a, b in zip(list(range(1,n+1)), list(range(1,n+1)[::-1])) if primes[a] and primes[b]]))
    except:
        break

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
#define left lft

const int N=1e7+5;
const int maxn=N+10;

int n,m,m0,m1,c[210],k1,left[210];
bool vis[210];
bool comp[maxn]; //composite
int primes,prime[maxn/10];

void prework()
{
	int i,j;
	comp[0]=comp[1]=1;
	for (i=2;i<=N;i++)
	{
		if (!comp[i]) prime[++primes]=i;
		for (j=1;j<=primes&&i*prime[j]<=N;j++)
		{
			comp[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	comp[2]=1;
}

bool match(int u)
{
	for (int v=1;v<=m;v++)
	{
		if (comp[abs(c[u]-c[v])]||vis[v]) continue;
		vis[v]=1;
		if (!left[v]||match(left[v]))
		{
			left[v]=u;
			return 1;
		}
	}
	return 0;
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,x;
	prework();
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&x);
		c[(i<<1)-1]=x;
		c[i<<1]=x+1;
	}
	sort(c+1,c+n+n+1);
	for (i=1;i<=n+n;i++)
		c[i]==c[m]?m--:c[++m]=c[i];

	for (i=1;i<=m;i++)
		c[i]&1?m1++:m0++;
	for (i=1;i<=m;i++)
	{
		memset(vis,0,sizeof(vis));
		if (c[i]&1) k1+=match(i);
	}
	m0-=k1; m1-=k1;
	printf("%d\n",k1+((m0>>1)+(m1>>1))*2+(m0&1)*3);
}


Measured memory_bytes: 13952
import java.util.*;
public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int max = Integer.MIN_VALUE;
		int sum = A+B;
		if(sum>max) max = sum;
		int red = A-B;
		if(red > max) max = red;
		int d = A*B;
		if(d > max) max = d;
		System.out.println(max);
	}
}


Measured memory_bytes: 23764
n,m,c = map( int, input().split() )
b = list( map( int, input().split() ) )
a = []
for _ in range(n):
    a.append( list( map( int, input().split() ) ) )

ans = 0
for i in range(n):
    point = c
    for j in range(m):
        point += a[i][j]*b[j]
    if point > 0:
        ans += 1

print(ans)

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    if (N == 3) {
        cout << "2 5 63" << endl;
        return 0;
    }

    vector<ll> v;
    v.push_back(2);
    v.push_back(4);
    {
        ll num = 3;
        while (v.size() < N - 1 && num + 6 <= 30000) {
            v.push_back(num);
            v.push_back(num + 6);
            num += 12;
        }
    }
    {
        ll num = 8;
        while (v.size() < N - 1 && num + 2 <= 30000) {
            v.push_back(num);
            v.push_back(num + 2);
            num += 6;
        }
    }
    {
        ll num = 6;
        while (v.size() < N) {
            v.push_back(num);
            num += 6;
        }
    }

    sort(v.begin(), v.end());
    REP(i, v.size()) {
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 640
# https://img.atcoder.jp/abc123/editorial.pdf
# 問題D: Cake 123 解法 #3 - さらに高速な解法、priority-queue を用いて O(K log K)

from heapq import heappush, heappop

def solve(X, Y, Z, K, A, B, C):
    def append(cand_a, cand_b, cand_c):
        cand_key = (cand_a, cand_b, cand_c)
        if not cand_key in pushedQ \
                and cand_a < len(A) \
                and cand_b < len(B) \
                and cand_c < len(C):
            yum = A[cand_a] + B[cand_b] + C[cand_c]
            heappush(Q, (-yum, cand_key))
            pushedQ.append(cand_key)

    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    Q = []
    a = 0
    b = 0
    c = 0
    yum = A[a] + B[b] + C[c]
    heappush(Q, (-yum, (a, b, c)))
    pushedQ = [(a, b, c)]

    for _ in range(K):
#       print(Q)
        max_q = heappop(Q)
        max_yum, max_key = max_q[0] * (-1), max_q[1]
        a, b, c = max_key
        print(max_yum)
        append(a+1, b, c)
        append(a, b+1, c)
        append(a, b, c+1)

if __name__ == "__main__":
    X, Y, Z, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    solve(X, Y, Z, K, A, B, C)

Measured memory_bytes: 4460
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<cmath>
#include<set>
#include<stack>

using namespace std;

int p,q,r;

int solve(string::const_iterator& s){
    switch (*s) {
        case '-':{
            s++;
            int res=solve(s);
            return 1+(1-res);
        }
        case '(':{
            s++;
            int res1=solve(s);
            int op=*s;
            s++;
            int res2=solve(s);
            int ans=0;
            if(op=='*'){
                if(res1==0||res2==0){
                    ans=0;
                } else if(res1 == 2 && res2 == 2){
                    ans=2;
                } else {
                    ans = 1;
                }
            } else {
                if(res1 == 2 || res2 == 2){
                    ans = 2;
                } else if(res1 ==1 || res2 == 1){
                    ans=1;
                } else {
                    ans = 0;
                }
            }
            s++;
            return ans;
        }
        default:
            if(*s>='0'&&*s<='2'){
                int ret = *s-'0';
                s++;
                return ret;
            }
            switch (*s) {
                case 'P':
                    s++;
                    return p;
                case 'Q':
                    s++;
                    return q;
                case 'R':
                    s++;
                    return r;
                default:
                    break;
            }
            break;
    }
    return 0;
}
int main()
{
//    freopen("/Users/shitian/Desktop/programmingcCntest/GCJ/gcj/gcj/B-small-practice.in", "r", stdin);
//    freopen("/Users/shitian/Desktop/programmingcCntest/GCJ/gcj/gcj/out.txt", "w", stdout);
//    int tcase;
//    cin>>tcase;
//    for(int tca=1;tca<=tcase;tca++){
//        cout<<"Case #"<<tca<<": ";
//        
//    }
    string str;
    while(cin>>str){
        if(str=="."){
            break;
        }
        int ans=0;
        for(p=0;p<3;p++){
            for(q=0;q<3;q++){
                for(r=0;r<3;r++){
                    string::const_iterator it=str.begin();
                    if(solve(it)==2){
                        ans++;
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1192
from itertools import combinations
def g(i):
    return chr(i+96)
def f(n,i):
    global Ind
    if n==0:
        B.append("".join(A))
        return
    if n==1:
        j = Ind.pop()
        A[j] = g(i)
        B.append("".join(A))
        A[j]=0
        Ind.append(j)
        Ind = sorted(Ind)
        return
    j0 = Ind.pop(0)
    Ind1 = Ind[:]
    A[j0] = g(i)
    for k in range(n):
        for x in combinations(Ind1,n-1-k):
            tmp = []
            for j in range(n-1-k):
                A[x[j]] = g(i)
                tmp.append(x[j])
            for j in tmp:
                Ind.remove(j)
            f(k,i+1)
            for j in tmp:
                A[j] = 0
                Ind.append(j)
            Ind = sorted(Ind)
    Ind.append(j0)
    Ind = sorted(Ind)
    
N = int(input())
A = [0 for _ in range(N)]
Ind = list(range(N))
B = []
f(N,1)
B = sorted(B)
for b in B:
    print(b)

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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()
 
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;
 
typedef long long ll;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

int main()
{
    VI v(5);
    int k;
    cin >>v[0]>>v[1]>>v[2]>>v[3]>>v[4]>>k;
    
    string ans="Yay!";
    REP(i,v.size()-1){
        for(int j=i+1;j<v.size();j++){
            if(v[j]-v[i]>k) ans=":(";
        }
    }

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

Measured memory_bytes: 256
nums = list(map(int, input().split()))
count=0
if (nums[1] % 2 == 1):
        count = nums[0] // nums[1]
        print(count ** 3)
else:
    count = nums[0] // nums[1]
    sum = count ** 3
    count=0
    for i in range(1, nums[0]+1):
        if i % nums[1] == (nums[1] / 2):
            count = count + 1
    sum += count**3
    print(sum)

Measured memory_bytes: 3064
n=int(input())
l=list(map(int,input().split()))
c=0
if n<3:
    print(0)
else:
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            if l[i]==l[j]:
                continue
            for k in range(j+1,n):
                if l[k]==l[i] or l[k]==l[j]:
                    continue
                if l[k]+l[i]>l[j] and l[i]+l[j]>l[k] and l[k]+l[j]>l[i]:
                    c+=1
    print(c)

Measured memory_bytes: 9212
import java.awt.*;
import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] h=new int[n];
        for(int i=0;i<n;i++){
            h[i]=sc.nextInt();
        }
        int[] dp=new int[n];
        dp[0]=0;
        dp[1]=Math.abs(h[0]-h[1]);
        for(int i=2;i<n;i++){
            dp[i]=Integer.min(dp[i-2]+Math.abs(h[i]-h[i-2]),dp[i-1]+Math.abs(h[i]-h[i-1]));
        }
        System.out.println(dp[n-1]);
    }
    public static int setBit(long n){
        int count=0;
        while(n>0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
}

Measured memory_bytes: 50164
N,M = [int(i) for i in input().split()]
A = [input().strip() for _ in range(N)]
B = [input().strip() for _ in range(M)]
flag = 0
for v in range(N-M+1):
  for h in range(N-M+1):
    for i in range(M):
      for j in range(M):
        if A[v+i][h+j] == B[i][j]:
          flag += 1
    if flag == M*M:
      break
    else:
      flag = 0
  if flag == M*M:
    break

if flag==0:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 3064
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i64,
        b: i64,
    }
    if(a<b){
        println!("a < b");
    }
    if(a>b){
        println!("a > b");
    }
    if(a==b){
        println!("a == b");
    }
}


Measured memory_bytes: 5024
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,K,Q;
  cin >> N >> K >> Q;
  vector<int> A(Q);
  for(int i=0;i<Q;i++){
    cin >> A.at(i);
  }
  
  vector<int> man(N,K);
  for(int i=0;i<Q;i++){
    man.at(A.at(i)-1)++;
  }

  for(int i=0;i<N;i++){
    man.at(i) = man.at(i)-Q;
  }

  for(int i=0;i<N;i++){
    if(man.at(i)>0){
      cout << "Yes" << endl;
    }
    else{
      cout << "No"  << endl;
    }
  }
}

Measured memory_bytes: 1408
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,sx[200],sy[200];

int main()
{
	while(scanf("%d",&n),n)
	{
		int x=0,X=0,y=0,Y=0;
		for(int i=1;i<n;i++)
		{
			int a,b; scanf("%d%d",&a,&b);
			sx[i]=sx[a]+dx[b]; sy[i]=sy[a]+dy[b];
			x=min(x,sx[i]); X=max(X,sx[i]);
			y=min(y,sy[i]); Y=max(Y,sy[i]);
		}
		printf("%d %d\n",X-x+1,Y-y+1);
	}
	return 0;
}

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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

// UnionFindTree
// T: 可換群
template<class T = int>
class UnionFindTree {
    const int n;
    std::vector<int> par, size;
    std::vector<T> diff_potential;
public:
    // 要素数を指定して初期化
    UnionFindTree(int n, T ZERO = 0) : n(n), par(n), size(n), diff_potential(n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            size[i] = 0;
            diff_potential[i] = ZERO;
        }
    }

    // 要素iが属する集合を表す木の根を求める
    int getRoot(int i) {
        if (par[i] == i) {
            return i;
        } else {
            int r = getRoot(par[i]);
            diff_potential[i] += diff_potential[par[i]];
            return par[i] = r;
        }
    }

    // 要素iのポテンシャル
    T getPotential(int i) {
        getRoot(i);
        return diff_potential[i];
    }

    // 要素iと要素jのポテンシャル差
    T getDiff(int i, int j) {
        return getPotential(j) - getPotential(i);
    }

    // getDiff(i, j) = dとなるように要素iと要素jの属する集合を併合
    void unite(int i, int j, T d = 0) {
        d -= getDiff(i, j);
        i = getRoot(i);
        j = getRoot(j);
        if (i == j)return;
        if (size[i] < size[j])swap(i, j), d = -d;
        par[j] = i;
        size[i] += size[j];
        diff_potential[j] = d;
    }

    // 要素iと要素jが同じ集合に属するか否か
    bool isSame(int i, int j) {
        return getRoot(i) == getRoot(j);
    }

    // 要素iが属する集合の大きさ
    int getSize(int i) {
        return size[getRoot(i)];
    }
};

int N, M;
int L[220000], R[220000], D[220000];

signed main() {
    cin >> N >> M;
    UnionFindTree<> uf(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> L[i] >> R[i] >> D[i];
        if (uf.isSame(L[i], R[i])) {
            if (uf.getDiff(L[i], R[i]) != D[i]) {
                cout << "No" << endl;
                return 0;
            }
        } else {
            uf.unite(L[i], R[i], D[i]);
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
typedef long long ll;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans=LINF,a,b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>n>>a;
    rep(i,n)cin>>b[i];
    sort(b,b+n);
    rep(i,n){
        if(i+a-1==n)break;
        ans=min(ans,b[i+a-1]-b[i]);
    }
    Cout(ans);
    return 0;
}


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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int n;cin>>n;

	int ct=0;
	for(int i=1; i<=n; i++){
		if(i%2 !=0)ct++;
	}

	printf("%0.10f",(double)ct/n);


}




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

const int N=100+5;

const int M=1e5 + 5;
int n,W;

long long  w[N];

long long c[N];

long long mem[N][M];

long long  knapsack(int i,long long TW){

if (i==n)
    return 0;
if(mem[i][TW]!=-1){

    return mem[i][TW];

}

long long p1=knapsack(i+1,TW);
long long p2=0;
if(TW+w[i]<=W){
    p2=knapsack(i+1,TW+w[i])+c[i];
}

mem[i][TW]=max(p1,p2);
return mem [i][TW];

}

int main(){

scanf("%d%d",&n,&W);

for(int i=0;i<n;i++){

    scanf("%lld%lld",&w[i],&c[i]);

}
memset(mem,-1,sizeof mem);

printf("%lld\n" , knapsack(0 , 0));

}


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

int main() {
  int l, r, d;
  cin >> l >> r >> d;
  int ans = r/d;
  ans -= (l-1)/d;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/

int main(void){
  int N;
  cin >> N;
  int a, b, c;
  a = N/100;
  b = N/10-a*10;
  c = N -a*100-b*10;
  if (a == c) cout <<"Yes" << endl;
  else cout << "No" << endl;


}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,a[110000],l,r,mi,f[220000];
long long m;
inline void add(int x){
	while (x<=n+n){
		f[x]++;
		x+=x&(-x);
	}
}
inline long long ask(int x){
	long long ans=0;
	while (x){
		ans+=f[x];
		x-=x&(-x);
	}
	return ans;
}
inline bool che(int x){
	int s=n+1;long long ans=0;//s=n TLE
	fo(i,0,n+n) f[i]=0;
	add(s);
	fo(i,1,n){
		if (a[i]>=x) s++;else s--;
		ans+=ask(s);
		add(s);
	}
	return ans>=m;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	m=n*1ll*(n+1)/2;
	m=(m+1)/2;
	l=0x7fffffff;r=0;
	fo(i,1,n){
		if (a[i]<l) l=a[i];
		if (a[i]>r) r=a[i];
	}
	l--;r++;
	while (l+3<r){
		mi=(l+r)>>1;
		if (che(mi)) l=mi+1;else r=mi-1;
	}
	fd(i,r+1,l-1) if (che(i)){//che(mi)!!!
		printf("%d\n",i);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
#define intxt freopen("in.txt","r",stdin)
const int maxn=1e6+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
inline void umax(int &p,int q){if(p<q)p=q;}
inline void umin(int &p,int q){if(p>q)p=q;}
inline ll read()
{
    ll x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,t,ok[maxn];
void gao(int p)
{
    for(int i=2;i<=p;i++)
    {
        while(p%i==0)ok[i]++,p/=i;
        if(p==1)return;
    }
}
int main()
{
    int i,j;
    scanf("%d",&n);
    rep(i,2,n)
    {
        gao(i);
    }
    ll ans=1;
    rep(i,1,n)ans*=(ok[i]+1),ans%=mod;
    printf("%lld\n",ans);
    //system("Pause");
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<tuple<string, int, int>> dict;
	rep(i, n) {
		string s;
		int p;
		cin >> s >> p;
		dict.push_back(make_tuple(s, 100-p, i + 1));
	}
	sort(dict.begin(), dict.end());

	rep(i, n) {
		cout << get<2>(dict[i]) << endl;
	}
}

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

int main() {
  int A, B;
  int x,y;
  cin >> A >> B;
  
  x = (A *B) % 2  ;
  if ( x ==1 ) {
    cout << "Odd" ;
  }
  else {
    cout << "Even" ;
  }
  


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
int main(void){
    // Your code here!
    int N, M;
    cin >> N >> M;
    
    vector<int>oks(N+1, true);//配列をtrue(1)で埋める
    for (int i = 0; i<M; ++i){
        int a; cin >> a;
        oks[a]=false;
    }
    
    vector<long long int>dp(N+1);
    dp[0]=1;
    for (int now = 0; now<N; ++now){
        for (int next = now+1; next<=min(N, now+2); ++next){
            if(oks[next]){//通常の場合ここがない。
                dp[next]+=dp[now];//基本はnext=now+1, now+2のみ
                dp[next]%=mod;
            }
        }
    }
    
    cout<<dp[N]<<endl;
    return 0;
}


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

namespace ITP1_10_A
{
    public class Program

    {
        public static void Main(string[] args)
        {
            double[] line = ReadDoubleAr();
            Console.WriteLine("{0}",Math.Sqrt(Math.Pow((line[2]-line[0]),2)+Math.Pow((line[3] - line[1]), 2)));
        }

        static string ReadSt() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Console.ReadLine()); }
        static long ReadLong() { return long.Parse(Console.ReadLine()); }
        static double ReadDouble() { return double.Parse(Console.ReadLine()); }
        static string[] ReadStAr(char sep = ' ') { return Console.ReadLine().Split(sep); }
        static int[] ReadIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
        static long[] ReadLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
        static double[] ReadDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }

    }

}



Measured memory_bytes: 18088
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;



int main(){
	int x,y,z,k;
	cin >> x >> y >> z >> k;
	vector<ll> A(x);
	vector<ll> B(y);
	vector<ll> C(z);
	
	for(int i=0;i<x;++i){
		cin >> A[i];
	}
	for(int i=0;i<y;++i){
		cin >> B[i];
	}
	for(int i=0;i<z;++i){
		cin >> C[i];
	}
	
	sort(A.rbegin(),A.rend());
	sort(B.rbegin(),B.rend());
	sort(C.rbegin(),C.rend());
	
	priority_queue<pair<pair<ll,ll>,pair<ll,ll> > > que;
	que.push(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[0]+B[0]+C[0],0),pair<ll,ll>(0,0)));
	int cnt = 0;
	set<pair<pair<ll,ll> ,pair<ll,ll> > > se;
	while(!que.empty() && cnt < k){
		pair<pair<ll,ll>,pair<ll,ll> >  p = que.top();que.pop();
		ll a = p.first.second;
		ll b = p.second.first;
		ll c = p.second.second;
		cnt++;
	
		cout << p.first.first << endl;
		
		if(a + 1 < x  && se.find(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a+1]+B[b]+C[c],a+1),pair<ll,ll>(b,c)))==se.end() ){
			que.push(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a+1]+B[b]+C[c],a+1),pair<ll,ll>(b,c)));
			se.insert(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a+1]+B[b]+C[c],a+1),pair<ll,ll>(b,c)));
		}
		if(b + 1 < y && se.find(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b+1]+C[c],a),pair<ll,ll>(b+1,c))) == se.end()){
			que.push(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b+1]+C[c],a),pair<ll,ll>(b+1,c)));
			se.insert(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b+1]+C[c],a),pair<ll,ll>(b+1,c)));
		}
		if(c + 1 < z && se.find(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b]+C[c+1],a),pair<ll,ll>(b,c+1))) == se.end()){
			que.push(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b]+C[c+1],a),pair<ll,ll>(b,c+1)));
			se.insert(pair<pair<ll,ll>,pair<ll,ll> >(pair<ll,ll>(A[a]+B[b]+C[c+1],a),pair<ll,ll>(b,c+1)));
		}
		
		
	}
	
	return 0;
}



Measured memory_bytes: 1152
inf = 10 ** 18
P = 10 ** 9 + 7

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

A_all = sum(A)

xi = min(A[0], B[0])
A[0] -= xi
B[0] -= xi
for i in range(N):
    yi = min(B[i], A[i + 1])
    A[1 + i] -= yi
    B[i] -= yi
    #
    if i < N - 1:
        xi = min(A[1 + i], B[1 + i])
        A[1 + i] -= xi
        B[1 + i] -= xi
    #
    # print("#", A, B, A_all - sum(A))
    
A_r = list(reversed(A))
B_r = list(reversed(B))


xi = min(A_r[0], B_r[0])
A_r[0] -= xi
B_r[0] -= xi
for i in range(N):
    yi = min(B_r[i], A_r[i + 1])
    A_r[1 + i] -= yi
    B_r[i] -= yi
    #
    if i < N - 1:
        xi = min(A_r[1 + i], B_r[1 + i])
        A_r[1 + i] -= xi
        B_r[1 + i] -= xi
    #
    # print("#", A, B, A_all - sum(A))

print(A_all - sum(A))

Measured memory_bytes: 18624
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define mat vector<vector<ll>>

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  ll n;
  cin >> n;
  
  vector<long double> x(n),y(n);
  vector<vector<long double>> v;
  for(ll i=0;i<n;i++){
    cin >> x[i] >> y[i];
    v.push_back({atan2l(y[i],x[i]),x[i],y[i]});
  }
  sort(v.begin(),v.end());

  long double ans=0;
  for(ll i=0;i<n;i++){
    for(ll j=i+1;j<n;j++){
      ll X=0,Y=0;
      for(ll k=i;k<=j;k++){
        X+=v[k][1];
        Y+=v[k][2];
      }
      long double kans=sqrt(X*X+Y*Y);
      ans=max(ans,kans);
      
      X=0,Y=0;
      for(ll k=j;k<n;k++){
        X+=v[k][1];
        Y+=v[k][2];
      }
      for(ll k=0;k<=i;k++){
        X+=v[k][1];
        Y+=v[k][2];
      }
      kans=sqrt(X*X+Y*Y);
      ans=max(ans,kans);
    }
  }
  //cout << ans << endl;

  for(ll i=0;i<n;i++){
    long double kans=sqrt(x[i]*x[i]+y[i]*y[i]);
    ans=max(ans,kans);
  }

  printf("%0.20Lf\n",ans);

}

Measured memory_bytes: 3908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,x,n) for(int i=x;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=50005,INF=1<<29;
vector<int> dy={1,1,0,-1,-1,0},dx={0,1,1,0,-1,-1};
int dis[MAX];

void BFS(int u,int t){
    queue<int> Q;
    Q.push(u);
    
    while(!Q.empty()){
        int a=Q.front();Q.pop();
        if(dis[a]==t) continue;
        
        for(int i=0;i<6;i++){
            int x=a%200,y=a/200;
            int xto=x+dx[i],yto=y+dy[i];
            //if(xto<0||yto<0||xto>=100||yto>=100) continue;
            
            if(dis[xto+yto*200]==-1){
                dis[xto+yto*200]=dis[x+y*200]+1;
                Q.push(xto+yto*200);
            }
        }
    }
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int T,N;cin>>T>>N;
        if(T+N==0) break;
        
        memset(dis,-1,sizeof(dis));
        
        for(int i=0;i<N;i++){
            int a,b;cin>>a>>b;
            a+=100;b+=100;
            dis[a+b*200]=INF;
        }
        
        int a,b;cin>>a>>b;
        a+=100;b+=100;
        
        dis[a+b*200]=0;
        
        BFS(a+b*200,T);
        int cnt=0;
        
        for(int i=0;i<MAX;i++){
            if(dis[i]!=-1&&dis[i]<=T) cnt++;
        }
        
        cout<<cnt<<endl;
    }
    
}



Measured memory_bytes: 3336
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    string t;
    cin >> t;
    int n = s.size();
    int m = t.size();
    int mam = INT_MIN, i = 0;
    while(i <= n-m)
    {
        //cout << "Case " << i << "\n";
        int cnt = 0;
        for(int j = i, k = 0; j< i+m && k < m;j++, k++ )
        {
            //cout << s[j] << " " << t[k] << "\n";
            if(s[j]==t[k])
            {
                cnt++;
            }
        }
        mam = max(mam,cnt);
        i++;
    }
    cout << m-mam << "\n";
}



Measured memory_bytes: 3592
#include <iostream>
using namespace std;
int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    int ans=1e9;
    for (int i=0; i<max(2*x,2*y)+2; i+=2){
        int cost=c*i+b*max(0,y-i/2)+a*max(0,x-i/2);
        ans=min(ans,cost);
    }
    cout << ans <<endl;
}

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

int main(void) {
    int a, b;
    cin >> a >> b;
    char ans = 'x';
    if (a + b == 15) ans = '+';
    if (a * b == 15) ans = '*';
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3560
n,m=map(int,input().split())
S = []
for _ in range(m):
  t = list(map(int,input().split()))[1:]
  t = [v-1 for v in t]
  S.append(t)
p = list(map(int,input().split()))

cnt = 0
for i in range(2**n):
  ok = True
  for j,s in enumerate(S):
    l = 0
    for v in s:
      if (i>>v) & 1: l+=1
    if l%2 != p[j]:
      ok = False
      break
  if ok:
    cnt += 1
print(cnt)

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vector<int> as(N);
    for(int i=0; i<N; i++) cin >> as.at(i);

    while(K--)
    {
        vector<int> nas(N, 0);
        int numnax = 0;
        for(int i=0; i<N; i++)
        {
            int l = max(0, i-as.at(i));
            int r = min(N-1, i+as.at(i));
            nas.at(l)++;
            if(r+1<N) nas.at(r+1)--;
        }
        if(nas.at(0)==N) numnax++;
        for(int i=1; i<N; i++)
        {
            nas.at(i) += nas.at(i-1);
            if(nas.at(i)==N) numnax++;
        }
        as = nas;
        if(numnax==N) break;
    }
    for(int i=0; i<N; i++)
    {
        if(i!=N-1) cout << as.at(i) << ' ';
        else cout << as.at(i) << '\n';
    }

    return 0;
}

Measured memory_bytes: 4864
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top, S[1000];

void push(int x){
    /* topを加算してからその位置へ挿入 */
    S[++top] = x;
}

int pop(){
    top--;
    /* topが指していた要素を返す */
    return S[top+1];
}

int main(){
    int a, b;
    top = 0;
    char s[100];
    while(scanf("%s", s) != EOF){
        if(s[0] == '+'){
            a = pop();
            b = pop();
            push(a + b);
        }else if(s[0] == '-'){
            b = pop();
            a = pop();
            push(a - b);
        }else if(s[0] == '*'){
            a = pop();
            b = pop();
            push(a * b);
        }else{
            push(atoi(s));
        }
    }
    printf("%d\n", pop());

    return 0;
}


Measured memory_bytes: 2104