akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int main() {
  int n, d, x;
  cin >> n >> d >> x;
  vector<int> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  int ans = x;
  for(int i = 0; i < n; i++) {
    int count = 0;
    for(int j = 0; j < d;) {
      count++;
      j += a.at(i);
    }
    ans += count;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n,a,b = gets.split(' ').map(&:to_i)
s = gets.split('').map(&:to_s)

pass = 0
gaijin = 0
n.times do |i|
	if(s[i] == 'a') && (pass < (a + b))
			pass += 1
			puts 'Yes'
	elsif(s[i] == 'b') && (pass < (a + b))
		gaijin += 1
		if(gaijin <= b)
			pass += 1
			puts 'Yes'
		else
			puts 'No'
		end
	else
		puts 'No'
	end
end


Measured memory_bytes: 10620
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n-1];
	for(int i=0;i<n-1;i++)
	cin>>a[i];
	unordered_map<int, int> mp;
	for(int i=0;i<n-1;i++)
	mp[a[i]]++;
	
	for(int i=1;i<=n;i++)
	{
		cout<<mp[i]<<endl;
	}
}

Measured memory_bytes: 12156
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    string S;
    cin >> S;
    cout << ((S[0] == 'A'
        && count(S.begin()+2, S.end()-1, 'C') == 1
        && count_if(S.begin(), S.end(), [](char c){ return 'a' <= c && c <= 'z'; }) == S.size()-2
    ) ? "AC" : "WA") << endl;
    return 0;
}


Measured memory_bytes: 256
use std::io;

fn main() {
    let ab: Vec<String> = read_input_vec();
    println!(
        "{}",
        ab.iter()
            .map(|x| x[0..1].to_uppercase())
            .collect::<String>()
    );
}

fn read_input<T: std::str::FromStr>() -> T {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.parse::<T>().ok().unwrap();
}

fn read_input_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input
        .split_whitespace()
        .map(|x| x.parse::<T>().ok().unwrap())
        .collect();
}


Measured memory_bytes: 4352
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
#define fo(i,a,b)for(int i(a);i<(b);i++)
#define rep(i,n)fo(i,0,n)
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mp make_pair
#define pb push_back
typedef pair<pair<int,int>,int>tri;

char s[500005];
int cnt[500005];
int ans[500005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>s[i];
    for(int i=1;i<=n;i++)
    if(s[i]=='0')cnt[i]=i;
    else cnt[i]=cnt[i-1];
    for(int i=1;i<=n;i++)
    {
        ans[i]=ans[i-1];
        if(s[i]=='1')
        {
            if(s[i-1]=='0' && s[i-2]=='1')
            {
                ans[i]=max(ans[i],ans[cnt[i-2]]+i-2-cnt[i-2]);
                ans[i]=max(ans[i],ans[cnt[i-2]+1]+i-2-cnt[i-2]-1);
            }
            if(s[cnt[i]-1]=='1')
            {
                ans[i]=max(ans[i],ans[cnt[i]-2]+i-cnt[i]);
            }
        }
    }
    cout<<ans[n];
    //system("pause");
    return 0;
}

Measured memory_bytes: 4736
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String in = sc.nextLine();
		String[] inArray = in.split(" ");
		int n1 = Integer.parseInt(inArray[0]);
		int n2 = Integer.parseInt(inArray[1]);
		int ans = (n1 -1) * (n2 -1);
		System.out.println(ans);
		sc.close();
	}


}

Measured memory_bytes: 20820
N = int(input( ))
line = list(map(int,input().split( )))

#print(N,line)

i=0
t=0

while i < N-1:
    k=1
    s=0
    while line[i] == line[i+k]:
        s+=1
        if i+k+1 <= N-1:
            k+=1
        else:
            break
    t += (s+1) // 2
    i += k
    
print(t)

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

int main()
{
	unsigned long long N;
	std::cin >> N;
	std::vector<unsigned long long> Sides(N, 0);
	for (unsigned i = 0; i < N; i++)
		std::cin >> Sides[i];
	std::sort(Sides.begin(), Sides.end());
	unsigned long long Sum = 0;
	for (unsigned i = 0; i < Sides.size() - 1; i++)
		Sum += Sides[i];
	if (Sum > Sides.back())
		std::cout << "Yes" << std::endl;
	else
		std::cout << "No" << std::endl;
}

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

