akhauriyash/Code-Regression huggingface dataset:
N, M, X = gets.chomp.split(" ").map(&:to_i)

DATA = []

N.times.map { gets.chomp }.each_with_index do |row, i|
  values = row.split(" ").map(&:to_i)
  DATA[i] = {c: values.shift, a: values}
end

def hoge(arr)
  price = 0
  lern = []

  arr.each do |i|
    price += DATA[i][:c]

    M.times do |j|
      # 全参考書の学習度
      lern[j] = 0 unless lern[j]
      lern[j] += DATA[i][:a][j]
    end
  end

  {
    arr: arr,
    price: price,
    val: lern.map{|l| X - l},
    learned: lern.map{|l| X - l}.all?{|v| v <= 0}
  }
end

results = []

N.times do |j|
  (0..N-1).to_a.combination(j+1).to_a.each do |_arr|
    results << hoge(_arr)
  end
end

lern_arr = results.select{|h| h[:learned]}

if lern_arr.count == 0
  puts -1
else
  puts lern_arr.map{|h| h[:price]}.sort.first
end

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

struct data {
	int wa;
	int ac;
};

void init_data(struct data* data, int n)
{
	int i;
	for (i = 0; i < n; i++)
	{
		data[i].wa = 0;
		data[i].ac = 0;
	}
}

int main()
{
	int m, n;
	int i, tmp;
	int wa_cnt = 0, ac_cnt = 0;
	char tmp_char[2];
	struct data *input;

	scanf("%d %d", &m, &n);
	input = (struct data*)malloc(sizeof(struct data) * (m + 1));
	if (input == NULL)
	{
		fprintf(stderr, "Failed to allocate memory\n");
		return -1;
	}

	init_data(input, m);

	for (i = 0; i < n; i++)
	{
		scanf("%d %s", &tmp, tmp_char);
		if (strcmp(tmp_char, "WA") == 0)
		{
			if (input[tmp].ac == 0)
				input[tmp].wa++;
		}
		else if (strcmp(tmp_char, "AC") == 0)
			input[tmp].ac = 1;
		else
			continue;
	}

	for (i = 0; i <= m; i++)
	{
		if (input[i].ac == 1)
		{
			ac_cnt++;
			wa_cnt += input[i].wa;
		}
	}

	printf("%d %d\n", ac_cnt, wa_cnt);

	return 0;
}

Measured memory_bytes: 896
A, B, C = [int(x) for x in input().split()]
ans = 0
while True:
    if A % 2 == 1 or B % 2 == 1 or C % 2 == 1:
        break
    elif A == B == C:
        ans = -1
        break
    ans += 1
    A, B, C = (B + C) // 2, (A + C) // 2, (A + B) // 2

print(ans)

Measured memory_bytes: 9220
#include <stdio.h>

int main() {
	int a, b, c, ans = 0, i = 0;
	scanf("%d %d %d", &a, &b, &c);

	while(a > 0 ){
		if(ans >= b && ans <= c){
			printf("OK");
			break;
		}else if(ans > c){
			printf("NG");
	 	break;
		}
		i++;
		ans = a * i; 
		}
  return 0;
}

Measured memory_bytes: 3228
use proconio::input;

fn main() {
    input!{
        a: u64,
        b: u64,
        n: u64,
    }
    let f = |x| { (a * x / b) - a * ( x / b ) };
    let mut ans = f(n);
    if n >= b - 1 {
        ans = std::cmp::max(ans, f(b - 1));
    }
    println!("{}", ans);
}


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

#define ipair pair<int,int>
#define rep(i,n) for(i=0;i<n;i++)
#define repj(i,j,n) for(i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()
#define SIZE(a,n) (a).resize(n)
#define SORT(a) sort(ALL(a))
#define RSORT(a, type) sort(ALL(a),greater<type>())
#define MAPIN(a,i,j) (a).insert(make_pair(i,j))
#define PREC(n) setprecision(n)

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

using namespace std;

typedef unsigned long long lli;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > Matrix;

int main() {
    ll r;

    cin>>r;

    cout<<r*r;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <stack>
#include <deque>
#include <ctime>
#include <random>
#include <cassert>
#include <cmath>
#include <climits>
#include <queue>
#include <cstring>
#include <bitset>
#include <iomanip>
#include <chrono>

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2")
*/


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else 
    #define dbg(x)
#endif

#define int long long
#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a,b) for (int i=a;i<b;i++)
#define fj(a,b) for (int j=a;j<b;j++)
#define fk(a,b) for (int k=a;k<b;k++)
#define fi1(a,b) for (int i=a-1;i>=b;i--)
#define fj1(a,b) for (int j=a-1;j>=b;j--)
#define fk1(a,b) for (int k=a-1;k>=b;k--)
#define fx(x,a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, T2 y) { if (x < y) x = y; }

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << ' ';
    return a;
}


typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 100010;
const int D = 310;
const double EPS = 1e-9;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[MX][D];
deque<int> mx[D];


int get(int i) {
    if (mx[i].empty())
        return 0;
    return mx[i].front();
}

void add(int i, int x) {
    while (mx[i].size() && mx[i].back() < x)
        mx[i].ppb;
    mx[i].pb(x);
}

void del(int i, int x) {
    if (mx[i].size() && mx[i].front() == x)
        mx[i].pop_front();
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
       
    int n, m, k;
    cin >> n >> m >> k;
    int ans = 0;
    fi(0, n) {
        int a;
        cin >> a;
        fj1(min(i + 1, k) + 1, 1) {
            if (i >= m)
                del(j, dp[i - m][j]);
            dp[i][j] = a * j + get(j - 1);
            add(j, dp[i][j]);
        }
        maxe(ans, dp[i][k]);
    }
    cout << ans << '\n';
}

