akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
int p[200005], block[200005];
int cover[200005];
int left[200005], right[200005];
int a[200005], b[200005];
int cost[200005][2];
int answer[200005];

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

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

int find(int u){
    if(p[u]==u) return u;
    else return p[u] = find(p[u]);
}

void merge(int x,int y){
    int u = find(x), v = find(y);
    if(u==v) return ; 
    block[u] += block[v];
    p[v] = u;
}

void doMerge(int l,int r,int tag){
    for(int i = l; i <= r; i++) cover[i] = tag;
}

void preWork(int n,int m){
    for(int i = n; i >= 1; i--){
        cost[i][0] = cost[i][1] = m;
        doMerge(a[i],b[i],i);
        left[i] = cover[a[i]-1];
        right[i] = cover[b[i]+1];
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    n++; a[n] = 1, b[n] = m;
    preWork(n,m);
    for(int i = 1; i <= m; i++){
        if(cover[i]!=1){
            int next = cover[i];
            //printf("next = %d\n",next);
            cost[next][0] = 0;
            cost[next][1] = min(cost[next][1],b[next]-i+1);
        }
    }
    cost[1][0] = cost[1][1] = 0;
    for(int i = 2; i <= n; i++){
        if(right[i]!=0){
            //printf("right[%d] = %d\n",i,right[i]);
            int rp = b[i]+1, next = right[i];
            cost[next][0] = min(cost[next][0],cost[i][1]);
            cost[next][1] = min(cost[next][1],cost[i][1]+b[next]-rp+1);
        }
    }
    //for(int i = 1; i <= n; i++) printf("cost[%d][0] = %d, cost[%d][1] = %d\n",i,cost[i][0],i,cost[i][1]);
    int minn = m;
    for(int i = n; i >= 2; i--){
        if(minn>cost[i][0]) minn = cost[i][0];
        if(minn!=m) answer[i] = minn+i-1;
        else answer[i] = -1;
    }
    for(int i = 2; i <= n; i++) printf("%d\n",answer[i]);
    return 0;
}


Measured memory_bytes: 7892
a = int(input())
ar = list(map(int,input().split(" ")))
count = 0
sw = "ON"
while sw == "ON":
    for r in ar:
        if r % 2 == 1:
            sw = "OFF"
    if sw == "ON":
        count += 1
        for i,r in enumerate(ar):
            ar[i] //= 2
print(count)

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

int main(){
string s;

long long ans  = 1,n,a ;
cin>>n>> a;
if(n==1){cout<<a<<endl;
return 0;
}
for(long long i=2;i<=sqrt(a)+1;i++ ){ 

if(a%i==0){
int cnt=0;
while(a%i==0){
cnt++ ;
a/=i;
 }
cnt/=n;
for(int j=0;j<cnt;j++)ans*=i;
}
}
cout<<ans<<endl;
return 0;
}

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

int main(){
  int n,k,x;
  cin >> n >> k;
  int sum[200010]={};
  for(int i=0;i<n;i++){
    cin >> x;
    sum[x]++;
  }
  int ans = 0;
  sort(sum,sum+200010,greater<int>());
  for(int j=0;j<k;j++){
    ans += sum[j];
  }
  cout << n-ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define maxn 200005
const ll inf=1e9+7;
#define pb push_back
#define PI 3.14159265
#define watch(x) cerr << (#x) << " is " << (x) << endl;
void solve();
void sieve();
int main()
{
	//sieve();
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout<<fixed;
	cout<<setprecision(10);
	
	ll t=1;
	//cin>>t;
	while(t--)
	solve();
	
	return 0;
}

ll pr[1001];
vector<ll> prime;
void sieve()
{
	pr[0]=-1;
	pr[1]=-1;
	ll i,j;
	for(i=2;i<1001;i++)
	{
		if(pr[i]!=-1)
		{
			pr[i]=1;
			for(j=2;j<1001/i+1;j++)
			{
				if(i*j<1001)
				pr[i*j]=-1;
			}
		}
	}
	for(i=2;i<1001;i++)
	{
		if(pr[i]==1)
		prime.pb(i);
	}
}
		
bool pal(string s)
{
	string t=s;
	reverse(s.begin(),s.end());
	return (t==s);
}
ll countdig(ll x)
{
	ll c=0;
	if(x==0)
	return 1;
	
	while(x!=0)
	{
		c++;
		x/=10;
	}
	return c;
}
bool isprime(ll x)
{
	bool flag=true;
	for(ll i=2;i<=sqrt(x)+1;i++)
	{
		if(x%i==0)
		{
			flag=false;
			break;
		}
	}
	if(x==1)
	flag=false;
	
	return flag;
}
void swap(ll& a,ll& b)
{
	ll t=a;
	a=b;
	b=t;
}
class matrix 
{
	public:
	vector<vector<ll>> v;
	ll row;
	ll col;
	matrix(vector<vector<ll>> mat)
	{
		v.assign(mat.begin(),mat.end());
		row=mat.size();
		col=mat[0].size();
	}
	vector<vector<ll>> I(ll n)
	{
		vector<vector<ll>> mat(n,vector<ll>(n,0));
		for(ll i=0;i<n;i++)
		mat[i][i]=1;
		return mat;
	}
	matrix operator * (matrix& u)
	{
		ll r=this->row;
		ll c=u.col;
		assert(this->col==u.row);
		vector<vector<ll>> res(r,vector<ll>(c,0));
		for(ll i=0;i<r;i++)
		{
			for(ll j=0;j<c;j++)
			{
				for(ll k=0;k<this->col;k++)
				res[i][j]+=v[i][k]*u.v[k][j];
			}
		}
		return matrix(res);
	}
	matrix fastexpo(matrix m,ll p)
	{
		assert(m.row==m.col);
		matrix res(I(m.row));
		
		while(p)
		{
			if(p&1)
			res=res*m;
			m=m*m;
			p=p>>1;
		}
		return res;
	}
};
bool comp(ll a,ll b)
{
	return a>b;
}
void gensparse()
{
	ll n=5,i,j;
	ll st[n][27];
	ll arr[]={1,2,3,4,5};
	for(i=0;i<n;i++)
	st[i][0]=(arr[i]);
	
	for(j=1;j<27;j++)
	{
		for(i=0;i+(1<<j)-1<n;i++)
		{
			st[i][j]=(st[i][j-1]+st[i+(1<<(j-1))][j-1]);
		}
	}
	//now query 
	ll l,r;
	cin>>l>>r;
	ll ans=0;
	for(j=26;j>=0;j--)
	{
		if((1<<j)<=r-l+1)
		{
			ans+=st[l][j];
			l+=(1<<j);
		}
	}
	cout<<ans;
}
ll solve(ll l,ll r,ll n)
{
	if(l>r)
	return 0;
	ll g=(l+r)/2;
	if(g==0)
	return solve(g+1,r,n);
	
	if(n>=(ll)pow(26,g-1)+1&&n<=(ll)pow(26,g))
	return g;
	else if(n>(ll)pow(26,g))
	return solve(g+1,r,n);
	else
	return solve(l,g-1,n);
}
void solve()
{
	ll n,i,s=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		ll curr=i*(n/i)*(n/i+1)/2;
		s+=curr;
		
	}
	cout<<s;
}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	


Measured memory_bytes: 3696
n = int(input())
a = [[] for _ in range(100010)]
for i in range(n):
    a[i] = (list(map(int, input().split())))

dp = [[0] * 3 for _ in range(100010)]
for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i][k] < dp[i - 1][j] + a[i - 1][k]:
                dp[i][k] = dp[i - 1][j] + a[i - 1][k]
