akhauriyash/Code-Regression huggingface dataset:
import java.util.HashMap;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long mod = 1000000007l;
    long answer = 1l;
    int zeroCnt = 0;
    Tupple zeroTupple = new Tupple();
    HashMap<String, Tupple> map = new HashMap<>();
    long[] p2table = new long[n + 1];
    p2table[0] = 1;
    for(int i = 1; i <= n; i++){
      p2table[i] = p2table[i-1] * 2 % mod;
    }
    for(int i = 0; i < n; i++){
      long a = sc.nextLong();
      long b = sc.nextLong();
      if(a == 0 && b == 0){
        zeroCnt++;
        continue;
      }
      if(a == 0) {
        zeroTupple.a++;
        continue;
      }
      if(b == 0) {
        zeroTupple.b++;
        continue;
      }
      if(b < 0){
        a = -a;
        b = -b;
      }
      long gcd = gcd(Math.abs(a), Math.abs(b));
      a /= gcd;
      b /= gcd;
      String key;
      if(a > 0){
        key = a + "/" + b;
      } else {
        key = b + "/" + (-a);
      }
      if(map.containsKey(key)){
        Tupple t = map.get(key);
        if(a > 0){
          t.a++;
        } else {
          t.b++;
        }
      } else {
        Tupple t = new Tupple();
        if(a > 0){
          t.a++;
        } else {
          t.b++;
        }
        map.put(key, t);
      }
    }
    map.put("0", zeroTupple);
    for(Tupple t : map.values()){
      long ans = p2table[t.a] + p2table[t.b] - 1;
      answer = answer * ans % mod;
    }
    answer = (answer + zeroCnt + mod - 1) % mod;
    System.out.println(answer);
  }

  static long gcd(long a, long b){
    if(b == 0){
      return a;
    }
    return gcd(b, a % b);
  }
  static class Tupple {
    int a = 0;
    int b = 0;
  }
}