Measured memory_bytes: 246112
#include <stdio.h>
#include <stdlib.h>

#define A_CHARACTER 'A'
#define B_CHARACTER 'B'
#define C_CHARACTER 'C'



void CreateArray(char * letterArray, int * lettersAmount)
{
	
}

int main()
{
	int lettersAmount, printOutput = 0;	
	char inputChar;
	scanf("%d", &lettersAmount);
	char *letterArray;

	letterArray = malloc(sizeof(char) * lettersAmount);

	for (int i = 0; i < lettersAmount + 1; i++)
	{
		scanf("%c", &inputChar);
		letterArray[i - 1] = inputChar;
	}

	for (int i = 0; i < lettersAmount; i++)
	{
		char stringABC[5];
		if (letterArray[i] == A_CHARACTER && i < lettersAmount && i + 1 < lettersAmount && i + 2 < lettersAmount)
		{
			stringABC[0] = letterArray[i];
			stringABC[1] = letterArray[i + 1];
			stringABC[2] = letterArray[i + 2];
		}
		if (stringABC[0] == 'A' && stringABC[1] == 'B' && stringABC[2] == 'C')
		{
			printOutput++;
		}

		stringABC[0] = NULL;
		stringABC[1] = NULL;
		stringABC[2] = NULL;
	}

	printf("%d \n", printOutput);
	return 0;
}

Measured memory_bytes: 128
import math

n,d=map(int,input().split())
x=[]
for i in range(n):
    x.append(list(map(int,input().split())))
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        dis = 0
        for k in range(d):
            dis += (x[i][k]-x[j][k])**2
        dis = math.sqrt(dis)
        if (dis-int(dis) == 0):
            ans += 1
print(ans)

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

map<int, int> mp[100010];

vector<pair<int, int> > tmp;
int main(){
  int n, m;
  cin >> n >> m;

  int p[100010], y[100010];


  for(int i = 0;i < m;i++){
    cin >> p[i] >> y[i];
    tmp.push_back(make_pair(y[i],p[i]));
  }

  sort(tmp.begin(), tmp.end());

  int tt[100010] = {};
  for(int i = 0;i < tmp.size();i++){
    mp[tmp[i].second][tmp[i].first] = tt[tmp[i].second]+1;
    tt[tmp[i].second]++;
  }

  for(int i = 0;i < m;i++){
    printf("%06d%06d\n", p[i], mp[p[i]][y[i]]);
  }

  return 0;
}


Measured memory_bytes: 12788
import math
import sys

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False

q = input()
lr = []
max_num = 0
INF = sys.maxint
input_list = sieve_of_erastosthenes(100000)
# prime_list = [i for i, b in enumerate(input_list) if b == True]
prime_list_append = []
sum_count = 0
for index, i in enumerate(input_list):
    if i and input_list[(index + 1) / 2]:
        # print i, (index + 1)/2, sum_count
        sum_count += 1
        prime_list_append.append(sum_count)
    else:
        prime_list_append.append(sum_count)

for ii in xrange(q):
    tmp = map(int, raw_input().split(" "))
    # count = 0
    # for j in prime_list_append[tmp[0]:tmp[1]]:
    #     count += 1
    print prime_list_append[tmp[1]] - prime_list_append[tmp[0]-1]


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

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<ll> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

struct Item {
    ll price, weight, time;
    char type;
    string name;

    bool operator<(const Item &other) const {
        if (price < other.price) return true;
        if (price > other.price) return false;

        if (weight < other.weight) return true;
        if (weight > other.weight) return false;

        if (type < other.type) return true;
        if (type > other.type) return false;

        if (time < other.time) return true;
        if (time > other.time) return false;

        if (name < other.name) return true;
        if (name > other.name) return false;

        __throw_runtime_error("onaji");

    }


};

int main() {
    int n;
    cin >> n;
    vector<Item> a(n);
    rep(i, n) {
        cin >> a[i].price;
        cin >> a[i].weight;
        cin >> a[i].type;
        cin >> a[i].time;
        cin >> a[i].name;
    }

    sort(a.begin(), a.end());

    for (Item p : a) {
        printf("%lld %lld %c %lld %s\n", p.price, p.weight, p.type, p.time, p.name.c_str());
    }
}


Measured memory_bytes: 12984
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n; cin>>n;
  long double sum=0;
  int m1,m2; m1=0; m2=0;
  long double r,t; 
 vector<vector<int>> data(n, vector<int>(2));

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> data.at(i).at(j);
    }
  }

r=0;
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        m1=data[i][0]-data[j][0];
        m2=data[i][1]-data[j][1];
      t=sum+ ( sqrt(m1*m1+m2*m2) +r);
      r= ( sqrt(m1*m1+m2*m2) +r) -(t-sum);
      sum=t;


    }
}
cout << fixed << setprecision(10);
cout<<sum*2/n<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define llong long long
#define pii pair<int,int>
#define riterator reverse_iterator
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 250;
llong P;
int al[(N<<1)+3],ar[(N<<1)+3],ax[(N<<1)+3];
int a[(N<<1)+3],cnt[(N<<1)+3];
llong dp[(N<<1)+3][N+3];
int n;

bool cmp(int x,int y) {return ax[x]>ax[y];}

llong updsum(llong &x,llong y) {x = x+y>=P?x+y-P:x+y;}

