akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
/*	#include <boost/math/common_factor.hpp>  boost::math::lcm(10,20) ---> use it to find lcm. fill_n(&an[0][0],n*m,0); typedef long long ll;*/
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long 
#define PI pair<int , int >
#define mpr make_pair
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define FO(i,a,b) for(int i = (int)a;i < (int)b;++i)
#define FE(i,a,b) for(int i = (int)a;i <= (int)b;++i)
const int MOD = 1e9+7;
const int MAXN = 1e5+3;
const int inf = 2e9;
int max(int a,int b){	if(a > b)return a; else return b; }
int min(int a, int b){	if(a < b)return a; else return b; }
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
bool cmp(PI p1,PI p2){
	if(p1.ff < p2.ff)return true;	// You should not be writing p1.ss <= p2.ss !!!
	else if(p1.ff == p2.ff){ if(p1.ss < p2.ss)return true; return false; }
	return false;
}

void solve(){
	int n;
	cin >> n;
	int a[n];
	FO(i,0,n)cin >> a[i];
	int j = 1;
	int ans = 0;
	FO(i,0,n){
		if(a[i] == j){
			j++;
			ans++;
		}
	}
	if(j>1)cout << n-ans << endl;
	else cout << -1 << endl;
}

int32_t main(){
	IO;
	#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	#endif // ONLINE_JUDGE
	// std::cout << std::setprecision(15); std::cout << std::fixed;
	int t; t = 1;
	// cin >> t;
	FE(i,1,t)
		solve();
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
#define ll long long 
string s;
int main()
{
	cin>>s;
	int ans=0;
	for(int i=0,j=s.size()-1;i<j;){
		if(s[i]==s[j]){
			i++;
			j--;
		}
		else if(s[i]=='x'){
			i++;
			ans++;
		}
		else if(s[j]=='x'){
			j--;
			ans++;
		}
		else{
			cout<<"-1";
			return 0;
		}
	}
	cout<<ans;
    return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;
const int Maxn = 1e9 + 10;
const int N = 1e5 + 10;
const int INF=(0x7fffffff)/2;
int dp[105][305];
int n, W;
int w[105], v[105];
int d, ans=0;
int main(){
	int i, j, k;
	while(~scanf("%d%d",&n,&W)){
		for(i = 1; i <= n; i++)
			scanf("%d %d", &w[i], &v[i]);
		for(i = 0; i <= n; i++)
			for(j = 0; j <= 300; j++)
				dp[i][j]=0;
		for(i = 1; i <= n; i++)
			for(j = n; j > 0; j--)
				for(k = 300; k >= 0; k--){
				d = w[i] - w[1];
				if(k < d)
					break;
				dp[j][k] = max(dp[j][k], dp[j-1][k-d] + v[i]);
				}
		for(i = 0; i <= n; i++)
			for(j = 0; j <= 300; j++)
				if(1ll * i * w[1] + 1ll * j <= 1ll * W)
					ans = max(ans, dp[i][j]);
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void){
	int A,B,C,D;
	int a[4],min;
	
	scanf("%d",&A);	scanf("%d",&B);
	scanf("%d",&C);	scanf("%d",&D);
	min = a[0] = A + C;	a[1] = A + D;
	a[2] = B + C;	a[3] = B + D;
	
	for(int i = 1;i < 4; ++i){
		if(min > a[i])	min = a[i];
	}
	printf("%d\n",min);
	return 0;
}


Measured memory_bytes: 128
line = int(input())
column = int(input())
min_black_tile = int(input())
paint_tile = 0
count = 0

if line > column:
  while paint_tile < min_black_tile:
    paint_tile += line
    count += 1
  print(count)
else:
  while paint_tile < min_black_tile:
    paint_tile += column
    count += 1
  print(count)

Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#define N 205
using namespace std;

struct st{
	int x, y, c;
} a[N];
int n, ans;
set<int> b;

bool cmp(st p, st q) {return p.x < q.x;}

int main()
{
	int i, t1, t2;
	set<int>::iterator it;
	cin >> n;
	for (i = 0; i < n; i++) scanf("%d %d", &a[i].x, &a[i].y), a[i].c = 0;
	for (i = n; i < n * 2; i++) scanf("%d %d", &a[i].x, &a[i].y), a[i].c = 1;
	sort(a, a + n * 2, cmp);
	for (i = 0; i < n * 2; i++) {
		if (!a[i].c) b.insert(a[i].y);
		else {
			it = b.lower_bound(a[i].y);
			if (it == b.begin()) continue;
			it--;
			ans++;
			b.erase(it);
		}
	}
    cout << ans << endl;
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  long A,B[N-1],sum=0;
  for(int i=0;i<N-1;i++){
    cin >> B[i];
  }
  sum = B[0];
  for(int i=1;i<N;i++){
    A = min(B[i-1],B[i]);
    sum += A;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> X(M);
    for (ll i = 0; i < M; i++) {
        cin >> X[i];
    }

    if (N >= M) {
        cout << 0 << endl;
        return 0;
    }

    sort(X.begin(), X.end());
    vector<ll> diff;
    for (ll i = 1; i < M; i++) {
        diff.push_back(X[i] - X[i - 1]);
    }
    sort(diff.begin(), diff.end());
    ll ans = 0;
    for (ll i = 0; i < M - N; i++) {
        ans += diff[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 2168
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;
    ll ans = INT_MAX;
    for (ll i = 0; i < S.size() - 2; i++) {
        ans = min(ans, (ll)abs(753 - stoll(S.substr(i, 3))));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

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

        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(is);

        List<String> mylist = new ArrayList<>();

        // 標準入力からの値を変数strinputに代入
        String strinput = reader.readLine();

        while (strinput != null) {

            mylist.add(strinput);
            strinput = reader.readLine();

        }

        String arr01[] = mylist.get(0).split(" ");
        String arr02[] = mylist.get(1).split(" ");
        int n = Integer.valueOf(arr01[0]);

        String arr_result[] = new String[n];

        Arrays.fill(arr_result, "0");

        for (int i = n - 1; i >= 1; i--) {
            int a = Integer.valueOf(arr02[i - 1]);
            int val = Integer.valueOf(arr_result[a - 1]);
            arr_result[a - 1] = String.valueOf(val + 1);

            //            System.out.println(Arrays.toString(arr_result));
        }
        String result = String.join(System.getProperty("line.separator"), arr_result);

        System.out.println(result);
    }

}


Measured memory_bytes: 74940
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ull unsigned long long 
#define ld long double
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define er erase
#define line cout<<"\n";
#define mod  1000000007

int main()
{
    string s;
    cin>>s;
    int t=s.length();
    if(s[t-1]=='s')
    cout<<s+"es";
    else
    cout<<s+"s";
    
}

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

#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl

#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)

#define FOREACH(x,a) for(auto&& (x) : (a) )

#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])

#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl

#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}

#define ALL(obj) (obj).begin(),(obj).end()

#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template <class T = ll>
T IN(){T x;cin>>x;return (x);}

template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
  VECCIN(head);
  VT2(move(tail)...);
}

template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
  seco[head]=IN();
  VT3(head,move(tail)...);
}

#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc

// #include <boost/multiprecision/cpp_ll.hpp>
// using namespace boost::multiprecision; // cpp_ll

#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>

#define pb(a) push_back(a)
#define mp make_pair

signed main(){
    CIN(n);
    VC1(n,a);
    COUT(accumulate(ALL(a),0LL) - n);
}


Measured memory_bytes: 256
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def inverse(self, k):
        """kの逆元を求める O(1)"""
        return (self.inv_fact[k] * self.fact[k - 1]) % self.MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r)
        kが大きいが、r <= nを満たしているときに使用
        """
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


p = int(input())
a = list(map(int, input().split()))
comb = Combination(p - 1, p)


b = [0] * p
for i in range(p):
    for j in range(p):
        # (x - j) ^ (p - 1) の係数x^iの部分
        tmp = pow(-j, (p - 1 - i), p) * comb.combination(p - 1, i)
        b[i] -= a[j] * tmp
        b[i] %= p
b[0] = a[0]

print(*b)

Measured memory_bytes: 74792
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = ((int)a) - 1; i >= ((int)a); --i)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

void dump_impl(string s) {}
template <class H, class... T>
void dump_impl(string s, H head, T... tail) {
    int p = 0;
    rep(i, 0, sz(s)) {
        char x = s[i];
        if (p == 0 && x == ',') {
            cerr << "=" << head << ", ";
            dump_impl(s.substr(i + 1), tail...);
            return;
        } else {
            cerr << x;
            if (x == '(') p++;
            if (x == ')') p--;
        }
    }
}
#ifdef LOCAL
#define dump(...) do { cerr << "\x1b[33;1m"; dump_impl(#__VA_ARGS__ ",", __VA_ARGS__); cerr << "\x1b[0m" << endl; } while (0) 
#else
#define dump(...)
#endif

constexpr int DY[8] = {-1, 0, 1, 0, -1, 1, 1, -1};
constexpr int DX[8] = {0, 1, 0, -1, 1, 1, -1, -1};

struct Range {
    int mn_x;
    int mx_x;
    int mn_y;
    int mx_y;
    Range() {
        mn_x = 1000;
        mn_y = 1000;
        mx_x = -1000;
        mx_y = -1000;
    }
    void update(int y, int x) {
        mn_x = min(mn_x, x);
        mx_x = max(mx_x, x);
        mn_y = min(mn_y, y);
        mx_y = max(mx_y, y);
    }
};

void solve(int H, int W) {
    vector<string> S(H); rep(i, 0, H) cin >> S[i];

    vector<Range> range(26);
    rep(i, 0, H) {
        rep(j, 0, W) {
            if (S[i][j] == '.') continue;
            int x = S[i][j] - 'A';
            range[x].update(i, j);
        }
    }

    vector<vector<int>> G(26);
    vector<int> deg(26);
    rep(i, 0, 26) {
        bool ng = false;
        rep(y, range[i].mn_y, range[i].mx_y + 1) {
            rep(x, range[i].mn_x, range[i].mx_x + 1) {
                if (S[y][x] == '.') {
                    ng = true;
                } else if (S[y][x] - 'A' != i) {
                    G[S[y][x] - 'A'].push_back(i);
                    deg[i]++;
                }
            }
        }
        if (ng) {
            cout << "SUSPICIOUS" << endl;
            return;
        }
    }
    queue<int> q;
    rep(i, 0, 26) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }
    int cnt = 0;
    while (sz(q)) {
        int v = q.front(); q.pop();
        cnt++;
        for (int w : G[v]) {
            deg[w]--;
            if (deg[w] == 0) {
                q.push(w);
            }
        }
    }
    if (cnt != 26) {
        cout << "SUSPICIOUS" << endl;
    } else {
        cout << "SAFE" << endl;
    }
}

signed main() {
    int T;
    cin >> T;
    rep(i, 0, T) {
        int W, H;
        cin >> H >> W;
        if (W == 0 && H ==0) break;
        solve(H, W);
    }
}


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

int main() {
  ll t1,t2,a1,a2,b1,b2;
  cin>>t1>>t2>>a1>>a2>>b1>>b2;
  if (a1*t1+a2*t2==b1*t1+b2*t2) {
    cout<<"infinity"<<endl;
    return 0;
  }
  if (a1*t1+a2*t2>b1*t1+b2*t2) {
    swap(a1,b1);
    swap(a2,b2);
  }
  if (a1*t1<b1*t1) {
    cout<<0<<endl;
    return 0;
  }
  if (((a1-b1)*t1)%((b1*t1+b2*t2)-(a1*t1+a2*t2))==0) {
    cout<<(((a1-b1)*t1)/((b1*t1+b2*t2)-(a1*t1+a2*t2))+1)*2-2<<endl;
    return 0;
  }
  cout<<(((a1-b1)*t1)/((b1*t1+b2*t2)-(a1*t1+a2*t2))+1)*2-1<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (int i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (int i = x.size()-1; i >= 0; i--)
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define fst first
#define scd second
#define nextline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int main()
{
    double a, b, x;
    cin>>a>>b>>x;
    if (x * 1.0 <= a * a * b / 2.0) {
        cout<<setprecision(9)<<atan((a * b * b / 2.0) / x) / M_PI * 180<<endl;
    } else {
        double t = (2.0 * x / a / a - 2 * b) / a;
        cout<<setprecision(9)<<-atan(t) / M_PI * 180<<endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    int n;
    std::cin>>n;

    std::string s = std::to_string(n);
    std::string ans  = "Yes";
    if(s.find('9') == std::string::npos){
        ans = "No";
    }
    std::cout<<ans<<std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n;
    cin>>n;
    int a[n],b[n];
    pair<int,int>p[n];
    int s=0;
    bool flag=true;
    for (int i = 0; i < n; ++i) {
        cin>>a[i]>>b[i];
        p[i].first=b[i];
        p[i].second=a[i];
    }

    sort(p,p+n);
    for (int i = 0; i < n; ++i)
    {
        s+=p[i].second;
        if(s>p[i].first)
        {
            flag=false;
            break;
        }
    }

    if(flag)
        cout<<"Yes";
    else
        cout<<"No";
}

Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
using ll = long long;

int main(){
    std::string s; std::cin >> s;
    std::string keyence = "keyence";
    for(int i=0; i<keyence.size()+1; i++){
        if(s.substr(0,i)+s.substr(s.size()-(keyence.size()-i))==keyence){
            std::cout << "YES";
            return 0;
        }
    }
    std::cout << "NO";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c;
    cin>>a>>b>>c;
    cout << (max(c-a+b,0))<<endl;
    return 0;
}



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

using namespace std;

const int MAX = 1e5+10;

int h[MAX];
int dp[MAX];

int main(){

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

    int n, k;
    cin >> n >> k;

    for(int i=1;i<=n;++i)
        cin >> h[i];
    
    dp[1] = 0; 
    for(int i=2;i<=n;++i){
        dp[i] = (int)1e9+10;
        for(int j=1;j<=k;++j)
            if(i-j >= 1)
                dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]));
    }

    cout << dp[n] << '\n';

    return 0;
}

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

bool f;

int expr(string, int&);
int term(string, int&);
int factor(string, int&);
int number(string, int&);


int expr(string s, int& p) {
  int res = term(s, p);
  while ( p < (int)s.size() ) {
    if ( s[p] == '+' ) {
      p++;
      res += term(s, p);
      continue;
    }
    break;
  }
  return res;
}

int term(string s, int& p) {
  int res = factor(s, p);
  while ( p < (int)s.size() ) {
    if ( s[p] == '*' ) {
      p++;
      res *= factor(s, p);
      continue;
    }
    break;
  }
  return res;
}

int factor(string s, int& p) {
  int res;
  if ( s[p] == '(' ) {
    p++;
    res = expr(s, p);
    p++;
  } else {
    res = number(s, p);
  }
  return res;
}

int number(string s, int& p) {
  int res = 0;
  while ( p < (int)s.size() && isdigit(s[p]) ) {
    res = res*10+s[p++]-'0';    
  }
  return res;  
}

int main() {
  map<string, int> wei;
  {
    string s;
    while ( cin >> s, s != "END_OF_FIRST_PART" ) {
      int a;
      cin >> a;
      wei[s] = a;      
    }
  }

  string s;
  while ( cin >> s, s != "0" ) {
    // cout << s << endl;
    string t = "";
    int l = s.size();
    bool flag = true;
    for ( int i = 0; i < l; i++ ) {
      if ( s[i] == '(' || s[i] == ')' ) {
	t.push_back(s[i]);
	if ( s[i] == ')' && i < l-1 ) {	  
	  if ( isdigit(s[i+1]) ) t.push_back('*');
	  else if ( s[i+1] != ')' ) {
	    t.push_back('+');
	  }
	}
      }
      else if ( isdigit(s[i]) ) {
	string add = "";	
	while ( 1 ) {
	  if ( i == l || !isdigit(s[i]) ) {	    
	    i--;
	    break;
	  }
	  add += s[i];
	  i++;
	}
	t += add;	
	if ( i < l-1 ) {	  
	  if ( isdigit(s[i+1]) ) t.push_back('*');
	  else if ( s[i+1] != ')' ) {
	    t.push_back('+');
	  }
	}
      } else {
	string a = ""; a += s[i];	
	if ( i < l-1 && 'a' <= s[i+1] && s[i+1] <= 'z' ) {
	  a += s[i+1];
	  i++;	  
	}
	if ( wei.count(a) == 0 ) {
	  flag = false;	  
	  break;	  
	} else {
	  t += to_string(wei[a]);	  
	}
	if ( i < l-1 ) {	  
	  if ( isdigit(s[i+1]) ) t.push_back('*');
	  else if ( s[i+1] != ')' ) {
	    t.push_back('+');
	  }
	}
      }
    }
    if ( !flag ) {
      cout << "UNKNOWN" << endl;
    }
    else {
      int p = 0;
      cout << expr(t, p) << endl;
    }
  }
}



Measured memory_bytes: 3244
/*           pmaik
    ░▒▓█►─═ Maneesh ═─◄█▓▒░


          ( •̪●)
        ███████]▄▄▄▄▄▄▄▄▃  ▃  ▃ 
    ▂▄▅█████████▅▄▃▂
   [███████████████████]
  ...◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤......  */

#include<bits/stdc++.h>
using namespace std;
#define inf() ifstream cin("in00.txt")
#define onf() ofstream cout("out00.txt")
#define ll long long int
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N=105;
const int M=100050;

ll dp[N][M];

int main()
{
    fastio;

    ll n,W;
    cin>>n>>W;

    ll w[n+1],v[n+1],i,j;
    for(i=1; i<=n; i++)
    {
        cin>>w[i]>>v[i];
    }

    for(j=0; j<=W; j++)
    {
        for(i=0; i<=n; i++)
        {
            if(i==0 || j==0)
            {
                dp[i][j]=0;
            }
            else if(j>=w[i])
            {
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
            }
            else
            {
                dp[i][j]=dp[i-1][j];
            }
        }
    }

    cout<<dp[n][W]<<endl;

    return 0;
}



Measured memory_bytes: 82540
#include<bits/stdc++.h>
#define ll long long
#define maxn 200001
#define pb push_back
#define fi first
#define se second
#define mod 1000000007
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

vi AdjList[maxn];
vi even;
vi odd;
bool check[maxn];
int ans[maxn];

void dfs(int start, int cnt)
{
	check[start] = true;
	if (cnt % 2 == 0)	even.pb(start);
	else odd.pb(start);
	for (int i = 0; i < AdjList[start].size(); i++)
	{
		int u = AdjList[start][i];
		if (!check[u])
		{
			dfs(u, cnt+1);
		}
	}
}
bool lost[maxn];

int main()
{
	int n;	cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int u, v;	cin >> u >> v;
		AdjList[u].pb(v);
		AdjList[v].pb(u);
	}
	dfs(1, 0);
	int temp = n/3;
	if (temp >= min(odd.size(), even.size()))
	{
		if (odd.size() <= even.size())
		{
			for (int i = 0; i < odd.size(); i++)
			{
				ans[odd[i]] = (i+1)*3;
				lost[(i+1)*3] = true;
			}
		}
		else
		{
			for (int i = 0; i < even.size(); i++)
			{
				ans[even[i]] = (i+1)*3;
				lost[(i+1)*3] = true;
			}
		}
		int cnt = 1;
		for (int i = 1; i <= n; i++)
		{
			if (ans[i] == 0)
			{
				if (lost[cnt])	cnt++;
				ans[i] = cnt;
				cnt++;
			}	
		}
		for (int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";	
		}
	}
	else
	{
		for (int i = 0; i < even.size(); i++)
		{
			if (i*3+1 > n)	break;
			ans[even[i]] = i*3+1;
			lost[i*3+1] = true;
		}
		for (int i = 0; i < odd.size(); i++)
		{
			if (i*3+2 > n)	break;
			ans[odd[i]] = i*3+2;
			lost[i*3+2] = true;
		}
		int cnt = 1;
		for (int i = 1; i <= n; i++)
		{
			if (ans[i] == 0)
			{
				ans[i] = cnt*3;
				cnt++;
			}
		}
		for (int i = 1; i <= n; i++)
		{
			cout << ans[i] << " ";	
		}
	}
}

Measured memory_bytes: 19572
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

int main(void)
{
	int array[8];
	char str[9];
	int n;
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		long long a = 0, b = 0, sa;
		scanf("%s", str);
		for (int i = 0; i < 8; i++){
			array[i] = str[i] - '0';
		}
		sort(array, array + 8, greater<int>() );
		for (int i = 0; i < 8; i++){
			a *= 10;
			a += array[i];
		}
		sort(array, array + 8);
		for (int i = 0; i < 8; i++){
			b *= 10;
			b += array[i];
		}
		sa = a - b;
		printf("%lld\n", sa);
	}
	
	return (0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin >> a;
	long long arr[a + 1], hero[a];
	for(int i=0; i<a + 1; i++)
		cin >> arr[i];
	for(int i=0; i<a; i++)
		cin >> hero[i];
	long long count = 0;
	for(int i=0; i<a; i++)
	{
		if(arr[i] >= hero[i])
		{ 
			count += hero[i];
			hero[i] = 0;
			arr[i] -= hero[i];
		}
		else
		{
			count += arr[i];
			hero[i] -= arr[i];
			arr[i] = 0;
			if(arr[i+1] >= hero[i])
			{
				count += hero[i];
				arr[i+1] -= hero[i];
			}
			else
			{
				count += arr[i + 1];
				arr[i + 1] = 0;
			}
		}
	}
	printf("%lld\n",count);
	return 0;
}

Measured memory_bytes: 1792
package main

import (
	"fmt"
	"math"
)

func main() {
	MOD := int(math.Pow10(9)) + 7

	var N int
	fmt.Scan(&N)

	S := [2]string{}
	fmt.Scan(&S[0], &S[1])

	var ans int
	if S[0][0] == S[1][0] {
		ans = 3
	} else {
		ans = 6
	}
	for i := 1; i < N; i++ {
		if S[0][i] == S[1][i] {
			if S[0][i-1] == S[1][i-1] {
				ans = (ans * 2) % MOD
			}
		} else {
			if S[0][i] == S[0][i-1] {
				continue
			}
			if S[0][i-1] == S[1][i-1] {
				ans = (ans * 2) % MOD
			} else {
				ans = (ans * 3) % MOD
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1840
a,b,c,x = open(0)
d = 0
x = int(x)
for i in range(int(a)+1):
  for j in range(int(b)+1):
    for k in range(int(c)+1):
      if 500 * i + 100 * j + 50 * k == x:
        d += 1
print(d)

Measured memory_bytes: 2940
N, M, K = map(int, input().split())

mod = 10**9 + 7
table = [1]
for i in range(N*M):
    table.append(table[-1] * (i+1) % mod)


def inv(N):
    return pow(N, mod-2, mod)  # Why mod?


def cmb(n, r):
    return table[n] * inv(table[n-r]*table[r]) % mod


print((M ** 2 * (N ** 3 - N) + N ** 2 * (M ** 3 - M)) // 6 * cmb(M * N - 2, K - 2) % mod)

Measured memory_bytes: 11028
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int num;
    cin >> num;
    vector<int> array(num,0);
    for(int i=0; i<num; i++) {
        int n;
        scanf("%d",&n);
        array[i] = n;
    }

    int ans = 0;

    for(int i=0; i<num; i++) {
        int tmpCounter = 0;
        if(i+ans>=num) {
            break;
        }
        for(int j=i; j<num-1; j++) {
            if(array[j] >= array[j+1]) {
                tmpCounter++;
            }else {
                i = j;
                break;
            }
        }
        ans = max(ans, tmpCounter);
    }
    cout << ans << endl;
}

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

int main()
{
 	ios::sync_with_stdio(0);
 	cin.tie(0);
 	int a[33]={1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
 	int k;
 	cin>>k;
 	
 	cout<<a[k-1]<< endl;
	return 0;
}


Measured memory_bytes: 256
'use strict'
 
const main = (input) => {
  input = input.split('\n');
  const a = input[0].split('')
  const b = input[1].split('')
  const c = input[2].split('')
  
  const n = 'a'
  const s = []
  
  while(true) {
    if (n==='a') {
      s=a
    }else if (n==='b') {
      s=b
    }else{
      s=c
    }
    if(s.length==0) {
      console.log(n.toUpperCase());
      break
    }
    n=s.shift()
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
// Create: 2018-03-24 08:34:33
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
int a[N], b[N];

int main()
{
	cin >> n;
	long long sa = 0, sb = 0, sum = 0;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++) {
		cin >> b[i];
		if(a[i] > b[i]) {
			sum += a[i] - b[i];
		} else {
			sum -= (b[i] - a[i]) / 2;
		}
	}
	if(sum > 0) {
		puts("No");
	} else {
		puts("Yes");
	}
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int main() {
  int n;
  scanf("%d",&n);
  int Rt[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &Rt[i]);
  }

  int maxv = Rt[1] - Rt[0];
  int minv = Rt[0];

  for (int j = 1; j < n; j++) {
    minv = min(minv, Rt[j-1]);
    maxv = max(maxv, Rt[j] - minv);
  }

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

  return 0;
}

Measured memory_bytes: 3976
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  string s;
  cin >> s;
  int ans=0;
  string s1="",s2="";
  for(int i=0; i<s.size(); i++) {
    s1+=s[i];
    if(s1!=s2) {
      s2=s1;
      ans++;
      s1="";
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int MAXH = 5e5+7;
typedef long long ll;
ll a[MAXH];
int h;
void maxHeap(int i) {
    int left = 2*i;
    int right = 2*i + 1;
    if(left > h) return;
    int mid = i;
    int largest_index = mid;
    if(a[left] > a[largest_index]) {
        largest_index = left;
    }
    if(right <= h && a[right] > a[largest_index]) {
        largest_index = right;
    }
    if(largest_index != mid) {
        swap(a[mid], a[largest_index]);
        maxHeap(largest_index);
    }
}
void buildMaxHeap() {
    int i;
    for(i = h/2; i >= 1; i--) {
        maxHeap(i);
    }
}
int main() {
    //freopen("in.txt", "r", stdin);

    scanf("%d", &h);

    for(int i = 1; i <= h; i++) {
        scanf("%lld", &a[i]);
    }
    buildMaxHeap();
    for(int i = 1; i <= h; i++){
        printf(" %lld", a[i]);
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 7092
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
int main() {
#ifdef _DEBUG
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int a,b;
    while(cin>>a>>b){
        int s=a+b-1;
        cout<<a*b-s<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
def calc(x, y):
    return (x + y) / 2


def main():
    N = int(input())
    V = list(map(int, input().split()))

    for _ in range(N - 1):
        V.sort()
        V.append(calc(V.pop(0), V.pop(0)))

    print(V.pop(0))

    return


if __name__ == "__main__":
    main()


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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)
    arr.append(1)
    return set(arr)


def main():
    a, b = map(int, input().split())
    a = factorization(a)
    b = factorization(b)
    l = a & b
    print(len(l))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+8;
int n,m;
int p[maxn];
string s[maxn];
bool ac[maxn];
int panalty[maxn];
int panaltySum = 0;
int acSum = 0;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>p[i]>>s[i];
        if(s[i] == "AC" && !ac[p[i]])
        {
            panaltySum += panalty[p[i]];
            acSum++;
            ac[p[i]] = true;
        }else
        {
            if(!ac[p[i]])
                panalty[p[i]]++;
        }
    }
    cout<<acSum<<" "<<panaltySum<<endl;
}

Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;

inline int num (const std::string& S, int idx){ return S.at(idx) - '0'; }
inline unsigned int bitMask(int i){ return (1 << i); }
inline bool isTrue(unsigned int bit, int i){ return bit & bitMask(i); }

int v[] = {0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main(){
	int K;
	cin >> K;
	cout << v[K] << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	
	int a,b,c,d,max;
	scanf("%d",&a);
	
	b=a/100;
	c=(a-b*100)/10;
	d=a%10;
	
	if(b==c&&c==d) printf("%d\n",a);
	
	if(b>c) printf("%d\n",b*111);
	
	if(b==c&&c>d) printf("%d\n",b*111);
	
	if(c>b) printf("%d\n",(b+1)*111);
	
	if(b==c&&c<d) printf("%d\n",(b+1)*111);
	
	return 0;
}


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

string s;

int main(){
  cin>>s;
  bool N= (string::npos!=s.find('N'));
  bool E= (string::npos!=s.find('E'));
  bool S= (string::npos!=s.find('S'));
  bool W= (string::npos!=s.find('W'));
  if(N^S){
    cout<<"No"<<endl;
  }else if(E^W){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
  }
  return 0;
}


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

a,b = map(int, input().split())

for _ in range(n-1):
    c,d = map(int, input().split())
    i = (a+c-1)//c
    j = (b+d-1)//d
    k = max(i,j)
    a = c*k
    b = d*k
print(a+b)


Measured memory_bytes: 3060
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define fi first
#define se second

int64 XOR(int64 n){
  if (n & 1){
    int64 cnt = (n + 1) / 2;
    if (cnt & 1) return 1;
    else return 0;
  }
  else {
    int64 cnt = n / 2;
    if (cnt & 1) return 1^n;
    else return n;
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int64 a, b; cin >> a >> b;

  if (a == b){
    print(a); return 0;
  }

  print(XOR(a - 1)^XOR(b));


  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <cmath>
#include <functional>
using namespace std;

vector<vector<int>>E;
int solve(int pre, int pos) {
	int cnt = 0;
	bool flag = false;
	for (int i = 0; i < E[pos].size(); i++) {
		if (E[pos][i] == pre)continue;

		int s = solve(pos, E[pos][i]);
		if (s == 1)cnt++;
		else if (s == 2)flag = true;
	}

	if (flag)return 2;
	if (cnt == 1)return 0;
	else if (cnt == 0)return 1;
	else return 2;
}

int main()
{
	int N; cin >> N;
	E.resize(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b; cin >> a >> b;
		--a; --b;
		E[a].push_back(b);
		E[b].push_back(a);
	}

	int s = solve(-1, 0);

	cout << (s ? "First" : "Second") << endl;

    return 0;
}



Measured memory_bytes: 5888
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class QuestionC
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列配列の入力
            string[] inputStrArray = Console.ReadLine().Split(' ');

            decimal a = decimal.Parse(inputStrArray[0]);
            decimal b = decimal.Parse(inputStrArray[1]);
            Console.WriteLine(Decimal.Floor(a * b));

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27500
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

//#include <map>
//#include <algorithm>

using namespace std;

int main(void)
{
	string str;
	getline(cin, str);

	vector<string> vStr;

	while (str.find(' ') != -1)
	{
		vStr.push_back(str.substr(0, str.find(' ')));
		str.erase(0, str.find(' ') + 1);
	}
	vStr.push_back(str);

	int a, b, c;
	a = stoi(vStr.at(0));
	b = stoi(vStr.at(1));
	c = stoi(vStr.at(2));

	if (a < b && b < c)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;

	}
	return 0;
}

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

const ll MOD = 1000000007;

int main(){
  string S;
  cin >> S;
  int n = S.length();
  
  vector<ll> AB(n,0);
  vector<ll> BC(n,0);
  // 3^n のテーブルを作っておく
  vector<ll> n3(n+1);
  n3[0] = 1;
  REP(i,n) n3[i+1] = n3[i]*3 % MOD;

  // B の位置を決めて、それより前にある A の位置も決めた場合に、
  // B よりも前の部分での場合の数
  ll a = 0;
  ll h = 0;
  REP(i,n){
    if (S[i]=='A') a++;
    else if (S[i]=='B')
      AB[i] = ((a * n3[h]) % MOD + (h * n3[h-1]) % MOD) % MOD;
    else if (S[i]=='?') {
      AB[i] = ((a * n3[h]) % MOD + (h * n3[h-1]) % MOD) % MOD;
      h++;
    }
//    cout << AB[i] << " " << a << " " << h << endl;
  }
  
  // B の位置を決めて、それより後ろある C の位置も決めた場合に、
  // B よりも後ろ部分での場合の数
  ll c = 0;
  h = 0;
  REP(i,n){
    if (S[n-i-1]=='C') c++;
    else if (S[n-i-1]=='B')
      BC[n-1-i] = ((c * n3[h]) % MOD + (h * n3[h-1]) % MOD) % MOD;
    else if (S[n-i-1]=='?') {
      BC[n-1-i] = ((c * n3[h]) % MOD + (h * n3[h-1]) % MOD) % MOD;
      h++;
    }
  }
  ll ans = 0;
  REP(i,n){
//    cout << AB[i] << " " << BC[i] << endl;
    if (S[i]=='B' || S[i]=='?') {
      ans = (ans + AB[i] * BC[i]) % MOD;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 2816
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 9;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
template<typename T, typename F> ll sum(T begin, T end, F func) {return accumulate(begin, end, 0ll, func);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

using Pair = pair<ll, ll>;

signed main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> a(n), b(n), c(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];
  REP(i, n) cin >> c[i];
  sort(all(a));
  sort(all(b));
  sort(all(c));
  ll ans = 0;
  REP(i, n) {
    ll cnt_a = lower_bound(all(a), b[i]) - a.begin();
    ll cnt_c = c.end() - upper_bound(all(c), b[i]);
    ans += cnt_a * cnt_c;
  }         
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2688
def main(argv)
  n = gets.chomp.to_i

  k = -1
  s = 0
  n.times do |i|
    s += i + 1
    if s >= n then
      k = i + 1
      break
    end
  end
  
  t = n
  k.downto(1).each do |i|
    if t >= i then
      puts i.to_s
      t -= i
    end
  end
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1788
#include <cstdio>
#include <algorithm>

#define MAX 100000

typedef long long ll;
int N, p[MAX + 1];

ll solve(int i){
    ll res = 1145141919810;
    if(i == N){
        if(p[i] == i){
            std::swap(p[i], p[i - 1]);
            return solve(1) + 1;
        }
        return 0;
    }

    if(p[i] == i){
        std::swap(p[i], p[i + 1]);
        res = std::min(res, solve(i + 1) + 1);
    }else{
        res = std::min(res, solve(i + 1));
    }

    return res;
}

int main(){
    scanf("%d", &N);

    bool f = true;
    for(int i = 1; i <= N; i++){
        scanf("%d", &p[i]);

        if(p[i] == i){
            f = false;
        }
    }

    if(f){
        printf("0\n");
        return 0;
    }

    printf("%lld\n", solve(1));

    return 0;
}


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

class Program
{
    static void Main(string[] args)
    {
        var hp = long.Parse(Console.ReadLine());
        var finish = false;

        long attachCount = 1;
        long monsterNum = 1;

        while (!finish)
        {
            if (hp > 1)
            {
                hp = (long)Math.Truncate((double)hp / 2);
                attachCount = attachCount + monsterNum * 2;
                monsterNum = monsterNum * 2;
            }
            else
            {
                finish = true;
            }
        }

        Console.WriteLine(attachCount);
        Console.ReadLine();
    }
}


Measured memory_bytes: 13140
import collections
 
def LI():
	return [ int(s) for s in input().split() ]
 
N = int(input())
A = LI()
 
c_counter = [0]*(2*(10**5))
 
for a in A:
  c_counter[a]+=1
 
total = 0
total_dict = [0]*(2*(10**5))
 
for a in range(len(c_counter)):
  v = c_counter[a]
  if v >= 2:
    comb = v*(v-1)//2
    total_dict[a] = comb
    total += comb
 
for a in A:
  if total == 0:
    print(0)
  else:
    print(total - total_dict[a] + (c_counter[a]-1)*(c_counter[a]-2)//2)

Measured memory_bytes: 26780
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

int main() {
  ll n;
  cin >> n;
  string a = "No";
  for (ll i = 1; i <= 9; i++) {
    for (ll j = 1; j <= 9; j++) {
      if (n == i * j) {
        a = "Yes";
        break;
      }
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
const int MOD = 1e9+7; const int MAX = 200020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 1e18;


void solve() {
	int D, N; cin >> D >> N;
	if (D == 0) {
		vector<int>d;
		FOR(i, 1, 100)d.push_back(i);
		FOR(i, 101, 200)d.push_back(i);

		print(d[N - 1]);
	}
	else if (D == 1) {
		vector<int>d;
		for (int i = 100; i < 10000; i += 100)d.push_back(i);
		for (int i = 10100; i < 20000; i += 100)d.push_back(i);
		print(d[N - 1]);
	}
	else {
		vector<int>d;
		for (int i = 10000; i < 10000 * 100; i += 10000)d.push_back(i);
		for (int i = 10000*100+10000; i < 20000 * 100; i += 10000)d.push_back(i);
		print(d[N - 1]);
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a>b){
int tmp=a;
a=b;
b=tmp;
}
for(int i=a;i<=b;++i){
if((i*b*a)&1){
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> mochis(n);
	for(int i=0;i<n;i++)
	{
		cin>>mochis[i];
	}
	sort(mochis.begin(),mochis.end());
	int max=0;
	int f=0;
	for(int i=0;i<n;i++)
	{
		if(mochis[i]!=f)
		{
			max++;
			f=mochis[i];
		}
	}
	cout<<max;
	return 0;	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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; }

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

const ll INF = 1LL << 60;

int main(){
  int n,k; cin >> n >> k;
  ll ans = 0LL;
  for (int b = 1; b <= n; b++) {
    if(b-k <= 0) continue;
    ans += (b-k)*(n/b);
    if(k != 0) ans += max(n%b-(k-1),0);
    else ans += n%b;
  }
  std::cout << ans << '\n';
}


Measured memory_bytes: 256
n,m=map(int,input().split())
x=set([int(input()) for _ in range(m)])
f=[0]*(n+1)
f[0]=1
for i in range(1,n+1):
  f[i]=f[i-1]+f[i-2]
  if i in x:
    f[i]=0
print(f[n]%(10**9+7))

Measured memory_bytes: 460020
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define black_tree tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define pair_black_tree tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update>
#define gp __gnu_pbds
#define INF 1000000000
#define MOD 1000000007
#define MAX 1000001
#define endl '\n'
#define ll long long
#define ld long double
#define lli long long int
#define ull unsigned long long
#define ulli unsigned long long int
#define pb push_back
#define pf push_front
#define ook order_of_key
#define fbo find_by_order
#define np next_permutation
#define mp make_pair
#define eb emplace_back
#define mae max_element
#define mie min_element
#define lb lower_bound 
#define ub upper_bound
#define bs binary_search
#define ff first
#define ss second
using namespace std;
using namespace gp;
ll a,b,c,d;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b>>c>>d;
	cout<<max(max(a*c,a*d),max(b*c,b*d));
}

Measured memory_bytes: 3648