int main() {

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];

	int h = 0;
	long long ans = 0;

	for (int i = 0; i < n; i++) {
		h = max(h, a[i]);
		ans += h - a[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int N = 100005;
#define ll long long
int cmp(int a,int b){
	return a>b;
}	
int gcd(int x, int y)
{
    while(y^=x^=y^=x%=y);
    return x;
}
int main(){
	double n;
	cin >> n;
	double c = 2*n*3.1415926;
	cout << c;
	return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#include <sstream>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl

String to integer:
stringstream dark(s);
int x = 0; dark >> x;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


int a, b, ans=0, k=1;

void solve()
{
    cin >> a >> b;
    while (k<b) {
        --k;
        k += a;
        ans++;
    }nout(ans);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3652
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    n = int(input())
    if n == 0:
        break
    A, B = 0, 0
    for i in range(n):
        a, b = map(int, input().split())
        if a > b:
            A += a + b
        elif a < b:
            B += a + b
        else:
            A += a
            B += b

    print(A, B)

Measured memory_bytes: 6724
s=input()
l=len(s)
t=input()
k=len(t)
cand=[]
for i in range(l-k+1):
    new=""
    for j in range(l):
        if i<=j<i+k:
            if s[j]=="?":
                new+=t[j-i]
            else:
                if s[j]==t[j-i]:
                    new+=t[j-i]
                else:
                    break
        else:
            if s[j]=="?":
                new+="a"
            else:
                new+=s[j]
    if len(new)==l:
        cand.append(new)
cand.sort()
if len(cand)==0:
    print("UNRESTORABLE")
else:
    print(cand[0])

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


int N;
vvint G;

Pi dfs(int u, int p) {
	int cnt = 0;
	int sum = 0;
	int sec = 0;
	for (auto &v : G[u]) {
		if (v == p) continue;
		Pi data = dfs(v, u);
		int val = data.first;
		sec = data.second;
		sum += val;
		cnt += (int)(val > 0);
	}
	if (cnt < (int)G[u].size()-2) {
		sum += (int)G[u].size()-cnt-2;
	}

	Pi ret;
	ret.first = sum;
	ret.second = 0;
	if (cnt == max(3, (int)G[u].size())-1) {
		ret.second = 1;
	}
	if (G[u].size() <= 2) {
		ret.second = sec;
	}
	//cout << " " << u << " " << ret.second << endl;
	return (ret);
}

void Main() {
	cin >> N;
	G = vvint(N);
	for (int i = 0; i < N-1; i++) {
		int a, b; cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		if (G[i].size() == 1) {
			Pi data = dfs(i, -1);
			cout << data.first + 1 - data.second << endl;
			return;
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 13568
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  lst = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:-x[1])
  
  ans = 0
  for d, p in lst:
    if m >= d:
      m -= d
    else:
      ans += (d - m) * p
      m = 0
  print(ans)



Measured memory_bytes: 7388
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 510000;
const int MOD = 1e9;

const double PI=3.14159265358979323846;

/*
long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

std::vector<int> Eratosthenes(int n ){
    std::vector<bool> is_prime( n + 1 );
    for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;
    std::vector<int> P;
    for( int i = 2; i <= n; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= n; j += i ){
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}*/

int length(vector<int> v, int u, int HW){
    if(v.size() == 0) return HW;
    if(v[0] > u) return v[0];
    if(v[v.size() - 1] < u) return HW - v[v.size()- 1] -1;
    else{
        int i = lower_bound(ALL(v), u)- v.begin();
        return v[i] - v[i-1] -1;
    }
}

int st[200001], t[10000];

int main(){
    int X,Y,Z;
    cin >> X >> Y >> Z >>K;
    vector<ll> A(X),B(Y),C(Z);
    REP(i, X) cin >> A[i];
    REP(i, Y) cin >> B[i];
    REP(i, Z) cin >> C[i];
    vector<ll> AB(X*Y);
    REP(i, X){
        REP(j, Y){
            AB[i *Y + j] = A[i] + B[j]; 
        }
    }
    sort(ALL(AB), greater<ll>());
    AB.resize(K);
    vector<ll> ABC(K * Z);
    REP(i, K){
        REP(j, Z){
            ABC[i * Z + j] = AB[i] + C[j];
        }
    }
    sort(ALL(ABC), greater<ll>());
    REP(i,K) cout << ABC[i] << "\n";
    return 0;
}

Measured memory_bytes: 31616
n,m=map(int,input().split())

ac_list=[]
ac_flags=[False]*n
wa_count=[0]*n
penalty = 0

for i in range(m):
    pi,si=input().split()
    pi=int(pi)
    if si=='AC':
        if ac_flags[pi-1]==False:
            ac_list.append(pi-1)
            penalty += wa_count[pi-1]
            ac_flags[pi-1]=True
    else:
        wa_count[pi-1]+=1

print(len(ac_list),penalty)


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

int main()
{
	int N;
	cin>>N;
	int temp;
	
	temp=N/100;
	N-=temp*100;
	if(temp==9)
	{
		temp=1;
	}
	else
	{
		if(temp==1)
		{
		temp=9;
		}
	}
	cout<<temp;
	
	temp=N/10;
	N-=temp*10;
	if(temp==9)
	{
		temp=1;
	}
	else
	{
		if(temp==1)
		{
		temp=9;
		}
	}
	cout<<temp;
	
	temp=N;
	if(temp==9)
	{
		temp=1;
	}
	else
	{
		if(temp==1)
		{
		temp=9;
		}
	}
	cout<<temp;
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int main()
{
    string s;
    cin >> s;
    rep(i, 4)
    {
        cout << s[i];
    }
    cout << " ";
    rep(i, s.length() - 4)
    {
        cout << s[i + 4];
    }
    cout << endl;
    return 0;
}


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

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	if (n % 2 == 0) {
		cout << 0.5 << endl;
	} else {
		int odd = (n + 1) / 2;
		cout << (double)odd / n << endl;
	}		
	return 0;
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N,K;
  cin>>N>>K;
  double ans=0;
  for(int i=1;i<=N;i++){
    double res=i;
    double j;
    for(j=0;res<K;j++){
      res*=2;
    }
    ans+=pow(0.5,j)/N;
  }
  cout<<fixed<<setprecision(20)<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
const LL INF = 999999999999;

signed main(){
    string s;
    cin >> s;
    int z=0, o=0;
    for(auto &i : s){
        if(i == '0') z++;
        else o++;
    }
    cout << 2*min(z, o) << endl;

}


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

using namespace std;

int main(){
    double a,b,x,v;
    double theta=0,h;
    h = double(360) / (double(2) * M_PI);
    cin >> a;
    cin >> b;
    cin >> x;
    
    v = a * a * b - x;
    if(v <= a * a * b / 2){
        theta = double(atan(((v * double(2)) / (a * a)) / a) * h);
    }
    else{
        theta = double(atan(b / ((x * double(2)) / b / a)) * h);
    }
    cout << fixed << setprecision(10) << theta << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int h1,h2,k1,k2,a,b,c,d,h,k;
	scanf("%d %d %d %d %d %d %d %d",&h1,&h2,&k1,&k2,&a,&b,&c,&d);
    h=h1*a+(h1/10)*c+h2*b+(h2/20)*d;
	k=k1*a+(k1/10)*c+k2*b+(k2/20)*d;
	if(h>k) printf("hiroshi\n");
	else if (h<k) printf("kenjiro\n");
    else printf("even\n");
	return 0;
}	



Measured memory_bytes: 2104
A=input()
B=input()
d={}
nglist=[]
flag=0

#for i,j in zip(A,B):
#    if i == j:
#        nglist.append(j)
usedj=[]
targets=[]
for i,j in zip(A,B):
    if i not in d:
        d[i] = j
        if j not in usedj:
            usedj.append(j)
        else:
            targets.append(j)

    else:
        if d[i] != j:
            flag=1
            break
#print(targets)
#print(set(A)&set(targets))
if len(set(A)&set(targets)) >0:
    flag=1

    #if i == j:
    #    nglist.append(j)

    #if (i != j) and (j in nglist):
    #    flag=1
    #    break
    #print(d)
    #print(nglist)



if flag==1:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3632
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
K, N = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
A2 = [0] * len(A)
for i, a in enumerate(A[1:], start=1):
    A2[i] = A[i] - A[i-1]
A2.append(A[0] + K - A[-1])
print(K - max(A2))

Measured memory_bytes: 26444
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int H,W,N;
pii P[3010];
int memo[3010];

int DP(int idx)
{
	if(memo[idx]!=-1)return memo[idx];
	int res=COM(P[idx].first-1+P[idx].second-1,P[idx].first-1);
	rep(i,0,N)
	{
		if(i==idx)continue;
		int dx=P[idx].first-P[i].first;
		int dy=P[idx].second-P[i].second;
		if(dx>=0&&dy>=0)
		{
			int tres=DP(i);
			tres*=COM(dx+dy,dx);
			tres%=MOD;
			res=(res-tres+MOD)%MOD;
		}
	}
	memo[idx]=res;
	return memo[idx];
}

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

	COMinit();
	fill(memo,memo+3010,-1);

	cin>>H>>W>>N;

	rep(i,0,N)cin>>P[i].first>>P[i].second;
	P[N]=mp(H,W);

	cout<<DP(N)<<endl;

	return 0;
}

Measured memory_bytes: 12288
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 998244353;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

void get_even_divisors(ll n, vector<ll> &divisors) {
    for(ll i=1;i*i<=n;++i) {
        if(n % i) continue;
        if(i % 2) divisors.push_back(i);
        if(i * i != n && (n/i) % 2) divisors.push_back(n/i);
    }
    return;
}

ll calc_patterns(ll d, ll n, string &s) {
    // cerr << "calc_patterns(" << d << ", " << n << ", " << s << ")" << endl;
    int pattern_length = n / d;
    vector<vector<ll>> dp(n+1, vector<ll>(2, 0));
    dp[n][0] = 1;
    for(int i=n;i>n-pattern_length;--i) {
        if(s[n-i] == '1') {
            dp[i-1][0] = dp[i][0];
            dp[i-1][1] = (dp[i][0] + (2 * dp[i][1]) % MOD) % MOD;
        } else {
            dp[i-1][0] = dp[i][0];
            dp[i-1][1] = (2 * dp[i][1]) % MOD;
        }
        // cerr << dp[i-1][0] << " " << dp[i-1][1] << endl;
    }
    if(dp[n-pattern_length][0] == 0) return dp[n-pattern_length][1];
    for(int i=n-pattern_length;i>0;--i) {
        char pattern_c = s[(n-i)%pattern_length];
        if(((n-i) / pattern_length) % 2 == 1) {
            pattern_c = (pattern_c == '1') ? '0' : '1';
        }
        // cerr << pattern_c;
        if(s[n-i] == '1') {
            if(pattern_c == '1') {
                dp[i-1][0] = dp[i][0];
            } else {
                dp[i-1][1] = dp[i][0];
            }
        } else {
            if(pattern_c == '1') {
                
            } else {
                dp[i-1][0] = dp[i][0];
            }  
        }
        dp[i-1][1] += dp[i][1];
        dp[i-1][1] %= MOD;
        // cerr << dp[i-1][0] << " " << dp[i-1][1] << endl;
    }
    return (dp[0][0] + dp[0][1]) % MOD;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<ll> divisors;
    get_even_divisors(n, divisors);
    string s;
    cin >> s;

    int nd = divisors.size();
    sort(divisors.rbegin(), divisors.rend());
    ll ans = 0LL;
    vector<ll> patterns(nd);
    for(int i=0;i<nd;++i) {
        int pattern_length_i = n / divisors[i];
        patterns[i] = calc_patterns(divisors[i], n, s);
        for(int j=0;j<i;++j) {
            int pattern_length_j = n / divisors[j];
            if(pattern_length_i % pattern_length_j == 0) {
                patterns[i] += MOD - patterns[j];
                patterns[i] %= MOD;
            }
        }
        // cerr << patterns[i] << endl;
        ans += (((patterns[i] * pattern_length_i) % MOD) * 2) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}


Measured memory_bytes: 11460
#include <bits/stdc++.h>
using namespace std;
const int MOD= 1E9+7;
int main(void)
{
    long long n,m;
    cin>>n>>m;
    if(m>=2*n)
    {
        cout <<(n)+(m-2*n)/4<<endl;
    }
    else
    {
        cout <<m/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>
const int N = 100032;
using namespace std;

int a[N];
vector<int> e[N], que, buf;
bool vis[N];

void dfs(int x, int fa) {
	vis[x] = true;
	buf.push_back(a[x]);
	for (int u : e[x])
		if (u != fa) dfs(u,x);
}

int main() {
	int n, m, p = 0, u, v;
	scanf("%d%d",&n,&m);
	if (m == n-1) {puts("0"); return 0;}
	for (int i = 0; i < n; i++)
		scanf("%d",a+i);
	while (m--) {
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		dfs(i,-1); p++;
		auto it = min_element(buf.begin(), buf.end());
		ans += *it;
		swap(*it, buf.back());
		que.insert(que.end(), buf.begin(), buf.end()-1);
		buf.clear();
	}
	auto l = que.begin(), r = l + p-2;
	if (r > que.end()) {puts("Impossible"); return 0;}
	nth_element(l, r, que.end());
	printf("%lld\n",accumulate(l, r, ans));
	return 0;
}


Measured memory_bytes: 7544
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();		
        int m = sc.nextInt();
        int ans = n;
        int [] in = new int [n];
        int [] in2 = new int [n];
        for(int i=0;i<n;i++){in[i] = sc.nextInt();                             
                            }      
        for(int i=0;i<m;i++){int a = sc.nextInt();
                             int b = sc.nextInt();
                             if(in[a-1]>in[b-1]){in2[b-1]=1;
                                    }else{if(in[a-1]<in[b-1]){in2[a-1]=1;}
                                         else{in2[a-1]=1;
                                             in2[b-1]=1;}
                                         }
                            }
        for(int i=0;i<n;i++){ans-=in2[i];}
		System.out.println(ans);
	}
}


Measured memory_bytes: 60688
void main() {
	auto ip = readAs!(long[]), N = ip[0], M = ip[1];
	auto A = readAs!(long[]);
	auto s = A.sum.to!double;
	ulong cnt;
	double k = s / 4.to!double / M.to!double;
	foreach(v; A) {
		if(v.to!double >= k) cnt++;
	}
	if(cnt >= M) writeln("Yes");
	else writeln("No");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double

using namespace std;
const int N=5e5+10,mod=998244353;
int rd()
{
	int x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
};
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}
int ginv(int a){return fpow(a,mod-2);}
int n,m,fac[N<<1],iac[N<<1];
int C(int a,int b){return b<0||a<b?0:1ll*fac[a]*iac[b]%mod*iac[a-b]%mod;}

int main()
{
	fac[0]=1;
	for(int i=1;i<=1000000;++i) fac[i]=1ll*fac[i-1]*i%mod;
	iac[1000000]=ginv(fac[1000000]);
	for(int i=1000000;i;--i) iac[i-1]=1ll*iac[i]*i%mod;
	n=rd(),m=rd();
	if(n<m) swap(n,m);
	int ans=0;
	for(int i=1;i<=n;++i) ad(ans,1ll*C(i+i,i)*C(n+m-i-i,n-i)%mod);
	ans=1ll*ans*ginv(C(n+m,n))%mod*ginv(2)%mod;
	ad(ans,n);
	printf("%d\n",ans);
	return 0; 
}


Measured memory_bytes: 8064
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int a, b;
  cin >> a >> b;

  if(b % a == 0){
    cout << a + b << endl;
  }else{
    cout << b - a << endl;
  }
  return 0;
}



Measured memory_bytes: 256
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N, W := sc.nextInt(), sc.nextInt()
	V := int(1e+5)
	w := make([]int, N)
	v := make([]int, N)
	for i := 0; i < N; i++ {
		w[i] = sc.nextInt()
		v[i] = sc.nextInt()
	}
	dp := make([][]int, N+1)
	for i := 0; i <= N; i++ {
		dp[i] = make([]int, V+1)
	}
	dp[0][0] = W + 1
	for i := 1; i <= N; i++ {
		for j := 0; j <= V; j++ {
			if j >= v[i-1] && dp[i-1][j-v[i-1]] >= w[i-1]+1 {
				dp[i][j] = dp[i-1][j-v[i-1]] - w[i-1]
			}
			dp[i][j] = max(dp[i][j], dp[i-1][j])
		}
	}

	for i := V; i >= 0; i-- {
		if dp[N][i] > 0 {
			fmt.Fprintln(wtr, i)
			break
		}
	}
	wtr.Flush()
}


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

typedef long long ll;
typedef unsigned long long ull;


template <typename T>
T median2(const std::vector<T>& a){
    auto n = a.size();
    if(n == 0) return std::numeric_limits<T>::max();
    auto b = a;
    sort(b.begin(), b.end());
    int i = n / 2;
    if(n % 2 == 0){
        return (b.at(i - 1) + b.at(i));
    }else{
        return 2*b.at(i);
    }
}

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    auto ma2 = median2(A);
    auto mb2 = median2(B);
    if(N%2==0){
        cout << (mb2 - ma2) + 1 << endl;
    }else{
        cout << (mb2 - ma2) / 2 + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 7948
MOD = 10**9+7


def main():
    X, Y = map(int, input().split())
    if X > Y:
        tmp = X
        X = Y
        Y = tmp
    if (X - (Y-X)) % 3 != 0:
        print("0")
        exit()
    Xleft = (X-(Y-X)) // 3
    Yleft = (X-(Y-X)) // 3 + (Y-X)
    Xkaijou = 1

    for i in range(1, Xleft+1):
        Xkaijou = (Xkaijou*i)%MOD
    Ykaijou = Xkaijou
    for i in range(Xleft+1, Yleft+1):
        Ykaijou = (Ykaijou*i)%MOD
    zenbu = Ykaijou
    p = 0
    for i in range(Yleft+1, Xleft+Yleft+1):
        zenbu = (zenbu*i) % MOD
        p += 1
    ans = (zenbu * (pow(Xkaijou, MOD-2, MOD) * pow(Ykaijou, MOD-2, MOD) % MOD) % MOD)
    print(int(ans))
    # print(Xkaijou, Ykaijou, zenbu)
if __name__ == "__main__":
    main()


Measured memory_bytes: 38896
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
S = list(input())

ans = []

for i in range(1 << 3):
	i = list("{:b}".format(i).zfill(3))
	shiki = []
	S_ = S.copy()
	shiki.append(S_.pop(0))
	while S_ != []:
		if i.pop(0) == "0":
			shiki.append("+")
		else:
			shiki.append("-")

		shiki.append(S_.pop(0))

	if eval("".join(shiki)) == 7:
		print("".join(shiki) + "=7")
		exit()

Measured memory_bytes: 13672
function f(x,D)
	s=string(x)
	for d=D
		if d[1] in s
			return false
		end
	end
	true
end
N,T=map(x->parse(Int,x),split(readline()))
D=split(readline())
while !f(N,D)
	N+=1
end
println(N)


Measured memory_bytes: 117424
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 4e3 + 10;
int sum1[N][N];
int sum2[N][N];
int n, k;

int getsum(int sum[N][N], int x1, int y1)
{
	int x2 = x1 - k + 1, y2 = y1 - k + 1;
	return sum[x1][y1] - sum[x1][y2 - 1] - sum[x2 - 1][y1] + sum[x2 - 1][y2 - 1];
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n >> k;
	while (n--)
	{
		int x, y;
		char c;
		cin >> x >> y >> c;
		x %= k * 2, y %= k * 2;
		x++, y++;
		if (c == 'W')
		{
			sum1[x][y]++;
			sum1[x + k * 2][y]++;
			sum1[x][y + k * 2]++;
			sum1[x + k * 2][y + k * 2]++;
		}
		else
		{
			sum2[x][y]++;
			sum2[x + k * 2][y]++;
			sum2[x][y + k * 2]++;
			sum2[x + k * 2][y + k * 2]++;
		}
	}
	for (int i = 1; i <= 4 * k; i++)
	{
		for (int j = 1; j <= 4 * k; j++)
		{
			sum1[i][j] += sum1[i][j - 1] + sum1[i - 1][j] - sum1[i - 1][j - 1];
			sum2[i][j] += sum2[i][j - 1] + sum2[i - 1][j] - sum2[i - 1][j - 1];
		}
	}
	int ans = 0;
	for (int i = k * 2; i <= 4 * k; i++)
	{
		for (int j = k * 2; j <= 4 * k; j++)
		{
			int tot = getsum(sum1, i, j) + getsum(sum1, i - k, j - k)
				+ getsum(sum2, i - k, j) + getsum(sum2, i, j - k);
			ans = max(ans, tot);
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int N;
  cin>>N;
  vector<char> vec(N);
  for(int i = 0; i<N;i++){
    cin>>vec.at(i);
  }
  if(N%2 == 0){
    int check = 0;
    for(int i = 0; i<N/2; i++){
      if(vec.at(i) == vec.at(i+N/2)) continue;
      else check++;
      break;
    }
    if(check) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
}



Measured memory_bytes: 256
package main

import "fmt"

func main(){
  var a, b, c, d int
  fmt.Scan(&a, &b, &c, &d)
  var res string
  switch {
  case a+b > c+d: res = "Left"
  case a+b == c+d: res = "Balanced"
  case a+b < c+d: res ="Right"
  }
  fmt.Println(res)
}


Measured memory_bytes: 512
input = raw_input

N = int(input())
h = list(map(int,input().split(" ")))

dp = [0 for i in range(N)]

for i in range(N-2, -1, -1):
    if i == N-2:
        dp[i] = dp[i+1] + abs(h[i] - h[i+1])
    else:
        dp[i] = min(dp[i+1] + abs(h[i] - h[i+1]), dp[i+2] + abs(h[i] - h[i+2]))

print(dp[0])


Measured memory_bytes: 39276
t_life, t_attack, a_life, a_attack = list(map(int, input().split()))
#  体力　攻撃力
t_c = 0
a_c = 0

while True:
    a_life -= t_attack
    t_c += 1
    if a_life <= 0:
        break


while True:
    t_life -= a_attack
    a_c += 1
    if t_life <= 0:
        break

if t_c <= a_c:
    print('Yes')
else:
    print('No')

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

int main() {
  long n;
  cin >> n;
  string ans = "";
  if (n == 0) {
    cout << "0" << endl;
    return 0;
  }
  while (n) {
    if (n % 2 == 0) {
      ans += "0";
    } else {
      ans += "1";
      n -= 1;
    }
    n /= -2;
  }

  reverse(ans.begin(), ans.end());
  int flag = false;
  for (int i = 0; i < ans.size() - 1; i++) {
    if (ans[i] == '1') {
      flag = true;
    }
    if (true) {
      cout << ans[i];
    }
  }
  cout << ans.back() << endl;
}


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

/*                    ॐ Shree ॐ                     */
/* ॐ ॐ ॐ
ॐ भूर् भुवः स्वः
तत् सवितुर्वरेण्यं
भर्गो देवस्य धीमहि
धियो यो नः प्रचोदयात्
*/
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
// online submission
#endif
	int k,n,a;
	vector<bool> present(110,false);
	cin>>k>>n;
	while(n--){
		cin>>a;
		present[a]=true;
	}
	int res=0;
	for(int i=0;i<=101;i++){
		if(present[i]==false && abs(res-k)>abs(i-k)){
			res=i;
		}
	}
	cout<<res;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll h[n];
    for(ll i=0;i<n;i++)
        cin>>h[i];
    ll dp[n];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(ll i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<dp[n-1];
}

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

int main(){
 int n;
 string x;
 cin >> n >> x;
  int count =0;
  if(n%2 == 0){
 for (int i =0; i < n/2; i++){
  if (x.at(i) == x.at(i + n/2)){
    count++;
  }
 }
  if (n/2 == count){
  cout << "Yes" <<endl;
  }
  else{
  cout << "No" <<endl;
  }
  }
  else{
   cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():

    N = input()

    l = len(N) - 1
    N = int(N)
    count = 0
    if l % 2 == 1:
        count += N - 10**(l-1) + 1
    i = 1
    while i < l:
        count += 10**i - 10**(i-1)
        i += 2
    print(count)




    pass
if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >>n;
    if(n%2==0){
        int k = 0;
        char arr[n];
        for(int i=0; i <n; ++i){
            cin >> arr[i];
        }
        while(k<n/2){
            if(arr[k] != arr[k+(n/2)]){
                cout << "No";
                k = -1;
                break;
            }
            ++k;
        }
        if(k!=-1){
            cout<< "Yes";
        } 
    }
    else{
        cout<<"No";
    }    
    return 0;
}

Measured memory_bytes: 256
//ABC171

#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <random>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <string>
#include <numeric>
#include <random>

using namespace std;

int main(){
    long long int n, q, buf, buf_1, buf_2, sum = 0; 
    cin >> n;
    vector<long long int> vv(100000, 0), l;
    for(int i=0; i<n; i++){
        cin >> buf;
        vv.at(buf-1)++;
        sum += buf;
    }
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> buf_1 >> buf_2;
        sum += vv.at(buf_1-1)*(buf_2-buf_1);
        vv.at(buf_2-1) += vv.at(buf_1-1);
        vv.at(buf_1-1) = 0;
        l.push_back(sum);
    }
    for(auto n: l){
        cout << n << endl;
    }
    return 0;
}

Measured memory_bytes: 5108
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) REP(i,0,b)
#define long long int lld
#define INF INT_MAX/3
#define debug(x) cout<<"#x"<<": "<<x<<endl
int main(void){
	string str;
	string list="abcdefghijklmnopqrstuvwxyz";
	vector<char> a,b;
	map<char,int> c;

	cin >> str;
	for(int i = 0; i < str.size(); i++) a.push_back(str[i]);
	for(int i = 0; i < list.size(); i++ ) b.push_back(list[i]);
	for(int i = 0; i < list.size(); i++) c[b[i]] = 0;
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());

	/*
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < b.size(); j++){
			if(b[i] == a[j]) c[b[i]]++;
		}
	}
	*/
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < b.size(); j++){
			if(a[i] == b[j]) c[b[j]]++;
		}
	}
	//for(int i = 0; i < list.size(); i++) cout <<c[b[i]]<< endl;
	int tmp = 1;
	for(int i = 0; i < b.size(); i++){
		if(c[b[i]]) continue;
		else{
			tmp = c[b[i]];
			cout << b[i] << endl;
			break;
		}
	}
	if(tmp) cout << "None" << endl;
	return 0;
}


Measured memory_bytes: 640
N, C = map(int, input().split())
rec = [[0]*C for _ in range(10**5)]
for _ in range(N):
  s, t, c = map(int, input().split())
  for i in range(s-1, t):
    rec[i][c-1] = 1

print(max([sum(rec[i]) for i in range(10**5)]))

Measured memory_bytes: 41800
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
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; }

ll func(ll a, ll b, ll x){
    ll tmp = x/b;
    return a*x/b - a*tmp;
}

int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    if(n>=b){
        cout << func(a,b,b-1) << endl;
    }else{
        cout << func(a,b,n) << endl;
    }


    return 0;
}


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

void solve()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    --k;
    s[k] = (char)tolower(s[k]);
    cout << s << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
// __builtin_ctz : no of trailing zeros
#define int long long
#define ll long long
#define pp pair<int,int>
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;
int max(int x, int y)
{
    return x>y ? x : y;
}
int min(int x, int y)
{
    return x<y ? x : y;
}
void _(int&a , int b)
{
    a=(a%mod+b%mod)%mod;
    a=(a+mod)%mod;
}
ll cl(ll a,ll b)
{
    return (a/b)+(!(!(a%b)));
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a;cin >> a;long double b;cin >> b;
    b=b*a;
    cout << (ll)b;
    }

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

int main(int argc, char *argv[]){
  int N,M;
  cin>>N;
  vector<int> A(N+1,0);
  vector<int> B(N,0);
  int a;
  vector<int> memo(N+1,0);
  for(int i=1; i<N+1; i++){
    cin>>a;
    A[i]=a;
  }
  int count=0;
  for(int i=N; i>0; i--){
      
      int sum=0;
      for(int j=i; j<N+1; j+=i){
		if(j%i==0){
	 	sum+=memo[j];
	}
      }
      if(sum%2==A[i]) continue;
      else{
		memo[i]++;
		B.push_back(i);
		count++;
	
      }
    }
  
  
  cout<<count<<endl;
  for(int i=N; i>=0; i++){
   
    if(B[i]==0) break;
    else{
      cout<<B[i]<<" ";
    }
  }



}
      


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <deque>
/**
 * 傾き: a[0]>a[1]>...
 * 座標: x[0]<x[1]<...
 */
template <typename T>
struct SimpleCHT
{
    using P = std::pair<T, T>;
    std::vector<P> lines;

public:
    void add(const T a, const T b)
    {
        auto check = [](auto&& self, const P& l1, const P& l2, const P& l3) -> bool { return l1 < l3 ? self(self, l3, l2, l1) : (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first); };
        while (lines.size() >= 2 and check(check, *(lines.end() - 2), lines.back(), {a, b})) { lines.pop_back(); }
        lines.push_back({a, b});
    }
    T query(const T x) const
    {
        static std::size_t head = 0;
        auto f = [&](const std::size_t i, const T x) { return lines[i].first * x + lines[i].second; };
        for (; lines.size() - head >= 2 and f(head, x) > f(head + 1, x); head++) {}
        return f(head, x);
    }
};
using ll = long long;
int main()
{
    std::size_t N;
    ll C;
    std::cin >> N >> C;
    std::vector<ll> h(N), dp(N);
    for (std::size_t i = 0; i < N; i++) { std::cin >> h[i]; }
    SimpleCHT<ll> cht;
    cht.add(-2 * h[0], dp[0] + h[0] * h[0]);
    for (std::size_t i = 0; i < N; i++) {
        dp[i] = cht.query(h[i]) + h[i] * h[i] + C;
        cht.add(-2 * h[i], dp[i] + h[i] * h[i]);
    }
    std::cout << dp[N - 1] << std::endl;
    return 0;
}


Measured memory_bytes: 9328
//K-OS WITH THE OCDE

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <iostream>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <climits>

using namespace std;

typedef long long int ll;
typedef long double db;


#define TEST ll t; cin>>t; while(t--)
#define vell vector<ll>
#define pl pair<ll,ll>
#define all(v) v.begin(),v.end()
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define dbg(x)  cerr << #x << ": "<< x <<endl
#define dbg2(x,y) cerr<< #x <<": "<< x <<" || "<< #y << ": " << y << endl

#define endl "\n"
#define MAX 1e18
#define MIN INT_MIN
#define mod 1000000007



void solve()
{
    ll n, x, t;
    cin >> n >> x >> t;
    ll f = (n / x) + (n % x != 0);
    cout << t * f << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    //TEST
    solve();
}



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

  int f(int x) {
    int cnt = 0;
    while (x % 2 == 0) {
      x /= 2;
      cnt++;
    }
    return cnt;
  }

  int main(){
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
      cin >> v.at(i);
    }
    int tmp = 0;
    for (int i = 0; i < n; i++) {
      if (v.at(i) % 2 == 0) {
        int x = v.at(i);
        tmp += f(x);
      }
    }
    cout << tmp << endl;

  }


Measured memory_bytes: 256
MOD = 10**9 + 7
def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
S = int(input())
ans = 0
for i in range(1,S+1):
    tmp = S
    tmp -= i*3
    if tmp < 0:
        continue
    ans += comb(i+tmp-1,tmp)
    ans %= MOD
print(ans)


Measured memory_bytes: 9216