llong solve(int k)
{
	memset(dp,0,sizeof(dp));
	dp[n+n][0] = 1ll;
	for(int i=n+n-1; i>=0; i--)
	{
		for(int j=0; j<=k; j++)
		{
			llong x = dp[i+1][j]; if(!x) continue;
			if(a[i]>=n)
			{
				updsum(dp[i][j],x*(max(0,ar[a[i]]+1-j-cnt[i]))%P);
			}
			else
			{
				updsum(dp[i][j+1],x*(max(0,al[a[i]]+1-j-cnt[i]))%P);
				updsum(dp[i][j],x*(max(0,ar[a[i]]+1-(3*n-1+k-i-cnt[i]-j)))%P);
			}
		}
	}
	return dp[0][k];
}

int main()
{
	scanf("%d%lld",&n,&P);
	for(int i=0; i<n; i++) al[i] = n*n-i*i-1,ax[i] = al[i];
	for(int i=0; i<n+n; i++) {ar[i] = 4*n*n-i*i; if(i>=n) ax[i] = ar[i];}
	for(int i=0; i<n+n; i++) a[i] = i;
	sort(a,a+n+n,cmp);
	for(int i=0; i<n; i++) al[i] = sqrt(al[i]);
	for(int i=0; i<n+n; i++) ar[i] = min((int)sqrt(ar[i]),n+n-1);
	for(int i=n+n-1; i>=0; i--) cnt[i] = cnt[i+1]+(a[i+1]>=n);
//	printf("a: "); for(int i=0; i<n+n; i++) printf("%d ",a[i]); puts("");
//	printf("cnt: "); for(int i=0; i<n+n; i++) printf("%d ",cnt[i]); puts("");
	llong ans = 0ll;
	for(int i=0; i<=n; i++)
	{
		llong cur = solve(i);// printf("ans[%d]=%lld\n",i,cur);
		if(i&1) updsum(ans,P-cur); else updsum(ans,cur);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1280
def resolve():
    H, W = map(int, input().split())
    S = []
    abs = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    for i in range(H):
        s = list(input().split())
        S.append(s)
    for p in range(H):
        for q in range(W):
            if S[p][q] == "snuke":
                print(abs[q]+str(p+1))
resolve()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  vector<int> l(60);
  cin >> n >> k;
  for(int i=0; i<n; i++){
    cin >> l[i];
  }
  sort(l.begin(), l.end(), greater<int>());
  int sum=0;
  for(int i=0; i<k; i++){
    sum+=l[i];
  }
  cout << sum << endl;
}

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

int main()
{
    int n;
    cin >> n;
    vector<string> w(n);
    rep(i, n) cin >> w[i];
    string ans = "Yes";
    repl(i, 1, n) {
        if(w[i][0] != w[i - 1][w[i - 1].size() - 1]) ans = "No";
        rep(j, i) {
            if(w[i] == w[j]) ans = "No";
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n, m = map(int, raw_input().split());
i = 0
ar = [0] * n
vc = [0] * m
while i < n:
    ar[i] = map(int, raw_input().split());
    i += 1
i = 0
while i < m:
    vc[i] = input();
    i += 1
for el in ar:
    ans = 0
    for el2, el3 in zip(vc, el):
        ans += el2 * el3
    print ans

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

int main() {
	int k = 0, sum = 0, x = 0, y = 0, z = 0, a = 0;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			for (int l = 1; l <= k; l++) {
				x = i; y = j; z = l;
				while ((a = x % y) != 0) {
					x = y;
					y = a;
				}
				while ((a = y % z) != 0) {
					y = z;
					z = a;
				}
				sum += z;
			}
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 3636
#if LOCAL_ENVIRONMENT == 1
#include "debug.hpp"
#endif
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
 
using namespace std;
#define ll long long
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}

#if LOCAL_ENVIRONMENT == 1
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define debugDP(dp) debugDPTable(dp);
#else
#define debug(x) {}
#define debugBit(x,n) {}
#define debugDP(dp) {}
#endif
 
int main()
{
#if LOCAL_ENVIRONMENT == 1
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
  ll N = input();
  ll W = input();
 
  vector<ll> weight;
  vector<ll> value;
  
  for(ll i=0;i<N;i++){
    ll w = input();
    ll v = input();
    weight.push_back(w);
    value.push_back(v);
  }
 
  vector<vector<ll>> dp(N+1, vector<ll>(W+1));
 
  for(int w=0;w<=W;w++){
    dp[0][w] = 0;
  }
 
  for(int i=0;i<N;i++){
    for(int w=0;w<=W;w++){
      if(weight[i] <= w){
        dp[i+1][w] = max(dp[i][w], dp[i][w-weight[i]] + value[i]);
      }
      else{
        dp[i+1][w] = dp[i][w];
      }
    }
  }

  debugDP(dp)
  debug(N);
  output(dp[N][W]);
 
  return 0;
}

Measured memory_bytes: 80256
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
	public static void main(String[]args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		int H=0;
		int W=0;
		String[] arr;
		while((str=br.readLine())!=null){
			arr=str.split(" ");
			H=Integer.parseInt(arr[0]);
			W=Integer.parseInt(arr[1]);
			if((H==0)&&(W==0)){
				break;
			}
			for(int i=1;i<=H;i++){
				for(int j=1;j<=W;j++){
					if((i==1)||(i==H)||(j==1)||(j==W)) System.out.print("#");
					else System.out.print(".");
				}
				System.out.print("\n");
			}
			System.out.print("\n");
		}
		br.close();
	}
}

Measured memory_bytes: 29676
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s.rfind('F')!=-1&&s.find('C')!=-1&&s.rfind('F')>s.find('C'))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
/*  ***  In The Name of God ... ***  */ 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int long long
#define all(v) v.begin() , v.end()
#define pb push_back
#define endl '\n' 
template<typename T> inline bool smin(T &a, const T &b){ return b < a ? a = b,1:0;}
template<typename T> inline bool smax(T &a, const T &b){ return a < b ? a = b,1:0;}

const int N = 1e5 + 10 ;

int n , t [ N ] , x [ N ] , y [ N ] ; 

int d ( int x , int y , int xx , int yy ) {
	return abs ( x - xx ) + abs ( y - yy ) ; 
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n ;
	for ( int i = 1 ; i <= n ; ++ i )
		cin >> t [ i ] >> x [ i ] >> y [ i ] ;
	t [ 0 ] = x [ 0 ] = y [ 0 ] = 0 ; 
	for ( int i = 1 ; i <= n ; ++ i ) {
		int dis =  d ( x [ i - 1 ] , y [ i - 1 ] , x [ i ] , y [ i ] ) ; 
		if ( dis > t [ i ] - t [ i - 1 ] || ( dis + t [ i ] - t [ i - 1 ] ) & 1 )
			return cout << "No\n" , 0 ; 
	}
	cout << "Yes\n" ; 
}


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

int main() {
	int n, m, A[100][100], b[100], c[100];

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)cin >> A[i][j];
	for (int i = 0; i < m; i++)cin >> b[i];

	for (int i = 0; i < n; i++) {
		c[i] = 0;
		for (int j = 0; j < m; j++){
			c[i] += A[i][j] * b[j];
	}
	}
	for (int i = 0; i < n; i++)cout << c[i] << endl;

	return 0;
}

Measured memory_bytes: 3028
import java.util.*;

public class Main {
	static final long MODULO = 1_000_000_000 + 7;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int C = sc.nextInt() - 1;
		int T = sc.nextInt();
		int[] a = new int[K];
		int[] b = new int[K];
		int[] t = new int[K];
		for (int i = 0; i < K; ++i) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			t[i] = sc.nextInt();
		}
		long[][][] A = new long[6][N][N];
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < b[i]; ++j) {
				A[t[i]][j][(a[i] - 1) + j] += 1;
			}
			for (int j = 0; j < a[i] - 1; ++j) {
				A[t[i]][b[i] + j][j] += 1;
			}
			for (int j = a[i] + b[i] - 1; j < N; ++j) {
				A[t[i]][j][j] += 1;
			}
		}
		long[][] dp = new long[6][N];
		dp[0][C] = 1;
		for (int i = 1; i <= 5; ++i) {
			for (int j = 0; j < i; ++j) {
				dp[i] = addVec(dp[i], mulVec(A[i - j], dp[j]));
			}
		}
		long[] v = new long[N * 5];
		for (int i = 0; i < 5; ++i) {
			for (int j = 0; j < N; ++j) {
				v[j + i * N] = dp[i][j];
			}
		}
		long[][] mx = new long[5 * N][5 * N];
		for (int i = N; i < 5 * N; ++i) {
			mx[i - N][i] = 1;
		}
		for (int i = 1; i <= 5; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					mx[4 * N + j][N * (5 - i) + k] = A[i][j][k];
				}
			}
		}

		v = mulVec(pow(mx, T), v);
		System.out.println(v[0]);
	}

	static long[][] mul(long[][] a, long[][] b) {
		int n = a.length;
		long[][] ret = new long[n][n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					ret[i][j] += a[i][k] * b[k][j] % MODULO;
					ret[i][j] %= MODULO;
				}
			}
		}
		return ret;
	}

	static long[] mulVec(long[][] a, long[] v) {
		int n = v.length;
		long[] ret = new long[n];
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				ret[i] += a[i][j] * v[j] % MODULO;
				ret[i] %= MODULO;
			}
		}
		return ret;
	}

	static long[] addVec(long[] a, long[] b) {
		int n = a.length;
		long[] ret = new long[n];
		for (int i = 0; i < n; ++i) {
			ret[i] = (a[i] + b[i]);
			if (ret[i] >= MODULO)
				ret[i] -= MODULO;
		}
		return ret;
	}

	static long[][] pow(long[][] a, long n) {
		int len = a.length;
		long[][] ret = new long[len][len];
		for (int i = 0; i < len; ++i)
			ret[i][i] = 1;
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1) {
				ret = mul(ret, a);
			}
		}
		return ret;
	}

}

