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

using namespace std;

int calc(int a, int b, int c, int x, int y) {
  int ret = a * x + b * y;
  for (int z = 2;; z += 2) {
    int const candidate =
        a * std::max(x - z / 2, 0) + b * std::max(y - z / 2, 0) + c * z;
    if (candidate >= ret) {
      break;
    }
    ret = candidate;
  }
  return ret;
}

int main() {
  int a, b, c, x, y;
  std::cin >> a >> b >> c >> x >> y;
  std::cout << calc(a, b, c, x, y) << std::endl;
  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))

res = 0
for d in range(40, -2, -1):
    
    if d != -1 and (K & 1 << d) == 0:
        continue

    tmp = 0
    for e in range(40, -1, -1):
        # 上位桁から見ていく。
        # 1回目のループで50桁目の1の数、2回目では49桁目の1の数、、、
        # という風に見ていきたいので、そのためのマスクを作成
        mask = 1 << e
        num = 0

        # Aの各要素について1になっている数を調べる
        for i in range(N):
            if A[i] & mask:
                num += 1
        if e > d:
            # マスクにはe桁目にのみ1が立っている
            # Kのe桁目が1の時のみAの各要素の0の数だけ値を加算
            if K & mask:
                tmp += mask * (N - num)
            else:
                tmp += mask * num
        elif e == d:
            tmp += mask * num
        # e < dの時、1と0の数を比べて多い方の値を加算
        else:
            tmp += mask * max(num, N - num)

    res = max(res, tmp)

print(res)


Measured memory_bytes: 69264
def calculate(n,m,arr,p):
    total = 0
    for i in range(2**n):
        #某一种情况

        check = [False for i in range(m)]
        for indexOfBlub in range(len(arr)):
            # 第几个灯泡
            onNumOfTheBlub = 0
            for indexOfSwitch in range(len(arr[indexOfBlub])):
                if i >> (arr[indexOfBlub][indexOfSwitch] - 1) & 1:
                    onNumOfTheBlub += 1

            # 该灯泡所有的switch都循环结束以后，统计on的数量是否和给定的一样

            if onNumOfTheBlub % 2 == p[indexOfBlub]:
                check[indexOfBlub] = True

        if all(check):
            total += 1

    return total

n = 5
m = 2

S = input()
S = S.split(" ")
n = int(S[0])
m = int(S[1])


inputArr = []


for i in range(m):
    S = input()
    inputArr.append([int(s) for s in S.split(" ")][1:])

S = input()
inputP = [int(s) for s in S.split(" ")]


res = calculate(n,m,inputArr,inputP)

print(res)

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

using namespace std;

typedef pair<int,int> pi;

const int mod = 1e9+7;
const int maxn = 200010;

int n, C = 1, ans = 0;
pi a[maxn];
int b[maxn], sum[maxn<<2], cnt[maxn<<2], K[maxn<<2];

int qpow(int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) ret = 1LL * ret * x % mod;
		x = 1LL * x * x % mod;
		y >>= 1;
	}
	return ret;
}

void pushUp(int rt) {
	sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % mod;
	cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
}

void modify(int rt, int k) {
	sum[rt] = 1LL * sum[rt] * k % mod;
	K[rt] = 1LL * K[rt] * k % mod;
}

void pushDown(int rt) {
	if (K[rt] != 1) {
		modify(rt<<1, K[rt]);
		modify(rt<<1|1, K[rt]);
		K[rt] = 1;
	}
}

void update(int p, int v, int l, int r, int rt) {
	if (l == r) {
		sum[rt] = (sum[rt] + v) % mod;
		cnt[rt] ++;
		return;
	}
	pushDown(rt);
	int m = (l + r) >> 1;
	if (p <= m) update(p, v, l, m, rt<<1);
	else update(p, v, m+1, r, rt<<1|1);
	pushUp(rt);
}

int query(int L, int R, int l, int r, int rt) {
	if (L > R) return 0;
	if (L <= l && r <= R) return sum[rt];
	int ret = 0;
	pushDown(rt);
	int m = (l + r) >> 1;
	if (L <= m) ret = (ret + query(L, R, l, m, rt<<1)) % mod;
	if (R > m) ret = (ret + query(L, R, m+1, r, rt<<1|1)) % mod;
	return ret;
}

int query_cnt(int L, int R, int l, int r, int rt) {
	if (L > R) return 0;
	if (L <= l && r <= R) return cnt[rt];
	int ret = 0;
	int m = (l + r) >> 1;
	if (L <= m) ret = ret + query_cnt(L, R, l, m, rt<<1);
	if (R > m) ret = ret + query_cnt(L, R, m+1, r, rt<<1|1);
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].first);
		a[i].second = i;
	}
	sort(a+1, a+n+1);
	for (int i = 1; i <= n; i++) {
		if (a[i].first-i+1 <= 0) {
			puts("0");
			return 0;
		}
		b[i] = 1LL*(a[i].first-i)*qpow(a[i].first-i+1, mod-2)%mod;
	}
	for (int i = 1; i <= n; i++) C = 1LL * C * (a[i].first-i+1) % mod;
	for (int i = 1; i <= n; i++) {
		int v = 1LL*(mod+1)/2*C%mod*qpow(a[i].first-i+1, mod-2)%mod;
		ans = (ans + 1LL*v*query(1, a[i].second-1, 1, n, 1)%mod)%mod;
		ans = ((ans + 1LL*C*query_cnt(a[i].second+1, n, 1, n, 1)%mod)%mod+mod-1LL*v*query(a[i].second+1, n, 1, n, 1)%mod)%mod;
		K[1] = 1LL * K[1] * b[i] % mod;
		update(a[i].second, a[i].first-i, 1, n, 1);
	}
	printf("%d\n", ans);
	return 0;
}

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