print(max(dp[n]))

Measured memory_bytes: 71200
n=int(input())
a=list(map(int,input().split()))

from itertools import product

pattern= list(product([0,1,2],repeat=n))

cnt=0
for p in pattern:
    ans=1
    for i in range(n):
        if p[i]==0:
            ans*=(a[i]-1) 
        elif p[i]==1:
            ans*=a[i] 
        else:
            ans*=(a[i]+1) 
        
    if ans%2==0:
        cnt+=1

print(cnt)

Measured memory_bytes: 17072
#include <stdio.h>

void func(int **a, int i, int j)
{
	if(a[i][j] == 0){
		return ;
	}
	a[i][j] = 0;
	
	if(i-1 >= 0){
		func(a, i-1, j);
	}
	if(i+1 < 12){
		func(a, i+1, j);
	}
	if(j-1 >= 0){
		func(a, i, j-1);
	}
	if(j+1 < 12){
		func(a, i, j+1);
	}
	
	return ;
}

int main(int argc, char **argv)
{
	int i, j, **a, t;
	
	while(scanf("%1d", &t) != EOF){
		a = (int **)calloc(12, sizeof(int));
		for(i = 0; i < 12; i++){
			a[i] = (int *)calloc(12, sizeof(int));
		}
		a[0][0] = t;
		for(i = 1; i < 12; i++){
			scanf("%1d", &a[0][i]);
		}
		for(i = 1; i < 12; i++){
			for(j = 0; j < 12; j++){
				scanf("%1d", &a[i][j]);
			}
		}
		
		for(i = 0, t = 0; i < 12; i++){
			for(j = 0; j < 12; j++){
				if(a[i][j] == 1){
					func(a, i, j);
					t++;
				}
			}
		}
		printf("%d\n", t);
		
		for(i = 0; i < 12; i++){
			free(a[i]);
		}
		free(a);
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#define N 100
int main(){
  int i,j,n,A[N],flag,a,b=0,m;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }flag=1;
  while(flag){
    flag=0;
    for(j=n-1;j>=1;j--){
      if(A[j]<A[j-1]){
        a=A[j];
        A[j]=A[j-1];
        A[j-1]=a;
        flag=1;
        b++;
      }
    }
  }for(m=0;m<n-1;m++){
    printf("%d",A[m]);
    printf(" ");
  }printf("%d\n",A[n-1]);
  printf("%d\n",b);
}



Measured memory_bytes: 2044
n,m = map(int,input().split())
l = []
for i in range(m):
    l.append([i] + list(map(int,input().split())))

l.sort(key=lambda x: (x[1],x[2]))

p = -1
no = 0
for item in l:
    if item[1] != p:
        p = item[1]
        no = 1
    else:
        no += 1
    item.append(no)

l.sort()

for item in l:
    print("{:06}{:06}".format(item[1],item[3]))

Measured memory_bytes: 36084
from bisect import bisect_left
 
N,M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
 
while M > 0:
    x = A.pop(-1)
    x //= 2
    ind = bisect_left(A, x)
    M -= 1
    if ind < N-1:
        temp = [x] + [A[-i-1]//2 for i in range(min(M, N-1 - ind))]
        A = sorted(A[:N-len(temp)] + temp)
    else:
        A.insert(bisect_left(A, x), x)
    M -= N-1 - ind
 
print(sum(A))

Measured memory_bytes: 14480
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define clear(a, b) memset((a), (b), sizeof(a))
typedef long long LL;
int read() {
	int x = 0, flag = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * flag;
}

#define Maxn 1009
char s[Maxn];
int n;
int W, E, S, N;
int main() {
#ifdef Qrsikno
	freopen("AGC003_1.in", "r", stdin);
	freopen("AGC003_1.out", "w", stdout);
#endif
	scanf("%s", s);
	n = strlen(s);
	rep(i, 0, n - 1){
		if(s[i] == 'W') W = 1;
		if(s[i] == 'E') E = 1;
		if(s[i] == 'S') S = 1;
		if(s[i] == 'N') N = 1;
	}
	if((N ^ S) || (W ^ E)) puts("No");
	else puts("Yes");
	return 0;
}


Measured memory_bytes: 256
using System;


class AOJ
{

    public static void Main()
    {

        const int max = 1000001;
        bool[] prime = new bool[max];

        prime[0] = prime[1] = false;

        for (int i = 2; i < max; i++)
            prime[i] = true;

        for (int i = 2; i * i < max; i++)
        {
            if (prime[i])
            {
                for (int j = (i << 1); j < max; j += i)
                {
                    if (prime[j])
                        prime[j] = false;
                }
            }
        }

        int count, n;
        string str;

        while ((str = Console.ReadLine()) != null)
        {

            n = int.Parse(str);
            count = 0;

            for (int i = 2; i <= n; i++)
            {
                if (prime[i])
                    count++;
            }

            Console.WriteLine(count);
        }
    }
}

Measured memory_bytes: 6580
from operator import itemgetter
N = int(input())

T = list()
for i in range(N):
    S, P = map(str, input().split())
    T.append((S, int(P), str(i+1)))

T = sorted(T, key=itemgetter(1), reverse=True)
T = sorted(T, key=itemgetter(0))
for t in T:
    print(t[2])


Measured memory_bytes: 9088
fn main() {
    let v = read_vec::<i64>();
    let n = v[0];
    let k = v[1];
    println!("{}", std::cmp::min((n % k).abs(), (k - n % k).abs()));
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <vector <int>> vii;
typedef vector <long long> vll;
typedef vector <string> vs;
typedef vector <char> vc;
typedef set <int> si;
typedef set <string> ss;
typedef queue <int> qi;
typedef queue <long long> qll;
typedef queue <string> qs;
typedef queue <char> qc;
typedef struct board board;
typedef pair <int, int> pi;
typedef pair <long long, long long> pll;
typedef pair <int, pair<int, int>> pii;

#define eb emplace_back
#define ppb pop_back
#define clr(a) a.clear()
#define F first
#define S second
#define mkp make_pair

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define left(x) x * 2
#define right(x) x * 2 + 1

#define meme(a, b, c) fill(a + 1, a + 1 + b, c)

#define max(a, b) (a > b ? a : b)
#define min(a, b) (a > b ? b : a)
#define abs(a) (a > 0? a : -(a))

#define move(s) s += "#"

#define fr(i, a, b) for (ll i = a; i <= b; ++ i)
#define rf(i, a, b) for (ll i = a; i >= b; -- i)

#define eprintf(...) fprintf(stderr, __VA_ARGS__);

void to_pray() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr << "Ready\n";
}

const int N = 4e6 + 10;
const int NN = 1e3 + 10;
const int NNN = 2e3 + 9;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e12 + 7;
const ll P = 53;
const int EPS = 1e-9 - 8;
const int vN = 2e4 + 10;
const int sz = (1 << 22) - 1;
const double PI = acos(-1);

int main () {
    to_pray();
    
    int a, b;
    cin >> a >> b;
    bool ok = false;
    
    for (int i = 1; i <= 3; ++ i) {
    	if ((a * b * i) & 1)
    		ok = true;
    }
    
    cout << (ok ? "Yes" : "No");
    
    cout << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	string c;
	cin >> c;
	if (c == "a" || c == "i" || c == "u" || c == "e" || c == "o") {
		cout << "vowel" << endl;
	}
	else {
		cout << "consonant" << endl;
	}
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>


using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;

struct edge_t
{
	int a, b, c;
	bool operator<(const edge_t&rhs) const
	{
		if(a>rhs.a) return false;
		if(a<rhs.a) return true;
		if(b>rhs.b) return false;
		if(b<rhs.b) return true;
		if(c>rhs.c) return false;
		if(c<rhs.c) return true;
		return false;
	}
};

int main(void)
{
	int l;

	while(scanf("%d", &l)==1)
	{
		int past=0;
		int n=1;
		vi v;
		vector<edge_t> ve;

		for(int i=0;i<19;i++)
		{
			int t=1<<i;
			if(t>=l) break;
			v.push_back(t);
			n++;
		}
		reverse(v.begin(), v.end());

//		for(int i=0;i<v.size();i++) printf("v[%d]=%d\n", i, v[i]);

		for(int i=0;i+1<v.size();i++)
		{
			ve.push_back(edge_t{i+2,i+3,v[i]/2});
			ve.push_back(edge_t{i+2,i+3,0});
		}

		int rest=l;
		for(;rest>0;)
		{
			for(int i=0;i<v.size();i++)
			{
				if(rest>=v[i])
				{
					ve.push_back(edge_t{1, i+2, past});
					past+=v[i];
					rest-=v[i];
					break;
				}
			}
		}
		sort(ve.begin(), ve.end());
		printf("%d %d\n", n, ve.size());
		for(auto&mve:ve)
		{
			printf("%d %d %d\n", mve.a, mve.b, mve.c);
		}
	}
	return 0;
}


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

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;

int main() {
    fast;
    cin.tie(0);
/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w" , stdout);
#endif*/
    lld n, k, i, j;
    cin >> n >> k;
    map<lld, lld> mp;
    lld cnt = 0;
    for (i = 0; i < k; i++) {
        lld d;
        cin >> d;
        lld a[d];
        for (j = 0; j < d; j++) {
            cin >> a[j];
            mp[a[j]]++;
        }
    }
    for (i = 1; i <= n; i++) {
        if (mp[i]) {

        }
        else cnt++;
    }
    cout << cnt << endl;

}

Measured memory_bytes: 3644
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x_max = max(x)
y_min = min(y)

for z in range(-99, 101):
    if X < z <= Y and x_max < z and y_min >= z:
        print("No War")
        break
else:
    print("War")


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>
#include <numeric>
#include <functional>
#include <stack>
#include <iomanip>
#include <map>
#include <cstdio>


int main() {
	long long a, b, n;

	std::cin >> a >> b >> n;

	long long c = std::min(b - 1, n);

	std::cout << a * c / b - a * (c / b) << std::endl;

	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

// 插入此處

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int N, X, Y; cin >> N >> X >> Y;
    vector<int> ans(N, 0);
    for (int i = 1; i <= N; ++i) {
        for (int j = i+1; j <= N; ++j) {
            int dist = min(j-i, abs(X-i) + abs(Y-j) + 1);
            ++ans[dist];
        }
    }
    for (int i = 1; i < N; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	int masu[13][13]={0},x,y,s;
	while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
		x+=2,y+=2;
		if(s==1){
			for(int i=x-1;i<=x+1;i++)masu[i][y]++;
			masu[x][y-1]++;
			masu[x][y+1]++;
		}else if(s==2){
			for(int i=x-1;i<=x+1;i++){
				for(int j=y-1;j<=y+1;j++){
					masu[i][j]++;
				}
			}
		}else{
			for(int i=x-1;i<=x+1;i++){
				for(int j=y-1;j<=y+1;j++){
					masu[i][j]++;
				}
			}
			masu[x-2][y]++,masu[x+2][y]++;
			masu[x][y-2]++,masu[x][y+2]++;
		}
	}
	int siro=0,koi=0;
	for(int i=2;i<=11;i++){
		for(int j=2;j<=11;j++){
			if(masu[i][j]==0)siro++;
			if(koi<masu[i][j])koi=masu[i][j];
		}
	}
	cout<<siro<<endl<<koi<<endl;
	return 0;
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
int n;
int main(){
	cin >> n;
	cout << 0 << endl;

	string pres;
	cin >> pres;
	if(pres == "Vacant")
		return 0;


	int l = 0,r = n;
	int cou = 0;
	while(1) {
		if(cou > 30)
			break;
		int m = (r + l) / 2;

		cout << m << endl;
		string s;
		cin >> s;
		if(s == "Vacant")
			break;
		int d = m - l;

		bool f;
		if(d % 2 == 0) {
			//equal
			if(s == pres) {
				f = true;
			}else{
				f = false;
			}
		}else{
			if(s == pres) {
				f = false;
			}else{
				f = true;
			}
		}

		if(f) {
			l = m;
			pres = s;
		}else{
			r = m;
		}
		cou++;
	}
	return 0;
}


Measured memory_bytes: 852
N = int(input())
X_ls = list(map(int, input().split(' ')))
rst = -1
for i in range(min(X_ls), max(X_ls) + 1):
    val = 0
    for j in X_ls:
        val += (i - j) ** 2
    if rst == -1:
        rst = val
    else:
        rst = min(rst, val)
print(rst)

Measured memory_bytes: 9020
#[allow(dead_code)]
fn is_whitespace(c: &char) -> bool {
    c.is_whitespace()
}

#[allow(dead_code)]
fn is_eol(c: &char) -> bool {
    ['\r', '\n'].contains(c)
}

#[allow(unused_macros)]
macro_rules! input {
    ($var:ident, $($r:tt)*) => {
        input_inner!{$var, $($r)*}
    };

    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        #[allow(unused_mut, unused_variables, bare_trait_objects)]
        let mut next = move |f: &Fn(&char)->bool| -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|f(&c))
                .take_while(|c|!f(&c))
                .collect()
        };
        input_inner!{next, $($r)*};
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; eol ]) => {
        $next(&is_eol).split(' ').map(|x| x.parse::<$t>().unwrap()).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, parser) => {
        $next
    };

    ($next:expr, $t:ty) => {
        $next(&is_whitespace).parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};

#[allow(dead_code)]
struct Edge {
    from: usize,
    to: usize,
}

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;
#[allow(dead_code)]
const M: usize = 1_000_000_007;

fn main() {
    input! {
        n: usize,
        m: usize,
    }
    let mut v = vec![];

    if n % 2 == 1 {
        let mut l = 1;
        let mut r = n - 1;
        while l < r {
            v.push((l, r));
            l += 1;
            r -= 1;
        }
    } else {
        let mut flag = false;
        let mut l = 1;
        let mut r = n - 1;
        while l < r {
            if !flag && r - l <= n / 2 {
                r -= 1;
                flag = true;
            }
            v.push((l, r));
            l += 1;
            r -= 1;
        }
    }
    for i in 0..m {
        println!("{} {}", v[i].0, v[i].1);
    }
}


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

int main() {
    int S, W;
    cin >> S >> W;
    puts(S <= W ? "unsafe" : "safe");
}

Measured memory_bytes: 3624
//package practice;

import java.util.*;

import java.io.*;
import java.math.*;

public class Main {
	
	
	public static void main(String args[]) throws Exception {
		Scanner scan = new Scanner(System.in);
		int L = scan.nextInt();
		double side = (double)L / 3;
		System.out.printf("%.12f", Math.pow(side, 3));
		

		
	}
}




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

const int MOD=1000000007;

long long Sum(int N, int k){
  return k*(N-k+1)+1;
}

int main(void){
  long long N,K;
  cin >> N >> K;
  
  long long ans=0;
  
  for (long long i=K; i<=N+1; i++){
    ans += i*(N-i+1)+1;
  }
  
  cout << ans % MOD << endl;
  
  
  return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
int main() {
  int ans=0;
  string s, t;
  cin >> s >> t;
  for(int i=0; i<s.size(); i++) {
    if(s.at(i)!=t.at(i)) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3920
#include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define o(a) cout<<a<<endl
using namespace std;

int main(){
	int h,w;
	while(1){
		cin>>h>>w;
		if(h==0&&w==0) break;
		char s[101][101];
		//vector<string> s(h);
		rep(i,0,h) rep(j,0,w) cin>>s[i][j];
		int y=0,x=0;
		bool f=0;
		//o(s[0][0]);
		for(int i=0;;i++){
			char c=s[y][x];
			//cout<<c<<endl;
			if(c=='>') x++;
			else if(c=='<') x--;
			else if(c=='^') y--;
			else if(c=='v') y++;
			else if(c=='.'){
				f=1; break;
			}
			//cout<<i<<endl;
			if(i>h*w) break;
		}
		if(f) cout<<x<<" "<<y<<endl;
		else cout<<"LOOP"<<endl;
	}
}

Measured memory_bytes: 1168
N = int(input())
A = list(map(int, input().split()))
B = []
flag = 0

for i in range(N//2):
    B.append((N-1) - (i*2))
    B.append((N-1) - (i*2))
if N % 2 == 1:
    B.append(0)
        
A.sort()
B.sort()
if A == B:
    print((2**(N//2)) % (1000000007))
else:
    print(0)

Measured memory_bytes: 13880
#include <stdio.h>

int main(void){
    int n;
    scanf("%d", &n);
    int ans = n * 2 - 3;

    for(int j = 2; j * j <= n; j++) {
        for(int i = j * j; i < n; i += j) {
            if(i == j * j) ans += 1;
            else if(i % j == 0) ans += 2;
        }
    }

    printf("%d\n", ans);
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
int main() {
  long a,b,c;
  cin>>a>>b>>c;
  if (a+b>c) cout<<"No"<<endl;
  else if (4*a*b<(c-a-b)*(c-a-b)) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

using namespace std;

double EPS = 1e-10;
const double PI = acos(-1);

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}

struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }

  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }

  point operator * (double d){
    return point(x*d,y*d);
  }

  point operator / (double d){
    return point(x/d,y/d);
  }
  
  bool operator == ( const point &p ) const {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

struct segment{
  point a,b;
};

double dot(point a, point b) {
  return (a.x * b.x + a.y * b.y);
}

double cross(point a, point b) {
  return (a.x * b.y - a.y * b.x);
}

double vec_abs(point a){
  return sqrt(a.x*a.x+a.y*a.y);
}

double dist(point a,point b){
  return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}

int ccw(point p0, point p1, point p2){
  point a = p1 - p0;
  point b = p2 - p0;
  if(cross(a,b)>EPS)return +1;
  if(cross(a,b)<EPS)return -1;
  if(dot(a,b)<-EPS)return +2;
  if(a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y)return -2;
  return 0;
}

vector<segment> construct_edge(point* p, int n){
  vector<segment>seg,seg2;
  segment temp;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i!=j){
	temp.a=p[i];
	temp.b=p[j];
	seg.push_back(temp);
      }
    }
  }

  int t=seg.size();
  for(int i=0;i<t;i++){
    int fg=0;
    for(int j=0;j<t;j++){
      if(i!=j && vec_abs(seg[i].b-seg[j].a)<=EPS){
	if(ccw(seg[i].a,seg[i].b,seg[j].b)==1){
	  fg=1;
	  break;
	}
      }
    }
    if(!fg)seg2.push_back(seg[i]);
  }
  return seg2;
}

/*
double areaPol(point* ps, int n){
  vector<segment>t=construct_edge(ps,n);

  int tsz=t.size();
  double area=0;
  for(int i=0;i<tsz;i++){
    area+=abs((t[i].a.x-t[i].b.x)*(t[i].a.y+t[i].b.y));
  }
  return abs(area)/2.0;
}
*/
/*
double areaPol(point* ps, int n){
  vector<segment>t=construct_edge(ps,n);

  int tsz=t.size();
  point c;
  c.x=c.y=0;
  for(int i=0;i<n;i++)c=c+ps[i];
  c=c/n;

  double area=0;
  for(int i=0;i<tsz;i++){
    double a=dist(t[i].a,t[i].b);
    double b=dist(t[i].a,c);
    double d=dist(t[i].b,c);
    double z=(a+b+d)/2;
    area+=sqrt(z*(z-a)*(z-b)*(z-d));
  }
  return area;
}
*/

int main(void){
  point p[21];
  int n=0;
  double x,y;
  char k;

  while(cin>>x>>k>>y){
    if(cin.eof())break;
    p[n].x = x;
    p[n].y = y;
    n++;
 }

  p[n]=p[0];
  double s;
  for(int j=0; j<n; j++) 
    s+=(p[j].x-p[j+1].x)*(p[j].y+p[j+1].y);


  printf("%.6f\n",abs(s/2));

  return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[] point = new Point[n];
        for (int i = 0; i < n; i++) {
            point[i] = new Point();
        }
        int[] index = new int[n - 1];
        
        // 自分に子を割り当てる
        for (int i = 0; i < n - 1; i++) {
            int p = sc.nextInt() - 1;
            int q = sc.nextInt() - 1;
            index[i] = q;   // 出力順を記憶する
            
            point[p].child.add(q);
        }
        
        point[0].color = 0;
        
        // 自分の子を若い色から塗る
        for (int i = 0; i < n; i++) {
            int nowColor = 1;
            int myColor = point[i].color;
            
            for (Integer children : point[i].child) {
                if (nowColor == myColor) {
                    nowColor++;
                }
                
                point[children].color = nowColor;
                nowColor++;
            }
        }
        
        // 必要な最小色数を出力
        int max = 0;
        for (Point p : point) {
            max = Math.max(max, p.color);
        }
        System.out.println(max);
        
        // 子の色を出力順に出力
        for (int i = 0; i < n - 1; i++) {
            System.out.println(point[index[i]].color);
        }
        
    }
    
    public static class Point {
        int color;
        List<Integer> child;
        
        Point() {
            this.child = new ArrayList<Integer>();
        }
    }
}


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

int main()
{
  int n;
  char judge[50];

  while(1)
  {
    int m, f, r;
      
    cin >> m >> f >> r;

    if(m == -1 && f == -1 && r == -1) break;

    if(m == -1 || f == -1)
    {
      judge[n] = 'F';
    }
    else
    {
      if(80 <= m + f)
      {
        judge[n] = 'A';
      }
      if(65 <= m + f && m + f < 80)
      {
        judge[n] = 'B';
      }
      if(50 <= m + f && m + f < 65)
      {
        judge[n] = 'C';
      }
      if(30 <= m + f && m + f < 50)
      {
        if(50 <= r)
        {
          judge[n] = 'C';
        }
        else
        {
          judge[n] = 'D';
        }
      }
      if(m + f < 30)
      {
        judge[n] = 'F';
      }
    }
      if(n < 50)
      {
        n++;
      }
      else
      {
        break;
    }
      
  }

  for(int i = 0; i < n; i++)
  {
    cout << judge[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3068
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<long long> a(N);
	auto sum = 0ll;
	for (auto i = 0; i < N; ++i)
	{
		cin >> a[i];
		sum += a[i];
	}

	auto temp = 0ll;
	auto result = LLONG_MAX;
	for (auto i = 0; i < N - 1; ++i)
	{
		temp += a[i];
		sum -= a[i];
		result = min(result, abs(temp - sum));
	}

	cout << result << endl;

	return 0;
}

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

const int N = 200010;
typedef long long ll;

ll dp[N][5];
int a[N];

void update(ll &a, ll b){
    if (a == -1 || a > b){
        a = b;
    }
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n + 1; ++ i){
        for (int j = 0; j <= 0; ++ j){
            if (dp[i - 1][j] != -1){
                update(dp[i][0], dp[i - 1][j] + a[i]);
            }
        }
        for (int j = 0; j <= 1; ++ j){
            if (dp[i - 1][j] != -1){
                update(dp[i][1], dp[i - 1][j] + (a[i] == 0 ? 2 : a[i] & 1));
            }
        }
        for (int j = 0; j <= 2; ++ j){
            if (dp[i - 1][j] != -1){
                update(dp[i][2], dp[i - 1][j] + !(a[i] & 1));
            }
        }
        for (int j = 0; j <= 3; ++ j){
            if (dp[i - 1][j] != -1){
                update(dp[i][3], dp[i - 1][j] + (a[i] == 0 ? 2 : a[i] & 1));
            }
        }
        for (int j = 0; j <= 4; ++ j){
            if (dp[i - 1][j] != -1){
                update(dp[i][4], dp[i - 1][j] + a[i]);
            }
        }
    }
    printf("%lld\n", dp[n + 1][4]);
    return 0;
} 

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

int main(){
  vector<int> price_a, price_b;
  int A, B, M, c, d, e, min_a, min_b,price;
    cin >> A >> B >> M;
    cin >> min_a;
    price_a.push_back(min_a);
  rep(i,A-1){
    cin >> c;
    price_a.push_back(c);
    min_a = min(min_a, c);
  }
  
  cin >> min_b;
  price_b.push_back(min_b);
  rep(i,B-1){
    cin >> c;
    price_b.push_back(c);
    min_b = min(min_b, c);
  }
  price = min_a + min_b;
  int x,y,kakaku;
  rep(i,M){
    cin >> x >> y >> c;
    kakaku = price_a.at(x-1) + price_b.at(y-1) - c;
    price = min(price,kakaku);
  }
  cout << price << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	string str[3];
	REP(i, 3) cin >> str[i];
	REP(i, 3) putchar(str[i][i]);
	puts("");
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  
  public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    if(N <= 999){
      System.out.println("ABC");
    }else{
      System.out.println("ABD");
    }
  }  
}

Measured memory_bytes: 35644
use proconio::input;

fn main() {
    input! {
      a: f64,
      b: f64,
      h: f64,
      m: f64,
    };
    // 針がそれぞれ1周の何％動いているかを求める
    let h: f64 = (h * 60.0 + m) / 720.0;
    let m: f64 = m / 60.0;
    // 差から 1 周の何％分開いているかを求める。(小さいほうの角度を使う)
    let p: f64 = (h - m).abs();
    let p = p.min(1.0 - p);
    // 角度にする
    let ang = p * 360.0;
    // ラジアンに変換する
    let rad: f64 = ang * std::f64::consts::PI / 180.0;
    // 余弦定理を使用する
    let ans = (a * a) + (b * b) - 2.0 * a * b * rad.cos();
    println!("{}", ans.sqrt());
}


Measured memory_bytes: 3096
#include<cstdio> 
int main(){
	int N,Y;
	scanf("%d%d",&N,&Y);
	for(int i=0;i<=N;i++)
		for(int j=0;i+j<=N;j++)
			if(i*10000+j*5000+(N-i-j)*1000==Y){
				printf("%d %d %d",i,j,N-i-j);
				return 0;
			}
	printf("-1 -1 -1");
}

Measured memory_bytes: 256
N = int(input())
tmp = list()
for i in range(N):
    s,p = input().split()
    tmp.append([s,int(p),i+1])
tmp = sorted(tmp, key = lambda x:x[1], reverse = 1)
tmp = sorted(tmp, key = lambda x:x[0])
tmp = [x[2] for x in tmp]
for i in range(N):
    print(tmp[i])

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

// 各iに対して文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか
// 計算量: O(|S|)
class KMP
{
public:
  string p;
  int plen;
  vector<int> mp;
  vector<int> kmp;

  /* MPとKMPの構築 計算量O(logN) */
  KMP(const string s) : p(s), plen((int)p.size()), mp(plen + 1), kmp(plen + 1)
  {
    mp[0] = kmp[0] = -1;
    int j = -1;
    for (int i = 0; i < plen; i++)
    {
      while (j >= 0 && p[i] != p[j])
        j = kmp[j];

      kmp[i + 1] = mp[i + 1] = ++j;

      if (i + 1 < plen && p[i + 1] == p[j])
        kmp[i + 1] = kmp[j];
    }
  }

  //文字列patternのS[0~i]の最小の周期長を求める
  //計算量:O(N)
  vector<int> cycle()
  {
    vector<int> res(plen);
    for (int i = 0; i < plen; i++)
    {
      res[i] = i - kmp[i];
    }
    return res;
  }

  /* MPを使った文字列検索 */
  vector<int> search(const string &text)
  {
    vector<int> res;
    int i, j;
    int tlen = text.size();

    i = j = 0;
    while (j < tlen)
    {
      while (i > -1 && p[i] != text[j])
        i = kmp[i];

      i++;
      j++;
      if (i >= plen)
      {
        res.push_back(j - i);
        i = kmp[i];
      }
    }
    return res;
  }
};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  string text, pattern;
  cin >> text >> pattern;

  KMP kmp(pattern);
  auto v = kmp.search(text);
  for (auto e : v)
  {
    cout << e << endl;
  }
}
//参考
// https://snuke.hatenablog.com/entry/2014/12/01/235807(MP法)

// http://www-igm.univ-mlv.fr/~lecroq/string/node8.html(KMP法)
// https://potetisensei.hatenablog.com/entry/2017/07/10/174908(KMP法)


Measured memory_bytes: 8896
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = vec![
        1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4,
        1, 51,
    ];
    let k = read::<usize>() - 1;
    println!("{}", v[k]);
}

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M,s,c;
    cin >> N >> M;
    int a[N+1];
    int b[N+1];
    for(int i=1;i<=N;i++)
	{
		a[i]=0;
		b[i]=0; 
	}
    for(int i=1;i<=M;i++){
        cin >> s>>c;
        if(N>1&&s==1&&c==0){
            cout << -1;
            return 0;
        }
        if(b[s]==0)
        {
            a[s]=c;
			b[s]=1;
        }
        else if(c!=a[s])
		{
			cout<<"-1"<<endl;
			return 0;
		}

    }
	if(N>1&&a[1]==0)
	{
		a[1]=1;
	}    
    for(int i=1;i<=N;i++){
        cout <<a[i];
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for(int i=0; i<N; i++)
    cin >> H[i];
  int tmpMax = -1;
  int ans = 0;
  for(int i=0; i<N; i++) {
    if(tmpMax <= H[i]) {
      ans++;
      tmpMax = H[i];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
#define MOD 1000000007
#define int long long

signed main(){
    int h,w;cin>>h>>w;
    rep(i,h)rep(j,w){
        string s;cin>>s;
        if(s=="snuke"){
            cout<<(char)('A'+j)<<i+1<<endl;
        }
    }
}

Measured memory_bytes: 256
<?php
//その都度計算しているとTLEになるので、最初に$max値で計算
 
$max = 1000000;
 
// 配列の初期化。素数には１が入る。ここがポイント。
for ($i = 0; $i < $max; $i++) {
    $array[$i] = 1;
}
$array[1] = 0;
 
// ふるい。０と１は素数では無いので２から探索開始
for ($i=2; $i<$max; $i++) {
  if ( $array[$i]===0 )
    // スタート値がふるい落とされていたら、その倍数も既出
    continue;
  else
    // $i自身は素数なので除外。$i*$i未満の組み合わせは既出なので除外。
    for ($j=$i*$i; $j<$max; $j+=$i) {
      $array[$j] = 0;
    }
}
 
// 各整数にそれ以下の素数の総数を格納。ここがポイント。
for ($i=2; $i<$max; $i++){
  $array[$i] += $array[$i-1];   //素数ならば１が入っているのでカウンターとして使う。
}
 
while(1){
  $res = fscanf(STDIN, '%d', $n);
  if ($res==0) break;
 
  $cnt = $array[$n];
 
  // 出力
  echo $cnt.PHP_EOL;
}

Measured memory_bytes: 147520
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
l = list(reversed(l))
total = 0
count = 0
for a, b in l:
  a += total
  if a % b == 0:
    continue
  
  temp = b - a % b
  count += temp
  total += temp

print(count)

Measured memory_bytes: 28148
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll a,b,n;
	cin>>a>>b>>n;
	ll z=min(n,b-1);
	cout<<(a*z)/b<<"\n";
	return 0;
}

Measured memory_bytes: 3652
use proconio::input;

fn main() {
    input!(n: usize, k: usize, xyc: [(usize, usize, char); n]);
    let mut geta = 0;
    let mut grid = vec![vec![0; 4 * k + 1]; 4 * k + 1];
    for (x, y, c) in xyc {
        let weight = match c {
            'W' => 1,
            'B' => {
                geta += 1;
                -1
            }
            _ => panic!(),
        };
        for (x, y) in [
            (x % (2 * k), y % (2 * k)),
            ((x + k) % (2 * k), (y + k) % (2 * k)),
        ]
        .iter()
        {
            for qx in 0..2 {
                for qy in 0..2 {
                    grid[qx * 2 * k + x + 1][qy * 2 * k + y + 1] += weight;
                }
            }
        }
    }

    for i in 0..=4 * k {
        for j in 0..=4 * k {
            if 0 < i {
                grid[i][j] += grid[i - 1][j];
            }
            if 0 < j {
                grid[i][j] += grid[i][j - 1];
            }
            if 0 < i && 0 < j {
                grid[i][j] -= grid[i - 1][j - 1];
            }
        }
    }

    println!(
        "{}",
        geta + (0..2 * k)
            .map(|i| {
                (0..2 * k)
                    .map(|j| grid[i + k][j + k] - grid[i + k][j] - grid[i][j + k] + grid[i][j])
                    .max()
                    .unwrap()
            })
            .max()
            .unwrap()
    );
}


Measured memory_bytes: 69204
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>


int main(void)
{	
	int n;
	scanf("%d",&n);
	
	if(n==1){
		printf("1\n");
	} else if(n>=2 &&n<=3){
		printf("2\n");
	} else if(n>=4 && n<=7){
		printf("4\n");
	} else if(n>=8 && n<=15){
		printf("8\n");
	} else if(n>=16 && n<=31){
		printf("16\n");
	} else if(n>=32 && n<=63){
		printf("32\n");
	} else if(n>=64 && n<=100){
		printf("64\n");
	}
	return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		bool flag = i % 3 == 0;
		stringstream ss;
		ss << i;
		string s = ss.str();
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == '3')flag = true;
		}
		if (flag)cout << " " << i;
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
const int inf = 1e9+7;
const int INF = 1e18+7;

int a[30];
signed main(){
	string str;
	cin >> str;
	int n = str.size();
	rep(i,n){
		a[str[i]-'a']++;
	}
	int ans = 0;
	rep(i,26)ans += a[i]*(a[i]-1)/2;
	printf("%lld\n", n*(n-1)/2-ans+1);
	return 0;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    long n;
    cin>>n;
    long x=n,sum=0;
    while(x>0){
        sum+=x%10;
        x/=10;
    }
    if(n%sum==0) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int A,B;
  cin >> A >> B;
  if(A>=13)
  {
    cout << B << endl;
  }
  else if(A<=5)
  {
    cout << 0 << endl;
  }
  else
  {
    cout << B/2 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a, b, c, x, y;
int main()
{
#ifdef _noname
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	cin >> a >> b >> c >> x >> y;
	long long ans = 2LL * c * max(x, y);
	if (x > y) ans = min(ans, 1LL * c * y * 2 + 1LL * a * (x - y));
	else ans = min(ans, 1LL * c * x * 2 + 1LL * b * (y - x));
	ans = min(ans, 1LL * a * x + 1LL * b * y);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;typedef long long ll;typedef vector<ll> vl;typedef vector<vl> vvl;typedef pair<ll,ll> pl;typedef vector<pl> vp;const ll INF=1001001001;const ll LINF=1001001001001001001;const ll D4[]={0,1,0,-1,0};const ll D8[]={0,1,1,0,-1,-1,1,-1,0};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;}
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()

void solve(long long K){
    if(K<10){
        cout<<K<<endl;
        return;
    }

    vl a;
    fore(i,1,9)a.push_back(i);
    K-=9;

    while(1){
        vl nxt;
        for(ll x:a){
            ll d=x%10;
            fore(i,-1,1){
                if(d+i<0||d+i>9)continue;
                nxt.push_back(x*10+d+i);
                K--;
                if(!K){
                    cout<<x*10+d+i<<endl;
                    return;
                }
            }
        }
        a=nxt;
    }
}

int main(){
    long long K;
    scanf("%lld",&K);
    solve(K);
}


Measured memory_bytes: 1152
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
#include <numeric>

template <typename C>
void print_container(const C &c, const std::string &name)
{
  std::cout << name << ": ";
  std::for_each(c.cbegin(), c.cend(),
                [](auto &x) { std::cout << x << ", "; });
  std::cout << std::endl;
}

int main()
{
  int N, M;
  std::cin >> N >> M;
  std::vector<uint64_t> A(N), B(M), C(M);
  for(int i=0; i<N; i++) {
    std::cin >> A[i];
  }
  for(int i=0; i<M; i++) {
    std::cin >> B[i] >> C[i];
  }

  std::sort(A.begin(), A.end(), std::less<int>());
  std::vector<size_t> argsort(M);
  for(int i=0; i<M; i++) {
    argsort[i] = i;
  }

  // argsort C
  std::sort(argsort.begin(), argsort.end(),
            [&C](auto lhs, auto rhs) -> bool {
              return C[lhs] > C[rhs];
            });
  // print_container(argsort, "argsort");

  size_t j = 0;
  bool do_fin = false;
  for(size_t i : argsort) {
    uint64_t b = B[i];
    uint64_t c = C[i];
    uint64_t n_replaced = 0;

    while(j<N) {
      // std::cout << "j: " << j << std::endl;
      if(A[j] >= c) {
        do_fin = true;
        break;
      }

      A[j] = c;
      n_replaced++;
      j++;

      if(n_replaced == b) break;
    }

    if(do_fin) break;
  }

  // print_container(A, "A");
  uint64_t sum = std::accumulate(A.begin(), A.end(), 0ULL);

  std::cout << sum << std::endl;
  return 0;
}


Measured memory_bytes: 6404