Measured memory_bytes: 43776
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

#define Nmax 300003

int N, K;
int A[Nmax];
int T[Nmax*4];

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }

void update(int node, int st, int dr, int pos, int val) {
    if (st == dr) {
        T[node] = val;
        return;
    }
    int m = (st + dr) >> 1;
    if (m >= pos) {
        update(node << 1, st, m, pos, val);
    } else {
        update((node << 1) + 1, m + 1, dr, pos, val);
    }
    T[node] = max(T[node << 1], T[(node << 1) + 1]);
}

int query(int node, int st, int dr, int l, int r) {
    if (l <= st && r >= dr) {
        return T[node];
    }
    int m = (st + dr) >> 1;
    int v1 = 0, v2 = 0;
    if (m >= l) {
        v1 = query(node << 1, st, m, l, r);
    }
    if (m < r) {
        v2 = query((node << 1) + 1, m + 1, dr, l, r);
    }
    return max(v1, v2);
}

int main() {
    int best = 0;
    cin >> N  >> K;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    for (int i = 0; i < N; ++i) {
        int res = query(1, 0, Nmax, max(A[i] - K, 0), min(A[i] + K, Nmax)) + 1;
        update(1, 0, Nmax, A[i], res);
        if (res > best) {
            best = res;
        }
    }
    
    cout << best;
    
    return 0;
}


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