int main() {
  int E,Y,s,r;
  cin>> E >> Y;
  
  if(E==0&&Y<=1911&&Y>=1868){
    s=Y-1867;
    cout<< "M" << s <<endl;
  } else if(E==0&&Y<=1925&&Y>=1912){
     s=Y-1911;
     cout<< "T" << s <<endl;
   } else if(E==0&&Y<=1988&&Y>=1926){
     s=Y-1925;
     cout<< "S" << s <<endl;
   } else if(E==0&&Y<=2016&&Y>=1989){
     s=Y-1988;
     cout<< "H" << s <<endl;
   }
  if(E==1){
    r=1867+Y;
    cout<< r <<endl;
  } 
  if(E==2){
    r=1911+Y;
    cout<< r <<endl;
  } 
  if(E==3){
    r=1925+Y;
    cout<< r <<endl;
  } 
  if(E==4){
    r=1988+Y;
    cout<< r <<endl;
  } 
  
  return 0;
  
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  double ret=0;
  for(int i = 1; i <= a; i++) {
    double tmp = 1.0 / a;
    int now = i;
    while (now < b) {
      now *= 2;
      tmp /= 2;
    }
  ret += tmp;
  }
  printf("%.12f\n", ret);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

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

    int N; cin >> N;
    vector<int> A(N),B(N);
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];

    vector<int> ca(N + 1,0),cb(N + 1,0);
    rep(i,N){
        ca[A[i]]++;
        cb[B[i]]++;
    }
    rep(i,N) {
        if (ca[i+1] + cb[i+1] > N) {
            cout << "No" << '\n';
            return 0;
        }
    }

    reverse(B.begin(),B.end());
    int l = -1;
    int x = -1;
    rep(i,N) {
        if (A[i] == B[i]) {
            l = i;
            x = A[i];
            break;
        }
    }
    if (l < 0) {
        cout << "Yes" << '\n';
        rep(i,N) cout << B[i] << ' ';
        cout << '\n';
        return 0;
    }

    int r = N - 1;
    while (B[r] == x || A[r] == x) --r;
    while (l < N && A[l] == B[l]) {
        swap(B[l],B[r]);
        --r;
        while (B[r] == x || A[r] == x) --r;
        ++l;
    }
    cout << "Yes" << '\n';
    rep(i,N) cout << B[i] << ' ';
    cout << '\n';
    return 0;
}