Measured memory_bytes: 97232
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    cin >> n >> x;
    vector<int> m;
    int s;
    int sum=0;
    int Min=1000;
    for(int i=0;i<n;i++){
        cin >> s;
        m.push_back(s);
        sum+=s;
        Min=min(Min, s);
    }
    x-=sum;
    int count=n;
    while(x-Min>=0){
        x-=Min;
        ++count;
    }
    cout << count<< endl;
    return 0;
}

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using Int = long long;
int W, H;
vector<Int> p, q;
int main() {
    cin >> W >> H;
    p.resize(W), q.resize(H);
    rep(i, W) cin >> p[i];
    rep(i, H) cin >> q[i];
    sort(all(q));
    sort(all(p));
    Int ans = 0;
    int i = 0, j = 0;
    while (i < H || j < W) {
        if (i == H) {
            ans += p[j];
            j++;
        } else if (j == W) {
            ans += q[i];
            i++;
        } else {
            if (q[i] < p[j]) {
                ans += (W - j + 1) * q[i];
                i++;
            } else {
                ans += (H - i + 1) * p[j];
                j++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
typedef long long ll;
int arr[105];
int main()
{
	// freopen("AGC027-A.in", "r", stdin);
	int n, x, ans = 0;
	scanf("%d%d", &n, &x);
	for (int i = 0; i < n; i++)
		scanf("%d", arr + i);
	std::sort(arr, arr + n);
	for (int i = 0; i < n; i++)
	{
		if (x < arr[i])
			break;
		x -= arr[i];
		ans++;
	}
	if (ans == n)
		ans -= x != 0;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
static const double pi = 3.141592653589793;




int main(){
    ll N;
    cin>>N;
    vector<ll> Pr(N+1, 0);
    for(ll i=2; i<=N; i++){
        ll I=i;
        for(ll j=2; j<=i; j++){
            if(I<j)break;
            while(I%j==0){
                Pr[j]++;
                I/=j;
            }
        }
    }
    ll Three, Five, Fifte, Twent, Sevf;
    Three=0;
    Five=0;
    Fifte=0;
    Twent=0;
    Sevf=0;
    rep(i, N+1){
        if(Pr[i]>=2)Three++;
        if(Pr[i]>=4)Five++;
        if(Pr[i]>=14)Fifte++;
        if(Pr[i]>=24)Twent++;
        if(Pr[i]>=74)Sevf++;
      	//cout<<Pr[i]<<endl;
    }
    ll Ans=0;
    Ans+=Five*(Five-1)/2*(Three-2);
    Ans+=Fifte*(Five-1);
    Ans+=Twent*(Three-1);
    Ans+=Sevf;
    cout<<Ans<<endl;
}
    

Measured memory_bytes: 256
#include <cstdio>
using namespace std;

int l[10], v[2], sum;

int main(){
	while (true) {
		sum = 0;
		for (int i = 0; i < 10; i++) {
			if (scanf("%d,", &l[i]) == EOF) {
				return 0;
			}
			sum += l[i];
		}
		scanf("%d,%d,", &v[0], &v[1]);
		double t = 1.0 * sum / (v[0] + v[1]);
		t *= v[0];
		double loc = 0;
		for (int i = 0; i < 10; i++) {
			loc += l[i];
			if (t <= loc) {
				printf("%d\n", i+1);
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 2548
H,W = map(int,input().split())
ans = 0
if H == 1 or W == 1:
    print(1)
    exit()
if H%2 == 0 and W%2 == 0:
    ans = H*W//2
elif H%2 == 0 and W%2 == 1:
    ans = H*W//2
elif H%2 ==1 and W%2 == 0:
    ans = H*W//2
else:
    ans = H*W//2 + 1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string s;

inline int read(){
	int s=0,t=1;
	char c=getchar();
	while((c>'9'||c<'0')&&c!='-')c=getchar();
   	if(c=='-')t=-1,c=getchar();
   	while(c>='0'&&c<='9')s=s*10+c-'0',c=getchar();
   	return s*t;
}

int main(void){
	cin>>s;
	if(s=="Sunny")cout<<"Cloudy";
	if(s=="Rainy")cout<<"Sunny";
	if(s=="Cloudy")cout<<"Rainy";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll ans=0,n,arr[300005],i,t=0;
cin>>n;
for(i=0;i<n;i++)cin>>arr[i];
t=arr[0];
for(i=1;i<n;i++){
if(arr[i]<t){
ans+=t-arr[i];
}
else
t=arr[i];}
cout<<ans;}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pcase cout<<"Case "<<++cs<<":"
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define mp make_pair
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC() ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007


int main()
{
    int i = 0, j = 0, cs = 0, in;
    int n; cin>>n;
    string s; cin>>s;
    for(i = 0; i < s.size(); i++){
        char c = (s[i]+n);
        if(c > 90) c -= 26;
        cout << c;
    }
    cout << endl;
    return 0;
}


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

using namespace std;

int a[111111];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	sort(a, a + n);
	auto i = lower_bound(a, a + n, a[n - 1] / 2) - a;
	if (i&&a[n - 1] - a[i - 1] * 2 <= a[i] * 2 - a[n - 1])
		i--;
	cout << a[n - 1] << ' ' << a[i] << endl;
	return 0;
}


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

int main() {
  int N;
  cin>>N;
  string s,t;
  cin>>s>>t;
  reverse(s.begin(),s.end());
  for(int i=N;i<=2*N;i++){
    string S=s.substr(0,2*N-i);
    reverse(S.begin(),S.end());
    if(S==t.substr(0,2*N-i)){cout<<i<<endl;return 0;}
  }
  return 0;
}

Measured memory_bytes: 3632
N, M = gets.split.map(&:to_i)
As = gets.split.map(&:to_i).sort
As_max = As.last
As_min = As.first

$rui = Array.new(N + 1, 0)
N.times do |i|
  $rui[i+1] += $rui[i] + As[i]
end

$rui_cnt = Array.new(As_max + 1, 0)
As.each do |n|
  $rui_cnt[n] += 1
end
As_max.times do |i|
  $rui_cnt[i+1] += $rui_cnt[i]
end

def f(x)
  cnt = 0
  N.times do |i|
    t = x - As[i]
    if t > As_max
      next
    elsif t < As_min
      cnt += N
    else
      cnt += N - $rui_cnt[t-1]
    end
  end
  cnt
end

def g(x)
  cnt = 0
  tot = 0
  N.times do |i|
    t = x - As[i]
    if t > As_max
      next
    elsif t < As_min
      cnt += N
      tot += $rui[N] + As[i] * N
    else
      aa = N - $rui_cnt[t-1]
      cnt += aa
      tot += $rui[N] - $rui[$rui_cnt[t-1]] + As[i] * aa
    end
  end
  tot -= (cnt - M) * x if cnt > M
  tot
end

max = 2 * 10 ** 5 + 1
min = 0
while min + 1 < max
  mid = (max + min) / 2
  if f(mid) >= M
    min = mid
  else
    max = mid
  end
end

puts g(min)

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

int main() {
  int N;
  cin >> N;
  vector<vector<int>> V(N, vector<int>(3)), DP(N, vector<int>(3));
  for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) cin >> V.at(i).at(j);
  DP.at(0) = V.at(0);
  for (int i = 1; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      DP.at(i).at(0) = V.at(i).at(0) + max(DP.at(i - 1).at(1), DP.at(i - 1).at(2));
      DP.at(i).at(1) = V.at(i).at(1) + max(DP.at(i - 1).at(0), DP.at(i - 1).at(2));
      DP.at(i).at(2) = V.at(i).at(2) + max(DP.at(i - 1).at(0), DP.at(i - 1).at(1));
    }
  }
  cout << max({DP.at(N - 1).at(0), DP.at(N - 1).at(1), DP.at(N - 1).at(2)}) << "\n";
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,j,k,a,b,c,ans,f1,f2,f3;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&n);
    if(n%2==0)
    printf("%lld",a-b);
    else
        printf("%lld",b-a);


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <utility>
using namespace std;

typedef pair<double, double> VEC;

pair<double, double> projection(VEC from, VEC to) {
    double size = (from.first * to.first + from.second * to.second) / (pow(to.first, 2) + pow(to.second, 2));
    VEC res = make_pair(size * to.first, size * to.second);
    return res;
}

int main() {
    double x1, y1, x2, y2, xq, yq;
    while (scanf("%lf,%lf,%lf,%lf,%lf,%lf", &x1, &y1, &x2, &y2, &xq, &yq) != EOF) {
        VEC line = make_pair(x2 - x1, y2 - y1);
        VEC PQ = make_pair(xq - x1, yq - y1);
        VEC proj = projection(PQ, line);
        printf("%.6f %.6f\n", x1 + 2 * proj.first - PQ.first, y1 + 2 * proj.second - PQ.second);
    }
}

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

int n;
int dp[31][50];
int f[50][30];
int co[50][50];
vector<int> anss;

int dfs(int k){
  for(int i = 0; i < n; i++){
    if(f[i][k-1] == 0) continue;
    for(int j = 0; j < n ; j++){
      if(f[j][k-1] == 0) continue;
      for(int m = 0; m < n; m++){
        if(co[i][m] < co[j][m])co[i][m] = co[j][m];
      }
    }
  }

  for(int i = 0;i < n ; i++){
    int count = 0;
    for(int j = 0; j < n; j++){
      if(co[i][j] == 1) count++;
    }
    if(count == n) return k;
  }

  if(k < 30) return dfs(k+1);
  else return 0;
}

int main(){
  while(cin >> n && n != 0){
    // for(int i = 0; i < 31; i++){
    //   for(int j = 0; j < 50; j++){
    //     if(i == 0) dp[i][j] = 1;
    //     else dp[i][j] = 0;
    //   }
    // }
    for(int i = 0; i < 50; i++){
      for(int j = 0; j < 30; j++){
        f[i][j] = 0;
      }
    }
    for(int i = 0; i < 50; i++){
      for(int j = 0; j < 50; j++){
        if(i == j) co[i][j] = 1;
        else co[i][j] = 0;
      }
    }
    for(int i = 0 ; i < n; i++){
      int k;
      cin >> k;
      for(int j = 0; j < k; j++){
        int d;
        cin >> d;
        f[i][d-1] = 1;
      }
    }
    int ans = dfs(1);
    anss.push_back(ans);
    if( ans == 0 ) cout << -1 << endl;
    else cout << ans << endl;
  }
  // for(int i = 0; i < anss.size(); i++ ){
  //   cout << anss[i] << endl;
  // }
}



Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;



int main() {
	// A,C,G,T
	// A <--> T, C <--> G

	char b;

	cin >> b;

	char ans;
	if (b == 'A') {
		ans = 'T';
	}
	else if (b == 'T') {
		ans = 'A';

	}
	else if (b == 'G') {
		ans = 'C';
	}
	else {
		ans = 'G';
	}

	cout << ans << endl;


}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>


using namespace std;

bool isTri(int a, int b, int c){
  if(max(a, b) < c){
    if(pow(c, 2.0) == pow(a, 2.0) + pow(b, 2.0)){
      return true;
    }
  }else{
    if(pow(max(a, b), 2.0) == pow(min(a, b), 2.0) + pow(c, 2.0)){
      return true;
    }
  }
  return false;
}


int main(){
  int a, b, c;
  int num;
  cin >> num;
  
  while(cin >> a >> b >> c){
    if(isTri(a, b, c)){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
  }
    
}

Measured memory_bytes: 1152
def num_patty(n, x)
  np = Array.new(n + 1)
  np[0] = 1
  (1..n).each do |i|
    np[i] = 2 * np[i - 1] + 1
  end

  w = Array.new(n + 1)
  w[0] = 1
  (1..n).each do |i|
    w[i] = 2 * w[i - 1] + 3
  end

  memo = {}

  num_p = -> n, x {
    if n == 0
      return x >= 1 ? 1 : 0
    end

    memo[[n, x]] ||=
      if x <= 1
        0
      elsif x <= w[n - 1] + 1
        num_p.call(n - 1, x - 1)
      elsif x <= w[n - 1] + 2
        num_p.call(n - 1, x - 1) + 1
      elsif x <= 2 * w[n - 1] + 2
        np[n - 1] + 1 + num_p.call(n - 1, x - w[n - 1] - 2)
      else
        np[n]
      end
  }

  num_p.call(n, x)
end

n, x = gets.split.map(&:to_i)
puts num_patty(n, x)


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

using namespace std;

int main() {

	int K, N;

	cin >> K >> N;

	vector<int> A(N);
	vector<int> dif(N);

	for(int i = 0; i < N; ++i) cin >> A[i];
	for(int i = 0; i <= N - 1; ++i) {
		if(i == N - 1)
			dif[N - 1] = K - A[N - 1] + A[0];
		else
			dif[i] = A[i + 1] - A[i];
	}

	vector<int>::iterator iter = max_element(dif.begin(), dif.end());

	size_t maxIndex = distance(dif.begin(), iter);

	int sum = accumulate(dif.begin(), dif.end(), 0);

	cout << sum - dif[maxIndex] << endl;

	return 0;
}

Measured memory_bytes: 1792
import sys
input = sys.stdin.readline


def read():
    H1, M1, H2, M2, K = map(int, input().strip().split())
    return H1, M1, H2, M2, K


def solve(H1, M1, H2, M2, K):
    m1 = H1 * 60 + M1
    m2 = H2 * 60 + M2
    return m2 - m1 - K


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


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

int calc(vector<vector<int>> &a){
	int i1, i2, j1, j2, k, l, ans = 0;
	for(i1 = 0; i1 < a.size(); i1++){
		for(i2 = i1; i2 < a.size(); i2++){
			for(j1 = 0; j1 < a[0].size(); j1++){
				for(j2 = j1; j2 < a[0].size(); j2++){
					int now = 0;
					for(k = i1; k <= i2; k++){
						for(l = j1; l <= j2; l++){
							now += a[k][l];
						}
					}
					ans += now % 2;
				}
			}
		}
	}
	return ans;
}

vector<vector<int>> make(int A, int B){
	int i, j;
	vector<vector<int>> ans(A, vector<int>(B, -1));
/*	if(A == 1){
		for(j = 0; j < B; j++){
			ans[0][j] = 1 - j % 2;
		}
		return ans;
	}
	if(B == 1){
		for(i = 0; i < A; i++){
			ans[i][0] = 1 - i % 2;
		}
		return ans;
	}
*/	if(A * B == 0){
		return ans;
	}
	vector<vector<int>> res = make(A / 2, B / 2);
/*	for(i = 0; i < A / 2; i++){
		for(j = 0; j < B / 2; j++){
			printf("%d", res[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	for(i = 0; i < A; i++){
		ans[i][B / 2] = 0;
	}
	for(j = 0; j < B; j++){
		ans[A / 2][j] = 0;
	}
	ans[A / 2][B / 2] = 1;
/*	for(i = 0; i < A; i++){
		for(j = 0; j < B; j++){
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	for(i = 0; i < A / 2; i++){
		for(j = 0; j < B / 2; j++){
			ans[i][j] = 1 - res[i][j];
			ans[A / 2 + 1 + i][j] = 1 - res[i][j];
			ans[i][B / 2 + 1 + j] = 1 - res[i][j];
			ans[A / 2 + 1 + i][B / 2 + 1 + j] = 1 - res[i][j];
		}
	}
/*	for(i = 0; i < A; i++){
		for(j = 0; j < B; j++){
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	return ans;
}

int main(){
	int N, M, i, j;
	scanf("%d%d", &N, &M);
	vector<vector<int>> a((1 << N) - 1, vector<int>((1 << M) - 1, -1));
/*	for(i = 0; i < (1 << N) - 1; i++){
		for(j = 0; j < (1 << M) - 1; j++){
			a[i][j] = 1 - (i + j) % 2;
			scanf("%1d", &a[i][j]);
		}
	}
*/	a = make((1 << N) - 1, (1 << M) - 1);
//	printf("score = %d\n", calc(a));
//	return 0;
	for(i = 0; i < (1 << N) - 1; i++){
		for(j = 0; j < (1 << M) - 1; j++){
			printf("%d", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

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

using namespace std;

int n;
map<pair<int,int>,int> dp;
vector<int> prep(){
    set<int> st;
    st.insert(1);
    for(int i = 6 ; i <= n ; i *= 6){
        st.insert(i);
    }
    for(int i = 9 ; i <= n ; i *= 9){
        st.insert(i);
    }
    vector<int> v(st.begin(),st.end());
    sort(v.rbegin(),v.rend());
    return v;
}

vector<int> v;

int fun(int idx,int m){
    if(!m){
        return 0;
    }
    int &ret = dp[{idx,m}];
    if(ret){
        return ret;
    }
    ret = INT_MAX;
    //cout << idx << " " << m << endl;
    for(int i = idx ; i < v.size() ; i ++){
        if(m >= v[i]){
            //cout << v[i] << endl;
            ret = min(ret,fun(i,m - v[i]) + 1);
        }
    }
    return ret;
}

int main()
{
    cin >> n;
    v = prep();
    cout << fun(0,n) << endl;
    return 0;
}


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

int main() {
    // ll A;
    // long double B;
    // // cin >> A >> B;
    // // cin >> A;
    // // cin >> B;

    // if (A == 0 || B == 0.0) {
    //     cout << 0 << endl;
    //     return 0;
    // }

    // // ll A, B;
    // // double b;
    // // cin >> A >> b;
    // // B = (ll)(b * 100.0);
    // // cout << A * B / 100 << endl;

    // double ansd = (double)A * B;
    // // ll ansl = (ll)floor(ansd);
    // ll ansl = (ll)ansd;

    // // cout << (ll)floor((double)A * B) << endl;
    // cout << ansl << endl;

    // double a, b;
    // cin >> a >> b;
    // int ans = a * b;
    // cout << ans << endl;
 
	// int A; cin >> A;
	// long double B; cin >> B;
	// cout << (int)(A*B) << endl;
	// return 0;

    long long a;
    long double b;
    cin >> a >> b;
    long long c = a * b;
    cout << c << endl;
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vl(p) vector<p>
#define W while
#define For(i,s,x) for(i=s;i<x;i++)
#define Fore(i,s,x) For(i,s,x+1)
#define FoR(i,s,x) for(i=s-1;i>=x;i--)
#define ForE(i,s,x) FoR(i,s+1,x)
#define all(v) v.begin(),v.end()
#define pb push_back
#define in insert
#define sz size()
#define F first
#define S second
#define nl cout<<"\n"
#define pr(a) cout<<a<<" "
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define pr3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
#define mod 1000000007
#define MAX 200005


int main() {
    FASTIO;
    ll i, j, k, l;
    string s, t;
    cin>>s>>t;
    ll S=s.sz, T=t.sz;
    ll dp[S+1][T+1]={};
    Fore(i,1,S) {
        Fore(j,1,T) {
            if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    ll index=dp[S][T];
    char ans[index+1];
    ans[index]='\0';
    i=S; j=T;
    while(i>0&&j>0) {
        if(s[i-1]==t[j-1]) ans[--index]=s[i-1], i--, j--;
        else if(dp[i-1][j]>dp[i][j-1]) i--;
        else j--;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 73964
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#include<iomanip>
#include<set>
#include<string>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
//const int inf = 1e9 + 7;

int main() {
    string s; cin >> s;
    int table[26] = {0};
    rep(i, s.size()) table[s[i] - 'A']++;
    int flg = 0;
    if (table[10] != 1) flg = 1;
    if (table[7] != 1) flg = 1; //h
    if (table[8] != 1) flg = 1; //i
    if (table[1] != 1) flg = 1; //b
    if (table[17] != 1) flg = 1;
    table[0] = 0; table[1] = 0; table[7] = 0; table[8] = 0; table[10] = 0; table[17] = 0;
    rep(i, 26) if (table[i] != 0) flg = 1;
    if (flg == 0) {
        int cnt = 0; //a
        int cntt = 0;
        int cnttt = 0;
        rep(i, s.size()) {
            if (s[i] == 'A') cnt++;
            if (cnt <= 1 && s[i] == 'K') flg = 1;
            if (flg == 1 && s[i] == 'A') flg = -1;
            if (flg == 1 && s[i] == 'I') flg = 2;
            if (flg == 2 && s[i] == 'A') flg = -1;
            if (flg == 2 && s[i] == 'H') flg = 3;
            if (flg == 3 && s[i] == 'A') cntt++;
            if (cntt <= 1 && flg == 3 && s[i] == 'B') flg = 4;
            if (flg == 4 && s[i] == 'A') cnttt++;
            if (cnttt <= 1 && flg == 4 && s[i] == 'R') flg = 5;
            if (cnt >= 5) flg = -1;
        }
        if (flg == 5) {cout << "YES" << endl; return 0;}
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
  int a,b,c,k;
  cin>>a>>b>>c>>k;
  int ans=a+b+c;
  for(int i=0;i<k;i++){
    int n=max(a,max(b,c));
    ans+=n;
    if(a==n)
      a*=2;
    else if(b==n)
      b*=2;
    else
      c*=2;
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
from collections import deque

# input
n, m = map(int, input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

if m == 1:
    print('IMPOSSIBLE')
    exit()

to = [[] for _ in range(n+1)]
for i in range(m):
    to[a[i]].append(b[i])
    to[b[i]].append(a[i])
#print('to =', to)

# BFS
inf = 200200
dist = [inf for _ in range(n+1)]
q = deque()
q.append(1)
dist[1] = 0 

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] == inf:
            dist[u] = dist[v]+1
            q.append(u)

if dist[n] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 47060
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,a[100000],s=0,x=0;
int32_t main(){
CODE_START;
cin >> n;
for(ll i=0;i<n;i++)
{
    cin >> a[i];
    s+=a[i];
}
if(s%n==0){
x=s/n;
s=0;
for(ll i=0;i<n;i++)
{
    s+=abs(a[i]-x)*abs(a[i]-x);
}
cout << s;
}else {
ll s1=0,s2=0;
x=s/n;
s=0;
for(ll i=0;i<n;i++)
{
    s+=abs(a[i]-x)*abs(a[i]-x);
}
x++;
for(ll i=0;i<n;i++)
{
    s1+=abs(a[i]-x)*abs(a[i]-x);
}
x-=2;
for(ll i=0;i<n;i++)
{
    s2+=abs(a[i]-x)*abs(a[i]-x);
}
cout << min(s,min(s1,s2));
}
}




Measured memory_bytes: 256
line = gets.chomp.split
stack = []
 
line.each do |x|
  case x
  when '+', '-', '*'
    b = stack.pop
    a = stack.pop
    case x
    when '+'
      stack.push(a + b)
    when '-'
      stack.push(a - b)
    when '*'
      stack.push(a * b)
 
    end
  else
    stack.push(x.to_i)
  end
end
 
puts stack

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

using namespace std;

int main() {
	int n, k, i = 0, j = 0;
	cin >> n >> k;
	vector<int> w(n, 0);
	vector<int> track(k, 0);
	vector<int> t_init(track);
	int P;
	int sum_w = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> w[i];
		sum_w += w[i];
	}
	P = sum_w / k - 1;
	while (i != w.size())
	{
		i = 0;
		j = 0;
		P++;
		track = t_init;
		while (i != w.size())
		{
			if (track[j] + w[i] > P)
			{
				if (++j == k) break;
			}
			else
			{
				track[j] += w[i++];
			}
		}

	}
	cout << P << endl;
	return 0;
}


Measured memory_bytes: 3860
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    string s;
    vector<int> w;
    vector<int> b;
    vector<int> turn;

    cin >> n;
    cin >> s;

    w.push_back(0);
    b.push_back(0);
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '#') {
            w.push_back(w[i]);
            b.push_back(b[i]+1);
        }else{
            w.push_back(w[i]+1);
            b.push_back(b[i]);
        }
    }
    if(w[n] == 0 || b[n] == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    /*w.erase(w.begin());
    b.erase(b.begin());*/

    for(int i=1;i<=n;i++){
        turn.push_back(b[i-1]+(w[n]-w[i]));
    }
    cout << *min_element(turn.begin(),turn.end()) << endl;
    return 0;
}

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

using namespace std;
#define ll long long
#define ld long double
const int N = 2e5 + 5;
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int x, y;
    cin >> x >> y;
    for(int i = 0 ; i <= x ; i++) {
        if (i * 2 + (x - i) * 4 == y) return cout << "Yes",0;
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 3692
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int b = input.nextInt();
        System.out.println(String.format("%d %d %f", (int)(a / b), a % b, (double)a / b));
    }
}



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

namespace ConsoleApplication2
{
    class Program
    {

        static void Main(string[] args)
        {
            string data = Console.ReadLine();
            StringBuilder sb = new StringBuilder();
            foreach (var ch in data)
            {
                if ('a' <= ch && ch <= 'z')
                    sb.Append(ch.ToString().ToUpper());
                else if ('A' <= ch && ch <= 'Z')
                    sb.Append(ch.ToString().ToLower());
                else
                    sb.Append(ch.ToString());
            }
            Console.WriteLine(sb.ToString().Trim());
        }
    }
}

Measured memory_bytes: 9152
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
int n;

int main(){
  auto dmy = scanf("%d", &n);
  vector<ll> data(n);
  for(int i=0; i<n; i++) dmy = scanf("%lld", &data[i]);
  
  multiset<ll> s;
  for(int i=n-1; i>=0; i--){
    auto iter = s.insert(data[i]);
    if(i==n-1) continue;
    auto last = s.end();
    last--;
    if(iter != last){
      iter++;
      s.erase(iter);
    }
  }
  printf("%d", s.size());
  return 0;
}

Measured memory_bytes: 5760
#include "bits/stdc++.h"
using namespace std;
#define dbg(var) cout<<#var<<"="<<var<<" "
#define nl cout<<"\n"
#define fr(i,n) for(int i=0;i<n;i++)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define fa(v) for(auto &i:v)
#define all(v) v.begin(),v.end()
#define sz(v) (int)(v.size())
#define int long long
const int mod = 1e9 + 7;
int fpow(int a, int b){
	int res=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
	return res;
}
const int MX=1e6+10;
int mult(int a,int b){return (1ll*a*b)%mod;}
int fact[MX],inv[MX],invfact[MX];
void init_INV(){
	fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1;
    for (int i = 2; i < MX; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(inv[mod % i], mod - mod / i);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
}
int ncr(int n,int r){
	if(n < r) return 0;
	n = fact[n] * invfact[n - r]  % mod;
	n = n * invfact[r] % mod;
	return n;
}
int32_t main()
{
	init_INV();
	int n;cin >> n;
	int ans = 0;
	for(int len = 1; len <= n; len++){
		ans += ncr(n - len*3 + len - 1, len - 1);
		ans %= mod;
	}
    cout << ans ;	
}

Measured memory_bytes: 27056
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n) cin>>a[i];
  int start=1;
  int end=1000000001;
  int ans=1000000000;
  while(start!=end){
    int mid=(start+end)/2;
    int count=0;
    rep(i,n){
      if(a[i]%mid==0) count+=a[i]/mid;
      else count+=a[i]/mid+1;
      count--;
    }
    if(count>k) start=mid+1;
    else {
      ans=min(mid,ans);
      end=mid;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3972
#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define all(v) (v).begin(),(v).end()
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using int32 = int32_t; using str = string; using cstr = const str;
using ll = long long; using ull = unsigned long long; using cint = const int; using cll = const ll;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using psl = pair<string, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7;
static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
#define FASTCIN() cin.tie(0);ios::sync_with_stdio(false);
#ifdef IMPORT_SAMPLE
#define DEBUG_IMPORT(file) vs args(argv, argv+argc);str sample = make_sample(args, file);ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#else
#define DEBUG_IMPORT(file)
#endif
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}


struct CumSum {
    vi csum;
    int N;
    CumSum(IN(vi) A) {
        self.N = A.size();
        self.csum = vi(self.N+1, 0);
        FOR(i, 1, N+1)
            self.csum[i] = self.csum[i-1] + A[i-1];
    }
    int sum(int l, int r) {
        r = min(r, self.N);
        l = max(l, (int)0);
        if (l >= r) return 0;
        return csum[r] - csum[l];
    }
};


int32 main(int32 argc, char* argv[]) {
    FASTCIN();
    DEBUG_IMPORT("sample-2");


    int N,K; cin>>N>>K;
    vi A(N); REP(i,N) cin>>A[i];

    vi P(N, 0);  // 非負数列
    vi M(N, 0);  // 負数列
    REP(i,N) {
        if (A[i] >= 0)
            P[i] = A[i];
        else
            M[i] = A[i];
    }

    var psum = CumSum(P);
    var msum = CumSum(M);

    int ans = -INF;
    int psum0N = psum.sum(0,N);
    FOR(l, 0, N-K+1) {
        int black = psum0N + msum.sum(l, l+K);
        ans = max(ans, black);
        int white = psum0N - psum.sum(l, l+K);
        ans = max(ans, white);
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
signed main() {
  ios::sync_with_stdio(false);
  int N; cin >> N;
  int ans = 20;
  for(int x = 1; x * x <= N; x++) {
    int y = N / x;
    if(x * y != N) continue;
    int t = max((int)log10(x), (int)log10(y)) + 1;
    ans = min(ans, t);
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define f first
#define s second
const int MAXN=200100;
const int MAXK=16;
const int INF = 1e9;
const ll MOD = 1e9+7;

ll N,M,K,Q,u,v,w,a,b,c;
vpi V[MAXN];
vi A,B;

int main(){
	cin>>N>>M>>K;
	A.pb(0);B.pb(0);
	for(int i=0;i<N;++i){cin>>a;A.pb(a);}
	for(int i=0;i<M;++i){cin>>a;B.pb(a);}
	for(int i=1;i<=N;++i)A[i]+=A[i-1];
	for(int i=1;i<=M;++i)B[i]+=B[i-1];
	int ans=0;
	for(int i=0;i<=N;++i){
		int tar=K-A[i];
		if(tar<0)break;
		int t=ub(ALL(B),tar)-B.begin()-1;
		ans=max(ans,i+t);
	}
	cout<<ans;
}

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

using namespace std;
using ll = long long;

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

int main() {
  string s;
  cin >> s;
  int n = s.size();

  string x, y;
  rep(i, n) {
    x += (i & 1) ? '1' : '0';
    y += (i & 1) ? '0' : '1';
  }

  int dx = 0, dy = 0;
  rep(i, n) {
    if (s[i] != x[i]) ++dx;
    if (s[i] != y[i]) ++dy;
  }

  cout << min(dx, dy) << endl;
  return 0;
}


Measured memory_bytes: 3976
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
#define ll long long
#define re register
using namespace std;
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9' && ch>='0'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=233333;
int front[N],nxt[N<<1],to[N<<1],w[N<<1],W[N],n,m,cnt;
int siz[N],g[N],root,sum,vis[N];
struct node
{
	int u,v;ll w;
	bool operator<(const node&b)const
		{
			return w<b.w;
		}
}e[N*50];
ll Min;
int p;
void Add(int u,int v,int val)
{
	to[++cnt]=v;nxt[cnt]=front[u];front[u]=cnt;
	w[cnt]=val;
}
void getroot(int u,int fa)
{
	siz[u]=1;g[u]=0;
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		getroot(v,u);
		siz[u]+=siz[v];
		g[u]=max(g[u],siz[v]);
	}
	g[u]=max(g[u],sum-siz[u]);
	if(g[u]<g[root])root=u;
}
void dfs(int u,int fa,ll dep)
{
	if(Min>W[u]+dep){Min=W[u]+dep;p=u;}
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		dfs(v,u,dep+w[i]);
	}
}
void Link(int u,int fa,ll dep)
{
	e[++m]=(node){u,p,dep+Min+W[u]};
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa || vis[v])continue;
		Link(v,u,dep+w[i]);
	}
}
void solve(int u)
{
	vis[u]=1;
	Min=1e18+10;p=0;
	dfs(u,0,0);Link(u,0,0);
	for(int i=front[u];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v])continue;
		sum=siz[v];root=0;
		getroot(v,u);
		solve(root);
	}
}
int f[N];
int find(int x)
{
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
int main()
{
	n=gi();
	for(int i=1;i<=n;i++)W[i]=gi();
	for(int i=1;i<n;i++)
	{
		int u=gi(),v=gi(),val=gi();
		Add(u,v,val);Add(v,u,val);
	}
	g[0]=n+1;sum=n;
	getroot(1,0);
	solve(root);
	sort(e+1,e+m+1);
	for(int i=1;i<=n;i++)f[i]=i;
	ll ans=0;int k=0;
	for(int i=1;i<=m;i++)
	{
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v)
		{
			ans+=e[i].w;
			k++;f[v]=u;
			if(k==n-1)break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 73600
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;
typedef int64_t ll;

int main() {
    int64_t N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N - 1; i++){
        int a;
        cin >> a;
        A.at(a - 1)++;
    }
    for (int i = 0; i < N; i++){
        cout << A.at(i) << endl;
    }
}

Measured memory_bytes: 4052
def Plane_2N(n, abli, cdli):

    ans = 0
    count = [0]*n

    abli.sort(key=lambda x: - x[1])
    cdli.sort()

    for i in cdli:
        for w in range(n):
            if abli[w][0] < i[0] and abli[w][1] < i[1] and count[w] == 0:
                ans += 1
                count[w] = 1
                break

    return ans

def main():
    n = int(input())
    abli = [list(map(int, input().split())) for i in range(n)]
    cdli = [list(map(int , input().split())) for i in range(n)]
    print(Plane_2N(n , abli , cdli))

if __name__ == '__main__':
    main()

Measured memory_bytes: 39152
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define MOD 1000000007

ll powll(ll x, ll y){
	if (y == 0) return 1LL;
	return (x * powll(x, y-1)) % MOD;
}

int main(){
	int n;
	cin >> n;
	VI a(n);
	REP(i,n) cin >> a[i];
	sort(a.begin(), a.end());
	bool f = 1;
	if (n % 2 == 0){
		REP(i,n){
			int x = i+1;
			if (i % 2 == 1) x--;
			if (a[i] != x) f = 0;
		}
	}else{
		REP(i,n){
			int x = i;
			if (i % 2 == 1) x++;
			if (a[i] != x) f = 0;
		}
	}
	if (!f){
		cout << 0 << endl;
		return 0;
	}

	cout << powll(2LL, n/2) << endl;
    return 0;
}

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

int main(){
    ll a, b, c; cin >> a >> b >> c;
    cout << b/c - (a-1)/c << endl;


}

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

int main() {
int k;
  cin >> k;
  vector<int> vec; // int型の配列変数vecを宣言
 
  vec = {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}; // 25, 100, 64 という整数(int)の列を代入
 
  cout << vec.at(k-1) << endl; // 1つめである25を出力
}



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

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  vector<ll> town(N);
  for (auto &e : town) cin >> e;
  ll exh = 0;
  for (ll i = 0; i < N-1; i++) exh += min((town[i+1]-town[i])*A, B);
  cout << exh << endl;
}

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

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

	vector<vector<int>> vec(M);

	for (int i = 0; i < M; ++i) {
		int k; cin >> k;
		vec[i].resize(k);
		for (int j = 0; j < k; ++j) {
			cin >> vec[i][j];
			--vec[i][j];
		}
	}

	vector<int> p(M);
	for (int i = 0; i < M; ++i) cin >> p[i];

	int ans = 0;
	for (int i = 0; i < (1 << N); ++i) {
		bool ok = true;
		for (int j = 0; j < M; ++j) {
			int c = 0;
			for (int id : vec[j]) {
				if ((i >> id) & 1) {
					++c;
				}
			}
			c %= 2;
			if (c != p[j]) {
				ok = false;
			}
		}
		if (ok) {
			++ans;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3608
import math
import itertools

N,D = map(int, input().split())

points = []
counter = 0
num = []
for i in range(N):
	points.append(list(map(int, input().split())))
	num.append(i)
  
for v in itertools.combinations(num, 2):
	length2 = 0
	i1 = int(v[0])
	i2 = int(v[1])
	for j in range(D):
		length2 += (points[i1][j] - points[i2][j])*(points[i1][j] - points[i2][j])
	length = math.sqrt(length2)
	if(length.is_integer()):
		counter += 1
  
print(counter)  

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


int main() {
    int N, K;
    cin >> N >> K;
    vector<int> l(N);
    for(int i=0; i<N; i++) cin >> l[i];
    
    sort(l.begin(),l.end());
    reverse(l.begin(),l.end());
    
    int sum=0;
    for(int i=0; i<K; i++){
        sum += l[i];
    }
    
    cout << sum << endl;
}


Measured memory_bytes: 256
import bisect
import sys
n = 1000000
primes = {i for i in range(3, n, 2)}
for i in range(3, 1000, 2):
    s = {j for j in range(i*2, n, i)}
    primes -= s

primes = [2] + sorted(primes)
for l in sys.stdin:
    print(bisect.bisect(primes, int(l)))

Measured memory_bytes: 80672
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using vc = vector<char>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

ll ds(string s)
{
        ll sm = 0;
        rep(i, 0, len(s)) sm += (ll)(s[i] - '0');
        return sm;
}

int main()
{
        ll N;
        cin >> N;
        string s = to_string(N);
        if (all_of(s.begin()+1, s.end(), [](auto x) { return x == '9'; }) or len(s) == 1) {
                cout << ds(s) << endl;
        } else {
                ll ans = 9 * (len(s)-1) + (ll)(s.front() - '0') - 1;
                cout << ans << endl;
        }
}


Measured memory_bytes: 3696
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def knapsack_01(items, weight_limit):
    values = [0] * (weight_limit + 1)
    for w, v in items:
        for j in reversed(range(w, weight_limit + 1)):
            values[j] = max(values[j], values[j - w] + v)
    return max(values)


n, t = ril()
ls = rils(n)

dp = [[0] * t for _ in range(n + 1)]
for i in range(n + 1):
    for tt in range(t):
        if i == 0 or tt == 0:
            continue
        elif ls[i - 1][0] <= tt:
            dp[i][tt] = max(dp[i - 1][tt],
                            dp[i - 1][tt - ls[i - 1][0]] + ls[i - 1][1])
        else:
            dp[i][tt] = dp[i - 1][tt]

val = dp[n][t - 1]

res = set()
tt = t - 1
for i in range(n, 0, -1):
    if val <= 0:
        break
    if val == dp[i - 1][tt]:
        continue
    else:
        res.add(i - 1)
        val = val - ls[i - 1][1]
        tt = tt - ls[i - 1][0]

remaining = [v for i, (_, v) in enumerate(ls) if i not in res]
print(dp[n][t - 1] + max(remaining) if len(remaining) else dp[n][t - 1])

Measured memory_bytes: 114140
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]


Q = int(input())
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

mod = 10 ** 6 + 3
fact_mod = FactMod(mod - 1, mod)

for x, d, n in items:
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    else:
        # d の逆元
        invd = pow(d, mod - 2, mod)

        # x にd^-1をかける
        xd = x * invd % mod

        # 10**6が数列に存在しないか
        if n - 1 + xd >= mod:
            print(0)
            continue
        # 最後にd ** nをかける
        dn = pow(d, n, mod)
        print(fact_mod.fact(xd + n - 1) * fact_mod.inv[xd - 1] % mod * dn % mod)


Measured memory_bytes: 102468
package main
import (
   "fmt"
   "os"
   "bufio"
   "strconv"
   "math"
)
var sc = bufio.NewScanner(os.Stdin)

func main() {
  sc.Split(bufio.ScanWords)
  n := nextInt()
  x := 0.0
  y := 0.0
  t := 0
  var result []bool
  for i := 0; i < n; i++{
    ti := nextInt()
    xi := nextFloat()
    yi := nextFloat()
	t = ti - t
	abs := math.Abs(xi - x) + math.Abs(yi - y)
	if t % 2 == 0{
		if int(abs) <= t && int(abs)  % 2 == 0 {
			result = append(result, true)
		} else {
			result = append(result,false)
		}
	} else {
		if int(abs) <= t && int(abs)  % 2 == 1 {
			result = append(result, true)
		} else {
			result = append(result,false)
		}

	}
	t = ti
	x = xi
	y = yi
  }

  flg := true
  length  := len(result)
  for i := 0; i < length; i++ {
	  if result[i] == false {
		  flg = false
	  }
  }

  if flg {
	  fmt.Println("Yes")
  } else {
	  fmt.Println("No")
  }

}

func nextString() (string) {
	sc.Scan()
	v := sc.Text()
	return v
}

func nextInt() (int) {
	sc.Scan()
	v, e := strconv.Atoi(sc.Text())
    if e != nil { panic(e) }
    return v
}

func nextFloat() (float64) {
	sc.Scan()
	v, e := strconv.ParseFloat(sc.Text(), 64)
    if e != nil { panic(e) }
    return v
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Rep(i,a,b) for (int i=b;i>=a;i--)
using namespace std;
int n,m,mp[16][16],x,y,z,mmh[1<<15][15],o[1<<15][15];
inline ll read()
{
    ll x=0,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;
}
inline int work(int a,int b)
{
    int mmh=0;
    for (int i=0;i<n;i++)
    if ((a>>i)&1) mmh+=o[b][i];
    return mmh;
}
int main()
{
    n=read();m=read();
    memset(mp,0,sizeof(mp));
    memset(mmh,63,sizeof(mmh));
    while(m--)
	{
        x=read();y=read();z=read();
		x--;y--;
        mp[x][y]=mp[y][x]=z;
    }
    For(i,0,(1<<n)-1)
	    For(j,0,n-1)
		{
	        o[i][j]=0;
	        For(k,0,n-1)if ((i>>k)&1) o[i][j]+=mp[j][k];
	    }
    mmh[1][0]=0;
    For(i,0,(1<<n)-1)
	    For(j,0,n-1)
		    if ((i>>j)&1){
		        For(k,0,n-1)
		       		if (mp[j][k])
		        		if (!((i>>k)&1)) 
							mmh[i|(1<<k)][k]=min(mmh[i|(1<<k)][k],mmh[i][j]+work(i,1<<k)-mp[j][k]);
		        int u=(1<<n)-1-i;
		        for (int p=u;p;p=(p-1)&u) mmh[i|p][j]=min(mmh[i|p][j],mmh[i][j]+work(i^(1<<j),p));
		    }
    printf("%d\n",mmh[(1<<n)-1][n-1]);
}

Measured memory_bytes: 4096