int main(){
    int x,y,esc;
    while(1){
        cin >> x >> y;
        if(x==0&&y==0){break;}
        if(x>y){
            esc = x;
            x = y;
            y = esc;
        }
        cout << x << ' ' << y << endl;
    }
}


Measured memory_bytes: 2980
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e5 + 100, INF = 1e9 * 1e4 + 10, MOD = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n, a, b, c, d, dp[SIZE][30], lf, q;
vector<ll> vec;
map<ll, ll> ch;

ll check(int val, int pos) {
    if (val == 0) return pos;

    ll lft = val, u = pos;
    for (ll i = 29; i >= 0; i--) {
        if (lft - (1ll << i) >= 0) {
            u = dp[u][i];
            lft -= (1ll << i);
        }
    }

    return u;
}
void sol() {
    cin >> n;
    vec.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }

    cin >> lf;

    cin >> q;

    for (int i = 29; i >= 0; i--) {
        dp[n - 1][i] = n - 1;
    }
    for (int i = vec.size() - 2; i >= 0; i--) {
        int l = i, r = vec.size();

        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (vec[i] + lf < vec[mid]) {
                r = mid;
            }
            else {
                l = mid;
            }
        }

        dp[i][0] = l;
        for (int j = 1; j < 30; j++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    
    while (q--) {
        ll lq, rq;
        cin >> lq >> rq;
        if (lq > rq) swap(lq, rq);

        if (lq == rq) {
            cout << "0\n";
            continue;
        }

        lq--;
        rq--;
        ll dist = 0, cur = lq, curR = rq;

        int l = 0, r = vec.size() + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (check(mid, cur) >= curR) {
                r = mid;
            }
            else {
                l = mid;
            }
        }
        cout << r << "\n";
    }
}

int main()
{
    fastInp;

    ll t = 1;

    while (t--) {
        sol();
    }

    return 0;
}

Measured memory_bytes: 27536
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0

for i in b:
    ans+=(n-bisect.bisect(c,i))*bisect.bisect_left(a,i)

print(ans)

Measured memory_bytes: 101408
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <map>

#define ll long long
const ll MOD = 1e9 + 7;
const ll INF = 1 << 29;


int main()
{
    ll N, M, X;
    std::cin >> N >> M >> X;

    ll C[N];
    ll A[N][M];

    for (auto i=0; i<N; ++i)
    {
        std::cin >> C[i];
        for (auto j=0; j<M; ++j)
            std::cin >> A[i][j];
    }

    // 2^N を調べてそれぞれの場合で目標達成できるなら最小の金額を更新する
    ll result = INF;
    ll bit = 1 << N;
    for (auto i=0; i<bit; ++i)
    {
        ll cSum = 0;
        std::vector<ll> aSum(M, 0);
        for (auto n=0; n<N; ++n)
        {
            // n 番目の本を買う場合
            if (i & 1 << n)
            {
                cSum += C[n];
                for (auto m=0; m<M; ++m)
                    aSum[m] += A[n][m];
            }
        }

        auto canLearned = true;
        for (auto m=0; m<M; ++m)
            canLearned &= (X <= aSum[m]);

        if (canLearned && cSum < result)
            result = cSum;
    }

    if (result == INF)
        result = -1;

    std::cout << result << std::endl;
}