Measured memory_bytes: 6376
#include <iostream>
using namespace std;
int N,a[10];
bool ans;
bool test(int i){
	int b=0,c=0;
	for(int j=0;j<10;j++){
		if(i>>j&1){
			if(b>a[j])return false;
			else b=a[j];
		}else{
			if(c>a[j])return false;
			else c=a[j];
		}
	}
	return true;
}
int main()
{
    cin>>N;
	while(N--){
		ans=false;
		for(int i=0;i<10;i++)cin>>a[i];
		for(int i=0;i<1<<10;i++){
			if(test(i)){
				ans=true;
				break;
			}
		}
		if(ans)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
    return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>
int main(){
int a,b,c,d,n,x=0,count=0;

while((scanf("%d",&n))!=EOF){
for(a=0;a<=9;a++){
for(b=0;b<=9;b++){
for(c=0;c<=9;c++){
for(d=0;d<=9;d++){
x=a+b+c+d;
if(x==n){
count++;
}
}
}
}
}
printf("%d\n",count);
count=0;
x=0;
}
return 0;
}

Measured memory_bytes: 596
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};
#[allow(unused_imports)] use superslice::Ext as _;

#[proconio::fastout]
fn main() {
	input! {
		n: usize,
		mut a: [usize; n],
	}

	let mut ans = 0;
	for i in 0..n {
		ans += a[i] - 1;
	}

	println!("{}", ans);
}


Measured memory_bytes: 2184
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf=1e9+7;
int main()
{
	ll n,val,i,j,k,c,s=0;
	string ss;
	cin>>k>>n;
	vector<ll> v;
	for(i=0;i<n;i++)
	{
		ll a;
		cin>>a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	vector<ll> vv;
	for(i=0;i<n-1;i++)
	{
		vv.push_back(abs(v[i]-v[i+1]));
	}
	vv.push_back(abs((k-v[n-1])+v[0]));
	sort(vv.rbegin(),vv.rend());
	cout<<k-vv[0];
}

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

using i64 = int64_t;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> graph(n, vector<int>(n));
    for(int i=0;i<n;++i){
        int u, k;
        cin >> u >> k;
        for(int j=0;j<k;++j){
            int v;
            cin >> v;
            graph[u-1][v-1] = 1;
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(j)cout << " ";
            cout << graph[i][j];
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3208
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def min(a,b)
    return a>b  ? b : a
end
N=gets.to_i
B=get_i
ans=array(N)
ans[0]=B[0]
ans[-1]=B[-1]
1.upto(N-2) do|i|
    ans[i]=min(B[i-1],B[i])
end
puts ans.inject(:+)

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

int main(){
    int N,M;cin>>N>>M;
    vector<long> A(N);
    for(int i = 0; i < N ; i++){
        cin >> A[i];
    }
    vector<pair<long,int>> pick(M);
    for(int i = 0 ; i < M ; i++){
        int b;
        long c;cin >> b >> c;
        pick[i].first = c;
        pick[i].second = b;
    }
    sort(pick.rbegin(),pick.rend());
    sort(A.begin(),A.end());

    queue<pair<long,int>> que;

    for(auto e : pick){
        que.push(e);
    }
    int i = 0;
    bool flag = true;
    while(flag && !que.empty()){
        pair<long,int> p;
        p = que.front();
        int k = p.second;
        que.pop();
        while(k>0&&i<N){
            if(A[i] >= p.first){
                flag = false;
                break;
            }else{
                A[i] = p.first;
                i++;
                k--;
            }
            
        }
    }
    long ans = 0;
    for(auto e : A){
        ans += e;
    }
    cout << ans << endl;

}

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

int main() {
	long long n;
	long long m;
	long long ans = 0;
	cin >> n;

	for (long long i = 1; i < sqrt(n); i++) {
		if (n % i == 0) {
			m = (n / i) - 1;
			if (n % m == n / m) {
				ans += m;
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), m = scanner.nextInt(), q = scanner.nextInt();
			int[] a = new int[q], b = new int[q], c = new int[q], d = new int[q];
			IntStream.range(0, q).forEach(i -> {
				a[i] = scanner.nextInt() - 1;
				b[i] = scanner.nextInt() - 1;
				c[i] = scanner.nextInt();
				d[i] = scanner.nextInt();
			});
			System.out.println(calcMax(n, m, q, a, b, c, d));
		}
	}

	/**
	 * 得点の最大値を計算する
	 * 
	 * @param n 数列の数字の数
	 * @param m 数列の数字の最大値
	 * @param q 条件の組み数
	 * @param a 条件aの配列
	 * @param b 条件bの配列
	 * @param c 条件cの配列
	 * @param d 条件dの配列
	 * @return 得点の最大値
	 */
	private static int calcMax(final int n, final int m, final int q, final int[] a, final int[] b, final int[] c,
			final int[] d) {
		int[] array = new int[n];
		Arrays.fill(array, 1);
		int result = 0;
		while (array[0] <= m) {
			result = Math.max(result, calc(array, q, a, b, c, d));
			increase(array, n, m, n - 1);
		}
		return result;
	}

	/**
	 * 配列の得点を計算する
	 * 
	 * @param array 配列
	 * @param q     条件の組み数
	 * @param a     条件aの配列
	 * @param b     条件bの配列
	 * @param c     条件cの配列
	 * @param d     条件dの配列
	 * @return 配列の得点
	 */
	private static int calc(final int[] array, final int q, final int[] a, final int[] b, final int[] c,
			final int[] d) {
		return IntStream.range(0, q).filter(i -> array[b[i]] - array[a[i]] == c[i]).map(i -> d[i]).sum();
	}

	/**
	 * 配列のindex番を一つ上がる
	 * 
	 * @param array 配列
	 * @param n     数列の数字の数
	 * @param m     数列の数字の最大値
	 * @param index 上がるインデックス
	 */
	private static void increase(int[] array, final int n, final int m, final int index) {
		array[index]++;
		if ((array[index] > m) && (index > 0)) {
			increase(array, n, m, index - 1);
			array[index] = array[index - 1];
		}
	}
}


Measured memory_bytes: 56080
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int r;
    cin >> r;
 
    cout << 2*M_PI*r << "\n";
}

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

const string YES = "Yes";
const string NO = "No";

void solve(std::string S){
	cout << ((S[2] == S[3] && S[4] == S[5]) ? "Yes" : "No") << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<vector>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<utility>
#include<climits>
#include<set>
using namespace std;
#define ll long long


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

	ll n;cin>>n;
	vector<ll> v(n);
	for(int i=0;i<n;i++)
		cin>>v[i];
	ll ans=0;
	int modul=1'000'000'007;
	ll sum=0;
	ll x=0;

	for(int i=0;i<n;i++)
	{
		ans=(ans + v[i]*x)%modul;
		x=(x + v[i])%modul;
	}
	cout<<ans%modul;
    
}

Measured memory_bytes: 4704
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
void init_fact(){
	kaijo[0]=1;
	for(int i=1;i<=2000000;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(!kaijo[0])init_fact();
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int inv(int x){
	x=modpow(x,MOD-2);
	return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
double dist(double ax,double ay,double bx,double by){
	return sqrt((bx-ax)*(bx-ax)+(ay-by)*(ay-by));
}
int h,w,k,now=1,cnt[310],ans[310][310];
char c[310][310];
signed main(){
	cin>>h>>w>>k;
	rep(i,h){
		rep(j,w){
			cin>>c[i][j];
			if(c[i][j]=='#')cnt[i]++;
		}
	}
	rep(i,h){
		if(cnt[i]==0){
			if(i){
				rep(j,w){
					ans[i][j]=ans[i-1][j];
					cout<<ans[i][j]<<(j==w-1?"\n":" ");
				}
			}
			else{
				int nw=0;
				while(1){
					nw++;
					if(cnt[nw]){
						rep(j,w){
							ans[nw][j]=now;
							//cout<<now<<(j==w-1?"\n":" ");
							if(c[nw][j]=='#'){
								cnt[nw]--;
								if(cnt[nw])now++;
							}
							if(j==w-1)now++;
						}
						rep(i,nw+1){
							rep(j,w){
								cout<<ans[nw][j]<<(j==w-1?"\n":" ");
							}		
						}
						i=nw;
						break;
					}
				}
				
			}
		}
		else{
			rep(j,w){
				ans[i][j]=now;
				cout<<now<<(j==w-1?"\n":" ");
				if(c[i][j]=='#'){
					cnt[i]--;
					if(cnt[i])now++;
				}
				if(j==w-1)now++;
			}
		}
	}
	
	return 0;
}


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

int main(void){
    int n;
    cin >> n;

    int h;
    ll ans = 0;
    cin >> h;
    for(int i=0;i<n-1;i++){
        int nh;
        cin >> nh;
        if(nh>=h) h = nh;
        else ans += (h-nh);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
N=int(input())
a=list(map(int,input().split()))

A=[0]*N
sum=0
b=[]

for i in range(N,0,-1):
    #print(i)
    count=0
    for j in range(i-1,N,i):
        count+=A[j]
    if count%2==a[i-1]:
        pass
    else:
        A[i-1]=1
        sum+=1
        b.append(i)

print(sum)
if len(b)!=0:
    print(" ".join(map(str,b)))


Measured memory_bytes: 19808
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


int main(){FIN
    ll a,b;cin>>a>>b;
    vll s(3);
    s[0] = a+b;
    s[1] = a-b;
    s[2] = a*b;
    cout<<*max_element(ALL(s))<<endl;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <tuple>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

struct func {
  long long a, b;
  long long operator () (long long x) const {
    return a * x + b;
  }
};

constexpr long long inf = (1 << 30) - 1;

int main() {
  int N;
  long long T;
  std::cin >> N >> T;
  ++T;
  std::vector<func> former, latter;
  for (int i: range(0, N)) {
    func f;
    std::cin >> f.a >> f.b;
    ++f.a; ++f.b;
    (f.a > 1 ? former : latter).push_back(f);
  }
  std::sort(former.begin(), former.end(), [](auto x, auto y) {
    return (x.a - 1) * y.b > (y.a - 1) * x.b;
  });
  std::vector<long long> dp(50, inf);
  dp[0] = 1;
  for (auto f: former) {
    for (int i: revrange(0, 50)) {
      if (dp[i] == inf) continue;
      chmin(dp[i + 1], f(dp[i]));
    }
  }
  std::sort(latter.begin(), latter.end(), [](auto x, auto y) {
    return x.b < y.b;
  });
  std::vector<long long> sum(latter.size() + 1);
  for (int i: range(0, latter.size())) {
    sum[i + 1] = sum[i] + latter[i].b;
  }
  int ans = 0;
  for (int i: range(0, 50)) {
    if (dp[i] > T) continue;
    chmax(ans, i + std::upper_bound(sum.begin(), sum.end(), T - dp[i]) - sum.begin() - 1);
  }
  std::cout << ans << '\n';
  return 0;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> field(H,vector<char>(W));
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
    cin >> field.at(i).at(j);
  }}
  // なんか判定してくれる処理
  vector<int> ansH(H,-1),ansW(W,-1);
  for (int i=0;i<H;i++){
    bool flag=false;
    for (int j=0;j<W;j++){
      if (field.at(i).at(j)=='#'){
        flag=true;
        break;
      }}
    if (flag){
      ansH.at(i)=i;
    }
  }
  for (int i=0;i<W;i++){
    bool flag=false;
    for (int j=0;j<H;j++){
      if (field.at(j).at(i)=='#'){
        flag=true;
        break;
      }}
    if (flag){
      ansW.at(i)=i;
    }
  }
  int maxW;
  maxW=*max_element(ansW.begin(),ansW.end());
  // がんばって出力
  for (int i:ansH){
    for (int j:ansW){
      if(i!=-1 and j!=-1){
        cout << field.at(i).at(j);
        if(j==maxW){
          cout << endl;
      }}
    }
  }
}

Measured memory_bytes: 256
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int iNum = sc.nextInt();
    sc.nextLine();
    String sStr = sc.nextLine();
    String[] sSplitStr = sStr.split(" ");
    String s1 = sSplitStr[0];
    String s2 = sSplitStr[1];
    String[] s1Split = s1.split("");
    String[] s2Split = s2.split("");
    List<String> listStr = new LinkedList<String>();
    for (int i = 0; i < iNum; i++) {
      listStr.add(s1Split[i]);
      listStr.add(s2Split[i]);
    }
    StringBuilder sb = new StringBuilder();
    for (String str : listStr) {
      sb.append(str);
    }
    System.out.printf(sb.toString());
  }
}


Measured memory_bytes: 21332
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////

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

	vector<ll> a(N);

	ll s = 0;

	rep(i, N) {
		cin >> a[i];
		s += a[i];
	}

	ll ans = 0;

	ll dif = abs(s - a[0] * N);

	rep(i, N) {
		if (dif > abs(s - a[i] * N)) {
			ans = i;
			dif = abs(s - a[i] * N);
		}
	}

	cout << ans;

	system("PAUSE");
}


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


  
int main(){
  int a,b,c,d,e;
  cin>>a>>b>>c>>d>>e;
  
  int x,y,z,v,w;
  x=((a+9)/10)*10;
  y=((b+9)/10)*10;
  z=((c+9)/10)*10;
  v=((d+9)/10)*10;
  w=((e+9)/10)*10;
  
  int loss1,loss2,loss3,loss4,loss5;
  
  loss1=x-a;
  loss2=y-b;
  loss3=z-c;
  loss4=v-d;
  loss5=w-e;
  
  int m;
  
  m=max(max(max(max(loss1,loss2),loss3),loss4),loss5);
  
  cout<<x+y+z+v+w-m<<endl;
  
  
  
  
    
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[200001];
int main()
{
        long long sum,ans;
        sum=ans=0;
        scanf("%s",a);
        for(long long i=0;i<strlen(a);i++)
        {
                if(a[i]=='B')
                        sum++;
                else
                        ans+=sum;
        }
        printf("%lld",ans);
        return 0;
}


Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

		BufferedReader br =
				new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null) {
			String[] str = line.split(",");
			int number = Integer.parseInt(str[0]);
			double weight = Double.parseDouble(str[1]);
			double high = Double.parseDouble(str[2]);
			double bmi = weight / (high * high);
			if (bmi >= 25) System.out.println(number);
			line = null;
		}

	}

}

Measured memory_bytes: 16920
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define vii vector<pair<int,int> >
#define vi vector<ll>
#define ll long long
#define rep(i,a,b) for(i=a;i<=b;i++)
#define inf 100000000000000000

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s,t;
    cin>>s>>t;
    int l1=s.length();
    int l2=t.length();
    int dp[l2+1][l1+1];
    for(int i=0;i<=l1;i++)
    {
        dp[0][i]=0;
    }
    for(int i=1;i<=l2;i++)
    {
        dp[i][0]=0;
    }
    for(int i=1;i<=l2;i++)
    {
        for(int j=1;j<=l1;j++)
        {
            if(t[i-1]==s[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
                //cout<<s[j-1]<<endl;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    // for(int i=1;i<=l2;i++)
    // {
    //     for(int j=1;j<=l1;j++)
    //     {
    //         cout<<dp[i][j]<<" ";       
    //     }
    //     cout<<endl;
    // }
    //cout<<dp[l2][l1]<<endl;
    vector<char> v;
    int i=l2,j=l1;
    while(i>0 && j>0)
    {
        //cout<<dp[i][j]<<" "<<s[j-1]<<endl;
        if(dp[i][j]==dp[i-1][j])
        {
            i--;
        }
        else if(dp[i][j]==dp[i][j-1])
        {
            j--;
        }
        else{
            v.pb(s[j-1]);
            //cout<<s[i-1]<<endl;
            i--;
            j--;
        }
    }
    reverse(v.begin(),v.end());
    for(int k=0;k<v.size();k++)
    {
        cout<<v[k];
    }
    cout<<endl;
    return 0;
}

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

int main()
{
	long long a,b,m,n,d,e,f,i,c,k;
	while(cin>>a>>b)
	{
		if(a<b)
		{
			d=a;
			a=b;
			b=d;
		}
		e=a;
		f=b;
		c=a%b;
		 while (c!=0)   
         {
		 	a=b;
		 	b=c;
		 	c=a%b;
		  }
		n=b;
		k=(e*f)/n;
		m=k;
		cout<<n<<" "<<m;
		cout<<endl;
	}
	return 0;
 } 

Measured memory_bytes: 3080
N, M = gets.split.map(&:to_i)
AB = M.times.map { gets.split.map(&:to_i) }

sorted = AB.sort_by { |a, b| [a, -b] }
right = -(1 << 60)
removed_count = 0
sorted.each do |a, b|
  if a >= right
    removed_count += 1
    right = b
  elsif b < right
    right = b
  end
end
puts removed_count

Measured memory_bytes: 14072
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000+7;

//マクロ
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<long long, long long> 
#define vin(v,N) for(int i=0;i<N;i++) cin>>v.at(i)
#define pb push_back

//関数
//最大公約数
long long gcd(long long m,long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m,long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x,long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  int Q;cin>>Q;
  vector<ll>S(100000+1);
  S[0]=0;S[1]=0;
  for(ll i=2;i<100000+1;i++){
    if(i%2==0) S[i]=S[i-1];
    else{
      S[i]=S[i-1];
      if(is_prime(i)&&is_prime((i+1)/2))
        S[i]++;
    }
  }
  
  rep(i,Q){
    ll l,r;cin>>l>>r;
    cout<<S[r]-S[l-1]<<endl;
  }
}
        

Measured memory_bytes: 1408
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {

        int inpt = int.Parse(Reader.ReadLine());

        string ans = "ABD";

        if(inpt <1000) {
            ans = "ABC";
        }
        Console.WriteLine(ans);
    }


    public class Reader
    {
        static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"








";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 13140
use std::io::{self, BufRead};

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let line = lines.next().unwrap().unwrap();
  let vs: Vec<usize> = line.split(' ').map(|x| x.parse().unwrap()).collect();
  let n = vs[0];
  let k = vs[1];
  let line = lines.next().unwrap().unwrap();
  let ps: Vec<f64> = line.split(' ').map(|x| x.parse::<f64>().unwrap()).map(|p| (1.0 + p) / 2.0).collect();
  let mut ex: f64 = (0..k).fold(0.0, |acc, i| acc + ps[i]);
  let mut max = ex;
  for i in 0..(n-k) {
    ex = ex + ps[k+i] - ps[i];
    if max < ex {
      max = ex;
    }
  }
  println!("{}", max);
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    char ch;
    cin>>ch;
    if(ch>='A' && ch<='Z')
    cout<<'A';
    else
    cout<<'a';
    return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    vector<lint> v(n);
    REP(i, n) { cin >> v[i]; }
    lint mode = 0,pre=v[0];//0 1増加　2減少
    lint ans = 0;
    FOR(i,1,n){
        if(pre<v[i]){//増加モード
            if(mode==2){
                ans += 1;
                mode = 0;
            }else{
                mode = 1;
            }
        }
        if (pre ==v[i])
        { 
        }
        if (pre > v[i])
        { //減少モード
            if (mode == 1)
            {
                ans += 1;
                mode = 0;
            }
            else
            {
                mode = 2;
            }
        }
        pre = v[i];
    }

    cout << ans+1 <<"\n";

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

void solve() {
    auto YesNo = [&](bool t) { std::cout << (t ? "Yes" : "No") << std::endl; };
    int n;
    scanf("%d", &n);
    std::vector<int> h(n);
    rep(i, n) scanf("%d", &h[i]);
    for(int i = n - 2; i >= 0; i--)
        if(h[i] > h[i + 1]) {
            h[i]--;
        }
    bool ok = true;
    rep(i, n - 1) {
        if(h[i] > h[i + 1]) ok = false;
    }
    YesNo(ok);
    return;
}

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

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        S = S.replaceAll("B", "");
        if (S.length() == 0 || S.length() == 3) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }

    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <functional>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <map>

using namespace std;
using ll = long long;

int main()
{
	int n, m;
	cin >> n >> m;

	vector <vector <int> > adj(n);

	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int cnt = 0;
	vector<bool> zumi(n, false);
	for (int i = 0; i < n; i++)
	{
		if (!zumi[i])
		{
			cnt++;
			stack<int>s;
			s.push(i);

			while (!s.empty())
			{
				int oya = s.top();
				s.pop();
				zumi[oya] = true;
				for (int ko : adj[oya])
				{
					if (!zumi[ko])
					{
						s.push(ko);
					}
				}
			}
		}

	}
	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 6520
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 
int main()
{
  int A, B, C, X;
  cin >> A >> B >> C >> X;

  int cnt = 0;
  REP(i,A+1){
    REP(j,B+1){
      REP(k,C+1){
        if(i*500+j*100+k*50==X){
          cnt++;
        }
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
from itertools import permutations
n = int(input())
p = int(input().replace(' ', ''))
q = int(input().replace(' ', ''))
per = permutations([str(i) for i in range(1, n+1)], n)
lst = []
for pi in per:
  lst.append(int(''.join(pi)))
print(abs(lst.index(p) - lst.index(q)))

Measured memory_bytes: 10500
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
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; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  int a,b,c ;
  cin >> a >> b >> c;
  if (a+b-c >= 0) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }
}


Measured memory_bytes: 256
from collections import deque

def new_color(s, i, color):
  return s[:i] + color * 2 + s[i + 2:]

def solve(s):
  length = len(s)
  monos = ["r" * length, "g" * length, "b" * length]
  if s in monos:
    print(0)
    return

  another = {("r", "g"):"b", ("g", "r"):"b", 
             ("r", "b"):"g", ("b", "r"):"g",
             ("g", "b"):"r", ("b", "g"):"r"}
  visited = {s:0}
  que = deque()
  app = que.append
  pop = que.popleft
  que.append((s, 0))

  while que:
    colors, score = pop()
    score += 1
    temp = colors[0]

    for i in range(1, length):
      ci = colors[i]
      if ci != temp:
        new = new_color(colors, i - 1, another[(ci, temp)])
        if new in monos:
          print(score)
          return

        if new not in visited:
          visited[new] = score
          app((new, score))

      temp = ci

  print("NA")

def main():
  while True:
    s = input()
    if s == "0":
      break
    solve(s)

main()


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

int N, W, weight[104];
long long value[104];
long long dp[104][100005];

long long solve(int i, int w) {
	if (i>=N) {
		return 0;
	}
	
	if (dp[i][w] != -1) {
		return dp[i][w];
	} 
	
	long long X = solve(i+1, w);
	int nw = w - weight[i];
	if (nw >= 0) {
		X = max(X, value[i] + solve(i+1, nw));
	}
	
	return dp[i][w] = X;
}

int main() {
	cin>>N>>W; 
	for(int i=0;i<N;i++) {
		cin>>weight[i]>>value[i];
	}
	
	for(int i=0;i<N;i++) {
		for(int j=0;j<100005;j++) {
			dp[i][j] = -1;
		}
	}
	
	for(int i=0;i<=W;i++) {
		if(i>=weight[N-1]) {
			dp[N-1][i] = value[N-1];
		} else {
			dp[N-1][i] = 0;
		}
	}
	
	cout<<solve(0, W);
	
	return 0;
}

Measured memory_bytes: 81748
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8


void mainmain(){
	LL n, x, d;
	cin >> n >> x >> d;

	LL ans = 0;
	if(d == 0){
		set<LL> st;
		for(int i = 0; i <= n; ++i){
			st.insert(x * i);
		}
		ans = st.size();
	}
	else{
		map<LL,vector<pll>> mp;
		for(LL i = 0; i <= n; ++i){
			LL md = ((x * i) % d + d) % d;
			LL from = (x * i - md) / d + i * (i - 1) / 2;
			LL to = (x * i - md) / d + i * (2 * n - i - 1) / 2 + 1;
			mp[md].emplace_back(from, to);
		}
		for(auto &p : mp){
			auto &v = p.second;
			sort(ALL(v));
			LL mx = LLONG_MIN;
			for(cauto q : v){
				LL t = max(mx, q.first);
				chmax(mx, q.second);
				ans += mx - t;
			}
		}
	}
	cout << ans << endl;
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){
	throw;
}


Measured memory_bytes: 22144
N=int(input())
p = list(int(i) for i in input().split())
count = 0
for i in range(N):
    if p[i] == i+1:
        if i != N-1:
            a = p[i]
            p[i] = p[i+1]
            p[i+1] = a
            count += 1
        else:
            count += 1
print(count)

Measured memory_bytes: 14008
import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] citiesPos = new int[N];

        for (int i = 0; i < N; i++) {
            citiesPos[i] = sc.nextInt();
        }

        Arrays.sort(citiesPos);
        int min = 1000000000;
        if (citiesPos.length == 1) {
            min = Math.abs(citiesPos[0] - X);
        }else {
            for (int cityPos : citiesPos) {
                min = Math.min(min, Math.abs(X - cityPos));
            }
        }

        boolean indivisibleFlg = false;
        for (int cityPos : citiesPos) {
            if (indivisibleFlg) {
                break;
            }
            if ((cityPos - X) % min != 0) {
                indivisibleFlg = true;
            }
        }

        if (indivisibleFlg) {
            int[] absDiffs = new int[citiesPos.length];
            for (int i = 0; i < citiesPos.length; i++) {
                absDiffs[i] = Math.abs(X - citiesPos[i]);
            }

            int ans = gcd(absDiffs[0], absDiffs[1]);
            if (absDiffs.length > 2) {
                for (int i = 2; i < absDiffs.length; i++) {
                    ans = gcd(ans, absDiffs[i]);
                }
            }
            System.out.println(ans);
        } else {
            System.out.println(min);
        }
    }

    public static int gcd(int a, int b){
        int r = a % b;
        if (b % r != 0) {
            r = gcd(b,r);
        }
        return r;
    }
}

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

int main() {
  string X;
  int w=0,e=0,n=0,s=0;

  cin >> X;
  for(int i=0;i<X.size();++i){
    if(X.at(i) == 'W'){
      w = 1;
    }else if(X.at(i) == 'E'){
      e = -1;
    }else if(X.at(i) == 'N'){
      n = 1;
    }else{
      s = -1;
    }
  }
  if(e+w == 0 && n+s == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3616
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N = 100010;
int n, a[N], b[N], aq[N], bq[N], fa[N], ans;
map<int, int> pos;

int Find(int u)
{
	if (fa[u] == u) return u;
	return fa[u] = Find(fa[u]);
}

void Merge(int x, int y)
{
	if (Find(x) == Find(y)) return;
	fa[Find(x)] = Find(y);
	ans--;
}

int main()
{
	scanf("%d", &n);
	a[n+1] = 0;
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		aq[i] = a[i];
		a[n+1] ^= a[i];
	}
	aq[n+1] = a[n+1];
	sort(aq+1, aq+n+2);
	for (int i = 1; i <= n; i++){
		scanf("%d", &b[i]);
		bq[i] = b[i];
		b[n+1] ^= b[i];
	}
	bq[n+1] = b[n+1];
	sort(bq+1, bq+n+2);
	for (int i = 1; i <= n+1; i++)
		if (aq[i] != bq[i]){
			printf("-1");
			return 0;
		}
	ans = n*2;
	for (int i = 1; i <= n+1; i++) fa[i] = i;
	for (int i = 1; i <= n+1; i++){
		if (a[i] == b[i] && i != n+1)
			ans -= 2;
		else{
			if (pos.find(a[i]) != pos.end())
				Merge(pos[a[i]], i);
			else pos[a[i]] = i;
			if (pos.find(b[i]) != pos.end())
				Merge(pos[b[i]], i);
			else pos[b[i]] = i;
		}
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


const int N = 8;

vector<bool> row(N, false), col(N, false), dpos(2*N-1, false), dneg(2*N-1, false);
vector<vector<char>> fi(N, vector<char>(N, '.'));

void printBoard(){
    rep(i, N){
        rep(j, N) cout << fi[i][j];
        cout << endl;
    }
}



void input(){
    int k; cin >> k;
    rep(i, k){
        int r, c; cin >> r >> c;
        row[r] = true;
        col[c] = true;
        dpos[r-c+N-1] = true;
        dneg[r+c] = true;
        fi[r][c] = 'Q';
    }
}

void rec(int i){
    if(i == N){ printBoard(); return; }
    if(row[i] == true) { rec(i+1); return; }
    
    rep(j, N){
        if(col[j]==true || dpos[i-j+N-1]==true || dneg[i+j]==true) continue;
        row[i]=true; col[j]=true; dpos[i-j+N-1]=true; dneg[i+j]=true; fi[i][j]='Q';
        rec(i+1);
        row[i]=false; col[j]=false; dpos[i-j+N-1]=false; dneg[i+j]=false; fi[i][j]='.';
    }
}

void solve(){
    rec(0);
}

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

    input();
    solve();
    
    return 0;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

map<ll, ll> memo;
ll A, B, C, D;

ll f(ll N){
    if(memo.count(N)){
        return memo[N];
    }
    
    ll ret = INF;
    ret = min(ret, f(N/2) + A + (N%2)*D);
    ret = min(ret, f(N/2+1) + A + (2-N%2)*D);
    ret = min(ret, f(N/3) + B + (N%3)*D);
    ret = min(ret, f(N/3+1) + min(B + (3-N%3)*D, B+(N%3)*D+D));
    ret = min(ret, f(N/5) + min(C + (N%5)*D, C + (5-N%5)*D+D));
    ret = min(ret, f(N/5+1) + min(C + (5-N%5)*D, C + (N%5)*D+D));
    if(INF / D > N-N/2  ) ret = min(ret, f(N/2  ) + D*(N-N/2));
    if(INF / D > N-N/2-1) ret = min(ret, f(N/2+1) + D*(N-N/2-1));
    if(INF / D > N-N/3  ) ret = min(ret, f(N/3  ) + D*(N-N/3));
    if(INF / D > N-N/3-1) ret = min(ret, f(N/3+1) + D*(N-N/3-1));
    if(INF / D > N-N/5  ) ret = min(ret, f(N/5  ) + D*(N-N/5));
    if(INF / D > N-N/5-1) ret = min(ret, f(N/5+1) + D*(N-N/5-1));
    return memo[N] = ret;
}

int main(){
    int T;
    cin >> T;
    ll N;
    for (int i = 0; i < T; i++) {
        cin >> N >> A >> B >> C >> D;
        memo.clear();
        memo[0] = 0;
        memo[1] = D;
        memo[2] = min(2*D, A+D);
        printf("%lld\n", f(N));
    }
}

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

ll solve() {
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    if ( K <= A ) return K;
    else if ( K <= A+B ) return A;
    else return A - (K-A-B);
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3636
import bisect

n, q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]
AC_index = []

for index in range(len(s)-1):
  if s[index:index+2] == "AC":
    AC_index.append(index)

for i in range(len(lr)):
  left_index = bisect.bisect_left(AC_index,lr[i][0]-1)
  right_index = bisect.bisect_left(AC_index,lr[i][1]-1)
  print(right_index-left_index)

Measured memory_bytes: 30316
using System;
class Program
{
    public static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');
        int d1 = int.Parse(str[1]) - int.Parse(str[0]);
        int d2 = int.Parse(str[2]) - int.Parse(str[1]);
        Console.WriteLine(d1 == d2 ? "YES" : "NO");
    }
}

Measured memory_bytes: 11092