Measured memory_bytes: 3600
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int x[11];
    rep(i, N) cin >> x[i];
    int pattern = 1;
    rep(i, N) pattern *= 3; 
    int ans = 0;
    rep(tmp, pattern) {
        int bit = tmp;
        int y[11];
        rep(i, N) {
            y[i] = x[i] + bit % 3 - 1;
            bit /= 3;
        }
        bool ok = false;
        rep(i, N) if(y[i] % 2 == 0) ok = true;
        ans += ok;
        //rep(i, N) cout << y[i] << " ";
        //cout << ok  << endl;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
typedef struct Dice{
	int d[6];
	int r[6];
	int b[6];
}dice;
int main(){
	dice num,num2;
	int i,c,c2;
	for(i=0;i<6;i++){
		scanf("%d",&num.d[i]);
	}
	for(i=0;i<6;i++){
		scanf("%d",&num2.d[i]);
	}


	for(int k=0;k<6;k++){
		num.b[k]=num.d[k];
	}

	c=0;
	c2=0;
	for(int k=0;k<6;k++){
		num.r[k]=num.d[k];
	}
	for(int j=0;j<4;j++){
		for(int k=0;k<6;k++){
			num.r[k]=num.b[k];
		}
		num.r[2]=num.b[0];
		num.r[3]=num.b[5];
		num.r[5]=num.b[2];
		num.r[0]=num.b[3];
		for(int k=0;k<6;k++){
			num.b[k]=num.r[k];
		}
		if(num.r[0]==num2.d[0]){
			c=1;
			break;
		}

	}
	if(c==0){
		for(int j=0;j<4;j++){
			for(int k=0;k<6;k++){
				num.r[k]=num.b[k];
			}
			num.r[1]=num.b[0];
			num.r[4]=num.b[5];
			num.r[5]=num.b[1];
			num.r[0]=num.b[4];
			for(int k=0;k<6;k++){
				num.b[k]=num.r[k];
			}
			if(num.r[0]==num2.d[0]){
				c=1;
				break;
			}
		}
	}
	if(c==0){
		printf("No\n");
		return 0;
	}
	for(int j=0;j<4;j++){
		for(int k=0;k<6;k++){
			num.r[k]=num.b[k];
		}
		num.r[1]=num.b[3];
		num.r[4]=num.b[2];
		num.r[2]=num.b[1];
		num.r[3]=num.b[4];
		for(int k=0;k<6;k++){
			num.b[k]=num.r[k];
		}
		if(num.r[1]==num2.d[1]){
			c2=1;
			break;
		}
	}
	if(c2==0){
		printf("No\n");
		return 0;
	}
	if(num.r[2]==num2.d[2]&&num.r[3]==num2.d[3]&&num.r[4]==num2.d[4]&&num.r[5]==num2.d[5]){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

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

using namespace std;

vector<int> edge[100050];
int n;
int dep[100050];

void predo(int pos,int lst)
{
	dep[pos] = dep[lst] + 1;
	for(auto v : edge[pos])
		if(v != lst)
			predo(v,pos);
}

int par[100050];

void seek(int pos,int lst)
{
	dep[pos] = dep[lst] + 1;
	par[pos] = lst;
	for(auto v : edge[pos])
		if(v != lst)
			seek(v,pos);
}

vector<int> chain;
bool fg = 0;

void fuck(int pos,int l1,int l2)
{
	for(auto v : edge[pos])
		if(v != l1 && v != l2)
		{
			if(l2 == -1)
			{
				fg = 1;
				return ;
			}
			fuck(v,pos,-1);
		}
}

void Output(int *a)
{
	for(int i = 1;i <= n; ++ i)
		printf("%d ",a[i]);
	exit(0);
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i < n; ++ i)
	{
		int u,v; scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	predo(1,0);
	int pos = 0,maxn = 0;
	for(int i = 1;i <= n; ++ i)
		if(dep[i] > maxn)
			maxn = dep[i],pos = i;
	int tmp;
	seek(tmp = pos,0);
	pos = 0,maxn = 0;
	for(int i = 1;i <= n; ++ i)
		if(dep[i] > maxn)
			maxn = dep[i],pos = i;
	while(pos != tmp)
	{
		chain.push_back(pos);
		pos = par[pos];
	}
	chain.push_back(tmp);
	static int ans1[100050],ans2[100050];
	int a1c = 0,a2c = 0;
	for(int i = 0;i < chain.size(); ++ i)
	{
		fuck(chain[i],i == 0 ? 0 : chain[i - 1],i == chain.size() - 1 ? 0 : chain[i + 1]);
		if(fg)
		{
			printf("-1\n");
			return 0;
		}
		int c = edge[chain[i]].size() - 2 + (i == 0 || i == chain.size() - 1);
		int l = a1c + 1,r = a1c + 1 + c;
		for(int j = l + 1;j <= r; ++ j)
			ans1[++ a1c] = j;
		ans1[++ a1c] = l;
	}
	for(int i = chain.size() - 1;i >= 0; -- i)
	{
		int c = edge[chain[i]].size() - 2 + (i == 0 || i == chain.size() - 1);
		int l = a2c + 1,r = a2c + 1 + c;
		for(int j = l + 1;j <= r; ++ j)
			ans2[++ a2c] = j;
		ans2[++ a2c] = l;
	}
	for(int i = 1;i <= n; ++ i)
		if(ans1[i] < ans2[i])
			Output(ans1);
		else if(ans1[i] > ans2[i])
			Output(ans2);
	Output(ans1);
}

Measured memory_bytes: 13048
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# 
# a, b
# s = input()

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n-1):
    if (p[i-1] < p[i] and p[i] < p[i+1]) or (p[i-1] > p[i] and p[i] > p[i+1]):
        ans += 1
print(ans)


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

int main() {
  int A, B;
  string S,T, U;
  cin>>S>>T;
  cin>>A>>B;
  
  cin>>U;
  
  if(S == U) A = A-1;
  
  if(T == U) B = B-1;
    
  
    
  cout<<A<<" "<<B<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sync ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define mod 1000000007
using namespace std;
vector<ll> prime,sfac;
vector<ll>ps;
void sieve(ll n)
{
	prime.assign(n+1,1);
	sfac.assign(n+1,1);    
    for (int p=2; p*p<=n; p++) 
    {         
        if (prime[p] == 1) 
        { 	sfac[p]=p;  			  
            for (int i=p*p; i<=n; i += p) 
              {  prime[i] = 0; sfac[i]=p;}
        } 
    } 
	for(ll i=2;i<=n;i++)
	{
		if(prime[i])
			ps.push_back(i);
	}
}
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll power(ll x, ll y) 
{ 
    ll res = 1;     // Initialize result 
   
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = res*x; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = x*x;  // Change x to x^2 
    } 
    return res; 
}
int isPrime(ll n) 
{ 
    // Corner cases 
    if (n <= 1)  return 0; 
    if (n <= 3)  return 1; 
  
    // This is checked so that we can skip  
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return 0; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return 0; 
  
    return 1; 
} 

int main()
{
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    vector<ll>m;
    m.assign((1e+5)+1,0);
    for(int i=0;i<n;i++)
        m[a[i]]++;
    ll sum=0;
    for(int i=0;i<n;i++)
        sum+=a[i];
    ll q;
    cin>>q;
    while(q--)
    {
        ll b,c;
        cin>>b>>c;
        sum-=b*m[b];
        sum+=c*m[b];
        ll cc=m[b];
        m[b]=0;
        m[c]+=cc;
        cout<<sum<<endl;
    }

}


Measured memory_bytes: 4824
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[][] board = new int[N][N];
        int[][] temp = new int[M][M];

        for(int i = 0; i<N; i++) {
            String str = sc.next();
            for(int j = 0; j<N; j++) {
                board[i][j] = (str.charAt(j)=='#')?1:0;
            }
        }

        for(int i = 0; i<M; i++) {
            String str = sc.next();
            for(int j = 0; j<M; j++) {
                temp[i][j] = (str.charAt(j)=='#')?1:0;
            }
        }

        boolean f = false;
        for(int i = 0; i<=N-M; i++) {
            for(int j = 0; j<=N-M; j++) {
                f = true;
                for(int ii = 0; ii<M; ii++) {
                    for(int jj = 0; jj<M; jj++) {
                        if(board[i+ii][j+jj] != temp[ii][jj]) {
                            f=false;
                            //System.out.println(f);
                        }
                        //System.out.println(i+" "+j+" "+board[i+ii][j+jj] +" "+ temp[ii][jj]);
                    }
                }
                //System.out.println("f = " + f);
                if(f) {
                    System.out.println("Yes");
                    return;
                }
            }

        }

        System.out.println("No");

    }
}

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

int main() {
  int x, y, n;

  while (1) {
    cin >> x >> y;
    if (x == 0 && y == 0) {
      break;
    }
    if (x > y) {
      n = x;
      x = y;
      y = n;
    }

    cout << x << " " << y << endl;

  }
}


Measured memory_bytes: 3108
N, K, Q = map(int, input().split())
# 全問不正解の場合を初期値にする
l = [K - Q] * N
# 正解者に１ポイント加算
for _ in range(Q):
    A = int(input())
    l[A - 1] += 1

for li in l:
    if li <= 0:
        print("No")
    else:
        print("Yes")


Measured memory_bytes: 11484
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	A := nextInt()
	B := nextInt()
	if B == 1 {
		fmt.Println(0)
	} else {
		d := (B - 1) / (A - 1)
		r := (B - 1) % (A - 1)
		if r > 0 {
			d += 1
		}
		fmt.Println(d)
	}
}

func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}

func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}

func nextString() string {
	return nextReader()
}

func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

func nextInt64s(n int) []int64 {
	r := make([]int64, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt64()
	}
	return r
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func Min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func MinA(arg ...int) int {
	var s = arg[0]
	for _, v := range arg {
		s = Min(s, v)
	}
	return s
}

func MaxA(arg ...int) int {
	var s = arg[0]
	for _, v := range arg {
		s = Max(s, v)
	}
	return s
}

func Abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
// #define ll long long
typedef long long ll;
typedef pair<int, int> P;



int main(int argc, const char * argv[]) {

  int a, b;
  cin >> a >> b;
  
  if ((a + b) % 2 == 1) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }

  // long long a = (a + b) / 2;
  cout << (a + b) / 2 << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
ll x[100100], y[100100];

const int MAX = 100100;
const int MAX_E = 200100;
int par[MAX];
int r[MAX];

typedef struct {
    int u, v;
    ll cost;
} edge;

bool compare(const edge &e1, const edge &e2) {
    return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

void init(int n) {
    for (int i = 0; i < n; i++) {
	par[i] = i;
	r[i] = 0;
    }
}

int find(int x) {
    if (par[x] == x) {
	return x;
    } else {
	return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (r[x] < r[y]) {
	par[x] = y;
    } else {
	par[y] = x;
	if (r[x] == r[y]) r[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

ll kruskal() {
    sort(es, es+E, compare);
    init(V);
    ll res = 0;
    for (int i = 0; i < E; i++) {
	edge e = es[i];
	if (!same(e.u, e.v)) {
	    unite(e.u, e.v);
	    res += e.cost;
	}
    }
    return res;
}

struct info {
    ll px, py;
    int idx;
};

ll solve() {
    vector<info> vec;
    for (int i = 0; i < n; i++) {
        vec.push_back(info{x[i], y[i], i});
    }
    E = 0;
    sort(ALL(vec), [](const info& a, const info& b){ return a.px < b.px; });
    for (int i = 0; i < n-1; i++) {
        es[E] = edge{vec[i].idx, vec[i+1].idx, vec[i+1].px-vec[i].px};
        E++;
    }
    sort(ALL(vec), [](const info& a, const info& b){ return a.py < b.py; });
    for (int i = 0; i < n-1; i++) {
        es[E] = edge{vec[i].idx, vec[i+1].idx, vec[i+1].py-vec[i].py};
        E++;
    }
    V = n;
    return kruskal();
}

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

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

    input();
    cout << solve() << endl;
}


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

int main(){
  ll n;
  int k, ans = 0;
  scanf("%lld%d", &n, &k);
  while(n){
    n/=k;
    ans++;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

template<typename T> class fenwick {
  public:
  vector<T> fenw;
  int n;  
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (1 + x);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
  T get(int a, int b) {
    if (a > 0) {
      return get(b) - get(a - 1);
    } else {
      return get(b);
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  fenwick<long long> ft(n);
  while (q--) {
    long long com, x, y;
    cin >> com >> x >> y;
    if (com == 0) {
      ft.modify(x - 1, y);
    } else {
      cout << ft.get(x - 1, y - 1) << '\n';
    }    
  }
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
using namespace std;
typedef pair<int, int> P;

signed main(){
    int a[3];
    rep(i, 0, 3) cin >> a[i];
    sort(a, a + 3);
    if(a[0] + a[1] == a[2]) o("Yes");
    else o("No");
}

Measured memory_bytes: 256
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
P-=1
def f(x):
  if x<=P:
    return True
  elif A[x]+M<A[P]:
    return False
  c=0
  for i in range(N):
    if i<P or i>=x+1:
      c+=M
    else:
      c+=A[x]+M-A[i]
  return c>=M*V

l,r=0,N
while l+1!=r:
  m=(l+r)//2
  if f(m):
    l=m
  else:
    r=m
print(l+1)

Measured memory_bytes: 20376
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef double d;
int main()
{
    int num,odd_number=0;
    cin>>num;
    for(int i=1;i<=num;i++)
        if(i%2!=0)
        odd_number++;
        printf("%.10f\n",(d)odd_number/num);
    //cout<<setprecision(10)<<(d)odd_number/num<<endl;
    std::cin.get();
}


Measured memory_bytes: 256
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
const ll MAX = 2e5+10;
vector<ll> d(MAX,-1);
ll solve(ll n){
  if(n==0) return d[n] = 0;
  if(d[n]!=-1) return d[n];
  ll res = 0,cnt = 0,cn=n;
  while(n!=0){
    cnt += n%2;
    n /= 2;
  }
  res = solve(cn%cnt);
  return d[cn] = res + 1;
}
signed main(){
  init_io();
  ll n,btc=0,v0,v1,a0=0,a1=0;
  string s;
  cin >> n >> s;
  for(auto c:s){
    if(c=='1') btc++;
  }
  if(btc==1){
    if(s.back()=='1'){
      for(int i=0;i<n-1;i++) cout <<2<<endl; cout << 0 << endl;
    }else{
      for(int i=0;i<n-1;i++){
        if(s[i]=='1') cout << "0"<<endl;
        else cout << 1<<endl;
      }
      cout << 2 << endl;
    }
    return 0;
  }
  v0=1,v1=1;
  for(int i=n-1;i>=0;i--){
    a0 += v0*(s[i]=='1');
    a1 += v1*(s[i]=='1');
    v0 *= 2;
    v1 *= 2;
    a0 %= btc+1;
    a1 %= btc-1;
    v0 %= btc+1;
    v1 %= btc-1;
  }
  v0=1,v1=1;
  vector<ll> ans(n);
  for(int i=n-1;i>=0;i--){
    if(s[i]=='0'){
      ll t = (a0+v0)%(btc+1);
      ans[i] = solve(t);
    }else{
      ll t = (a1-v1+(btc-1)*4)%(btc-1);
      ans[i] = solve(t);
    }
    v0 *= 2;
    v1 *= 2;
    v0 %= btc+1;
    v1 %= btc-1;
  }
  for(int i=0;i<n;i++){
    cout << ans[i]+1 << endl;
  }
}


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

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

  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    B.at(i) = A.at(i);
  }
  sort(B.begin(), B.end());
  int a = B.at((N / 2) - 1);
  int b = B.at((N / 2));

  for (int i = 0; i < N; i++) {
    if (A.at(i) >= b)
      cout << a << endl;
    else
      cout << b << endl;
  }
}

Measured memory_bytes: 3712
const stdin = require('fs').readFileSync('/dev/stdin', 'utf8').trim()

const n = Number(stdin.split('\n')[0])
const h = stdin
  .split('\n')[1]
  .split(' ')
  .map(Number)

const ans = () => {
  let current = []

  for (let i = 0; i < n; i++) {
    current.push(0)
  }

  // 高さが足りないものを全てグループ化する
  // グループ化したものをすべて1増やす
  // 足りないものがなくなるまで繰り返す

  let count = 0
  while (1) {
    let head = -1
    let tail = -1

    // グループの始点と終点を探す
    for (let i = 0; i < n; i++) {
      if (head === -1 && current[i] < h[i]) {
        head = i
      }

      if (head > -1 && current[i] >= h[i]) {
        tail = i
        break
      }
    }

    // 終了条件
    if (head === -1) {
      return count
    }

    if (tail === -1) {
      tail = n
    }

    for (let i = head; i < tail; i++) {
      current[i] += 1
    }

    count++
  }
}

console.log(ans())


Measured memory_bytes: 7372
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main(void) {

	string s, t;
	cin >> s >> t;

	char sa[s.length() + 1];
	s.copy(sa, s.length());
	sa[s.length()] = '\0';
	sort(sa, sa + s.length());

	char ta[t.length() + 1];
	t.copy(ta, t.length());
	ta[t.length()] = '\0';
	sort(ta, ta + t.length());
	reverse(ta, ta + t.length());

	if (strcmp(sa, ta) < 0) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}



Measured memory_bytes: 256
m, n = map(int, input().split())
LN = 1000000007

def pwr(p, q):
    if q == 1:
        return p%LN
    elif q % 2 == 0:
        return (pwr(p, q//2)%LN)**2%LN
    else:
        return (pwr(p, q//2)%LN)**2*p%LN

print(pwr(m, n))



Measured memory_bytes: 5600
N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for l_pop in range(K + 1):
    for r_pop in range(K + 1):
        X = []
        if (l_pop + r_pop > K) or (l_pop + r_pop > N):
            continue
        else:
            X.extend(V[:l_pop])
            X.extend(V[::-1][:r_pop])

        X.sort()
        tmp = sum(X)
        for k in range(K - l_pop - r_pop):
            if k > len(X) - 1:
                break
            else:
                if X[k] < 0:
                    tmp -= X[k]

        ans = max(ans, tmp)

print(ans)


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

n = int(input())
*a, = map(int, input().split())

tmp = 1
cnt = 0
for i in range(n):
    if a[i] == tmp:
        tmp += 1
    else:
        cnt += 1

if cnt == n:
    print(-1)
else:
    print(cnt)

Measured memory_bytes: 24988