akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
//#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < (n); i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 5005, mod = 1000000007;
int n, m, p[MX], sz[MX], ex[MX];
ll dp[MX][MX], res, cn, fac[MX];
vi a;

int parent (int a) { return a == p[a] ? a : p[a] = parent(p[a]); }

void join (int a, int b) {
	a = parent(a), b = parent(b);
	if (a == b) return;

	ex[a] |= ex[b];
	sz[a] += sz[b];
	p[b] = a;
}

ll pot (ll b, int p) {
	ll res = 1;
	while (p) {
		if (p & 1) (res *= b) %= mod;
		(b *= b) %= mod;
		p /= 2;
	}
	return res;
}

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

	fac[0] = 1;
	forn (i, MX) {
		p[i] = i;
		sz[i] = 1;
		if (i) fac[i] = fac[i - 1] * i % mod;
	}

	cin >> n;
	forn (i, n) {
		int p;
		cin >> p;
		if (p == -1) ex[parent(i)] = 1;
		else join(i, p - 1);
	}

	forn (i, n) if (parent(i) == i) {
		if (ex[i]) a.pb(sz[i]);
		cn++;
	}

	m = a.size();
	res = (n - (cn - m)) * pot(n - 1, m) % mod;

	dp[0][0] = 1;
	forn (i, m) {
		forn (j, i + 1) {
			(dp[i + 1][j] += dp[i][j]) %= mod;
			(dp[i + 1][j + 1] += a[i] * dp[i][j]) %= mod;
		}
		(res -= (a[i] - 1) * pot(n - 1, m - 1)) %= mod;
	}

	for (int i = 2; i <= m; i++)
		(res -= dp[m][i] % mod * fac[i - 1] % mod * pot(n - 1, m - i)) %= mod;

	cout << (res + mod) % mod << endl;

	return 0;
}

Measured memory_bytes: 120404
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws Exception {
    try (final var stdin = new InputStreamReader(System.in);
         final var br = new BufferedReader(stdin)) {
      final var l = Arrays.stream(br.readLine().split(" "))
        .mapToInt(Integer::parseInt)
        .toArray();

      System.out.println(l[1] * l[2] >= l[0] ? "Yes" : "No");
    }
  }
}


Measured memory_bytes: 34276
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main() {
	int h,w; cin >> h >> w;
	char grid[50][50];
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++) cin >> grid[i][j];
	int minmass[50][50];
	int blacknum=0;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++) {
		minmass[i][j]=(grid[i][j]=='.'?1e5:-1);
		if(grid[i][j]=='#') blacknum++;
	}
	minmass[0][0]=1;
	queue<pair<int,int>> q;
	q.push(make_pair(0,0));
	while(!q.empty()){
		int i=q.front().first;
		int j=q.front().second;
		q.pop();
		int x=1,y=0;
		for(int k=0;k<4;k++){
			if(0<=i+y&&i+y<h && 0<=j+x&&j+x<w){
				if(minmass[i+y][j+x]!=-1){
					if(minmass[i+y][j+x]>minmass[i][j]+1){
						minmass[i+y][j+x]=minmass[i][j]+1;
						q.push(make_pair(i+y,j+x));
					}
				}
			}
			int temp=x;
			x=y;
			y=-temp;
		}
	}
	int ans=h*w-minmass[h-1][w-1]-blacknum;
	if(minmass[h-1][w-1]==1e5) cout << -1 << endl;
	else cout << ans << endl;
}


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

public class Main {
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
		String inputS = sc.nextLine();
		String[] inputT = sc.nextLine().split("");
		int minReplaceCount = inputT.length;
		// 切り出す頭の位置
		for (int i=0; i+inputT.length<=inputS.length(); i++) {
			// 検索する文字列を切り出す
			String[] targetStr = inputS.substring(i, i+inputT.length).split("");
			int replaceStrCount = 0;
			for (int j=0; j<targetStr.length; j++) {
				if (!targetStr[j].equals(inputT[j])) replaceStrCount++;
			}
			if (minReplaceCount > replaceStrCount) minReplaceCount = replaceStrCount;
		}
		System.out.println(minReplaceCount);
	}
}


Measured memory_bytes: 55916
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int i;
  string c;
  for(i=0;i<=1+b;i++){
    cout<<"#";
  }
  cout<<endl;
  for(i=0;i<a;i++){
    cin>>c;
    cout<<"#"<<c<<"#"<<endl;
  }
  for(i=0;i<=1+b;i++){
    cout<<"#";
  }
  cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if ( c > a + b ) cout << "No" << endl;
    else                     cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
const int MOD = 998244353,N = 2e5 + 5;
int fac[N],inv[N];
int qpow(long long a,long long b);
void run();
using namespace std;
int main()
{
	run();
	return 0;
} 
int qpow(long long a,long long b)
{
	long long res=1;
	while (b)
	{
		if (b&1)   res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
void run() {
    int n, m, k;
    cin >> n >> m >> k;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[n] = qpow(fac[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    int ans = 0;
    for (int t = n - k; t <= n; t++) {
        //x_1+x_2+..x_t = n
        int res = 1ll * m * qpow(m - 1, t - 1) % MOD;
        res = 1ll * res * fac[n - 1] % MOD * inv[t - 1] % MOD * inv[n - t] % MOD;
        ans = (ans + res) % MOD;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 5120
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>
#include <stdio.h>

int main(void){
  int n,m;
  std::cin >> n >> m;

  std::cout << n*(n-1)/2 + m*(m-1)/2;
  return 0;
}

Measured memory_bytes: 3572
def bitcount(x):
    r = 0
    l = len(bin(x))-2
    for i in range(l):
        if x>>i&1:r+=1
    return r
n,m = map(int,input().split())
switch = [0]*m
for i in range(m):
    tmp = list(map(int,input().split()))[1:]
    for s in tmp:
        switch[i] = switch[i]|2**(s-1)

P = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    ons = 0 #ついてる電球
    for j in range(m):#j番目の電球について
        tmp = i&switch[j]
        if bitcount(tmp)%2==P[j]:
            ons+=1
    if ons==m:ans+=1

print(ans)


Measured memory_bytes: 3064
#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 FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> c(h, vector<char>(w));
  rep(i, h) {
    rep(j, w) {
      cin >> c[i][j];
    }
  }

  rep(i, h) {
    rep(j, w) {
      if (c[i][j] == '.') {
        char res = '0';
        FOR(dy, -1, 2) {
          FOR(dx, -1, 2) {
            if (0 <= i + dy && i + dy < h && 0 <= j + dx && j + dx < w && c[i + dy][j + dx] == '#') res++;
          }
        }
        c[i][j] = res;
      }
    }
  }

  rep(i, h) {
    rep(j, w) {
      cout << c[i][j];
    }
    cout << endl;
  }





  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int MOD=1000000007;
using namespace std;
int main(){
    ll n,c;
    cin>>n>>c;
    vector<ll> x(n+1,0),v(n+1,0);
    rep(i,0,n) cin>>x.at(i+1)>>v.at(i+1);
    
    vector<ll> clock(n+1),counter(n+1);
    rep(i,0,n) clock.at(i+1)=clock.at(i)+v.at(i+1)-(x.at(i+1)-x.at(i));
    counter.at(n)=v.at(n)-(c-x.at(n));
    rrep(i,n,1) counter.at(i)=counter.at(i+1)+v.at(i)-(x.at(i+1)-x.at(i));
    
    rep(i,0,n) clock.at(i+1)=max(clock.at(i+1),clock.at(i));
    rrep(i,n,1) counter.at(i)=max(counter.at(i+1),counter.at(i));
    
    ll ans=0;
    rep(i,1,n+1){
        ans=max({ans,clock.at(i),counter.at(i)});
    }
    rep(i,1,n){
        ans=max(ans,clock.at(i)-x.at(i)+counter.at(i+1));
        ans=max(ans,counter.at(i+1)-(c-x.at(i+1))+clock.at(i));
    }
    
    cout<<ans<<endl;
}



Measured memory_bytes: 3328
#coding:utf-8
import math

n = int(input())
prime_count = 0
for i in range(n):
    x = int(input())
    div = 1
    div_count = 0

    while div <= math.sqrt(x) and div_count < 3:
        if x % div == 0 and div == math.sqrt(x):
             div_count += 1
        elif x % div == 0 and div != math.sqrt(x):
             div_count += 2
        div += 1

    if div_count == 2:
        prime_count += 1

print(prime_count)

Measured memory_bytes: 6812
#include <iostream>
#include <iomanip>
#include <cassert>

#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <limits>
#include <queue>
#include <unordered_map>
#include <list>
#include <set>
#include <numeric>
using namespace std;

using ll = long long;

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

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

	cout << a + a * a + a * a * a << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
using namespace std;

typedef vector<pair<int, int> > vpii;

int main() {
  int n;
  long a[200000];
  
  long sum;
  long Max = 0;
  cin >> n;
  for(int i = 0; i< n; i++) {
    cin >> a[i];
    a[i + n] = a[i];
    sum += a[i];
  }
  
  int i,j,k;
  long first, second, third, rest;
  rep(j,n) {
    first = 0;
    for (i = 0;i < n - 2 && first <= Max;i++){
      first += a[j + i];
    }
    rest = sum - first;
    second = a[j + i];
    k = j + i + 1;
    third = rest - second;
    while (k < j + n - 1 && second + a[k] <= third - a[k]) {
      second += a[k];
      third = rest - second;
      k++;
    }
    if((first <= second && first <= third) || (first <= second + a[k] && first <= third - a[k])) {
      Max = max(first, Max);
    }
    for (;i < n - 2;i++){
      first += a[j + i];
      rest -= a[j + i];
      second -= a[j + i];
      
      while (k < j + n - 1 && second + a[k] <= third - a[k]) {
        second += a[k];
        third = rest -second;
        k++;
      }

      if((first <= second && first <= third) || (first <= second + a[k] && first <= third - a[k])) {
        Max = max(first, Max);
      } else {
        break;
      }
    }
  }
  cout << Max << endl;
}

Measured memory_bytes: 2724
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>
#include <math.h>

int main (void)
{
    intmax_t N, D, X[10][10];
    intmax_t ans = 0;

    scanf("%jd%jd", &N, &D);
    for (size_t n = 0; n < N; n++) {
        for (size_t d = 0; d < D; d++) {
            scanf("%jd", &X[n][d]);
        }
    }

    for (size_t i = 0; i < N; i++) {
        for (size_t j = (i + 1); j < N; j++) {
            long double dist = 0;
            for (size_t d = 0; d < D; d++) {
                dist += abs(X[i][d] - X[j][d]) * abs(X[i][d] - X[j][d]);
            }
            dist = sqrtl(dist);
            if (dist == floorl(dist)) ans++;
        }
    }

    printf("%jd\n", ans);

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdlib>
using namespace std;

int main()
{
    string n;
    while(cin >> n, n != "0000"){
        if(n[0] == n[1] && n[1] == n[2] && n[2] == n[3]){
            cout << "NA" << endl;
            continue;
        }
        int ans = 0;
        while(n != "6174"){
            string l = n, s = n;
            sort(l.begin(), l.end(), greater<char>()); sort(s.begin(), s.end());
            int t = atoi(l.c_str()) - atoi(s.c_str());
            for(int i = 3; i >= 0; --i){
                n[i] = '0' + t % 10;
                t /= 10;
            }
            ++ans;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <algorithm>
#include <unordered_map>
#define int long long
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

using namespace std;

void fast()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MOD = 1e9 + 7;
const int INF = 1e9;

signed main()
{
	int n;
	cin >> n;
    map <int, int> cnt;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        ++cnt[a];
        sum += a;
    }

    int q;
    cin >> q;
    while (q--)
    {
        int b, c;
        cin >> b >> c;
        int cntt = cnt[b];
        cnt[b] = 0;
        cnt[c] += cntt;
        sum += (c - b) * cntt;
        cout << sum << '\n';
    }

    return 0;
}


Measured memory_bytes: 9556
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <complex>

using namespace std;
typedef long long ll;

typedef long double R;
typedef complex<R> P;

const R EPS = 1e-10;
const R PI = acos(-1);
int sgn(R a) {
    if (a < -EPS) return -1;
    if (a > EPS) return 1;
    return 0;
}


bool near(P a, P b) {
    return !sgn(abs(a-b));
}

R cross(P a, P b) { return imag(conj(a)*b); }
R dot(P a, P b) { return real(conj(a)*b); }

struct L {
    P x, y;
    L() {};
    L(P x, P y) :x(x), y(y) {};
};

namespace std {
    bool operator < (P a, P b) {
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
}

int ccw(P a, P b, P c) {
    double cr = cross(b-a, c-a);
    if (cr > EPS) return 1;
    if (cr < -EPS) return -1;
    if (dot(b-a, c-a) < -EPS) return 2;
    if (dot(a-b, c-b) < -EPS) return -2;
    return 0;
}

typedef vector<P> Pol;

Pol convex(Pol p) {
    sort(p.begin(), p.end());
    if (p.size() <= 2) return p;
    Pol up;
    for (P d: p) {
        //if (up.size() > 1) printf("ccw%d\n",  ccw(up[up.size()-2], up[up.size()-1], d) );
        while (up.size() > 1 && ccw(up[up.size()-2], up[up.size()-1], d) > 0) {
        //    printf("pop\n");
            up.pop_back();
        }
        //printf("push\n");
        up.push_back(d);
    }
    reverse(up.begin(), up.end());
    Pol down;
    for (P d: p) {
        while (down.size() > 1 && ccw(down[down.size()-2], down[down.size()-1], d) < 0) down.pop_back();
        down.push_back(d);
    }
    //printf("%ld %ld\n", up.size(), down.size());
    down.insert(down.begin(), up.begin()+1, up.end()-1);
    return down;
}

int main() {
    while (true) {
        int n;
        cin >> n;
        if (!n) break;
        Pol p;
        for (int i = 0; i < n; i++) {
            R x, y;
            scanf("%Lf,%Lf", &x, &y);
            p.push_back(P(x, y));
        }
        cout << n-convex(p).size() << endl;
    }
    return 0;
}

Measured memory_bytes: 1284
#include<iostream>
#include<bitset>
using namespace std;
int main(){
    int d,g,i,ans=1000;
    cin>>d>>g;
    int p[d],c[d];
    for(i=0;i<d;i++)cin>>p[i]>>c[i];
    for(int b=0;b<1<<d;b++){
        bitset<10>bit(b);
        int score=0,num=0;
        for(i=0;i<d;i++)if(bit[i])score+=(i+1)*100*p[i]+c[i],num+=p[i];
        i=d-1;
        while(i&&bit[i])i--;
        int tmp=(g-score+(i+1)*100-1)/((i+1)*100);
        if(tmp>=p[i])continue;
        if(score<g&&i>=0)num+=tmp;
        ans=min(ans,num);
    }
    cout<<ans<<endl;
    return 0;
    
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num1 = Integer.parseInt(sc.next());
		int num2 = Integer.parseInt(sc.next());

		if (num1 == 1 || num1 == num2) {
			System.out.println(num1 + num2);
		} else {
			if (num1 > num2) {
				if (num1 % num2 == 0) {
					System.out.println(num1 + num2);
				} else {
					System.out.println(num2 - num1);
				}
			} else if (num1 < num2) {
				if (num2 % num1 == 0) {
					System.out.println(num1 + num2);
				} else {
					System.out.println(num2 - num1);
				}
			}
		}
		sc.close();
	}
}

Measured memory_bytes: 22736
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin>>n;
  int sum = 0;
  vector<int> l(n),r(n);
 
  rep(i,n){
    cin>>l.at(i)>>r.at(i);
    sum += r.at(i)-l.at(i)+1;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
def solve(a,b,c):
  x=sum(a)
  y=sum(b)
  z=sum(c)
  if abs(x-y)%3!=0 or abs(y-z)%3!=0 or abs(z-x)%3!=0:
    return False
  for i in range(101):
    for j in range(101):
      for k in range(101):
        if (i-j)*3==(x-y) and (j-k)*3==(y-z) and (k-i)*3==(z-x):
          return True
  return False

A1=[int(x) for x in input().split()]
A2=[int(x) for x in input().split()]
A3=[int(x) for x in input().split()]

B1=[A1[0],A2[0],A3[0]]
B2=[A1[1],A2[1],A3[1]]
B3=[A1[1],A2[1],A3[1]]

if solve(A1,A2,A3) and solve(B1,B2,B3):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*3]*n
dp[0][0],dp[0][1],dp[0][2] = abc[0][0],abc[0][1],abc[0][2]  
for i in range(n-1):
  dp[i+1][0],dp[i+1][1],dp[i+1][2] = (abc[i+1][0] + max(dp[i][1],dp[i][2]),
                                      abc[i+1][1] + max(dp[i][2],dp[i][0]),
                                      abc[i+1][2] + max(dp[i][0],dp[i][1]))
print(max(dp[-1]))
  
    

Measured memory_bytes: 31348
#include<bits/stdc++.h>
using namespace std;
typedef signed long long ll;
typedef vector<int> vi;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a) (a).begin(), (a).end()


int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	cin >> n >> k;

	cout << ((n-1) + (k-2)) / (k-1) << endl;
}

Measured memory_bytes: 256
use proconio::input;

const MOD: i64 = 1000000007;

fn main() {
  input! {
    n : usize, k: usize,
    a: [usize; n]
  }
  
  if (n == 1) {
    println!("{}", if k > a[0] { 0 } else { 1 });
    return;
  }
  
  let mut dp = vec![0; k + 1];
  dp[0] = 1;
  for i in 1..=a[n-1] {
    dp[i] = (dp[i - 1] + 1) % MOD;
  }
  for i in (a[n-1]+1)..=k {
    dp[i] = dp[i - 1];
  }

  for i in (1..(n-1)).rev() {
    let mut dp_next = vec![0; k + 1];
    dp_next[0] = 1;
    for j in 1..=a[i] {
      dp_next[j] = (dp_next[j-1] + dp[j]) % MOD;
    }
    for j in (a[i]+1)..=k {
      dp_next[j] = (dp_next[j - 1] + (dp[j] + MOD - dp[j - a[i] - 1]) % MOD) % MOD;
    }
    dp = dp_next;
  }
  if k > a[0] { dp[k] = (dp[k] + MOD - dp[k - a[0] - 1]) % MOD }
  println!("{}", dp[k]);
}



Measured memory_bytes: 3608
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)




int main() {
    string s, t;
    cin >> s >> t;
    
    ll n = s.size() + 1, m = t.size() + 1;
    vector<ll> cntA1(n + 5), cntA2(m + 5);
    REP(i, n){
        cntA1[i + 1] = (s[i] == 'A')? 1 : 2;
        cntA1[i + 1] += cntA1[i];
    }
    REP(i, m){
        cntA2[i + 1] = (t[i] == 'A')? 1 : 2;
        cntA2[i + 1] += cntA2[i];
    }
    
    ll q;
    cin >> q;
    REP(i, q){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        if((cntA1[b] - cntA1[a - 1]) % 3 == (cntA2[d] - cntA2[c - 1]) % 3){
            cout << "YES" << '\n';
        }
        else{
            cout << "NO" << '\n';
        }
    }
}

Measured memory_bytes: 2432
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
create(x::Int,y::Int)=lpad(x,6,0)*lpad(y,6,0)

function main()
	n,m = readline() |> split |> parseMap
	a = Tuple{Int,Int,Int}[]
	for i in 1:m
		p,y = readline() |> split |> parseMap
		push!(a,(i,p,y))
	end
	a = sort(a,by=x->(x[2],x[3]))
	g = String["" for i in 1:m]
	c = 1
	g[a[1][1]]=create(a[1][2],c)
	for i in 2:m
		if a[i][2]!=a[i-1][2]
			c = 1
		else
			c += 1
		end
		g[a[i][1]]=create(a[i][2],c)
	end
	map(println,g)
end

main()

Measured memory_bytes: 166864
#include <iostream>
#include <string>

int solve(const std::string& s)
{
  int result = 0;
  for (auto i = 0u; i < s.size(); ++i) {
    if (i % 2 == 0) {
      if (s[i] == '0') ++result;
    } else {
      if (s[i] == '1') ++result;
    }
  }
  return result <= static_cast<int>(s.size() / 2) ? result : s.size() - result;
}

int main()
{
  std::string s;
  std::cin >> s;

  std::cout << solve(s) << std::endl;
}


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args)
	{
		FastReader in = new FastReader();
		int n = in.nextInt();
		int[] h = new int[n];
		for(int i = 0; i < n; i++)
		{
			h[i] = in.nextInt();
		}
		int[] dp = new int[n];
		dp[1] = Math.abs(h[0]-h[1]);
		for(int i = 2; i < n; i++)
		{
			dp[i] = Math.min(dp[i-1]+Math.abs(h[i-1]-h[i]), dp[i-2]+Math.abs(h[i-2]-h[i]));
		}
		System.out.println(dp[n-1]);
	}
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                }
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
}


Measured memory_bytes: 32400
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            var N = IO.GetInt();
            var W = IO.GetIntList();
            var sum = W.Sum();
            var ans = int.MaxValue;
            var tempsum = 0;
            for(int i = 0; i < N; i++)
            {
                tempsum += W[i];
                ans = Math.Min(Math.Abs(sum - 2*tempsum), ans);
            }


            Console.Write(ans);
        }
    }


    static class IO
    {
        static public string GetString() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public List<string> GetStringList() { return Console.ReadLine().Split(' ').ToList(); }
        static public List<int> GetIntList() { return Console.ReadLine().Split(' ').Select(int.Parse).ToList(); }
        static public List<long> GetLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteStrings<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
    }
}

Measured memory_bytes: 13268
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
#include <numeric>
#include <bitset>
#include <map>
#include <limits.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<=n;i++)
using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;


/// 各桁の和
int sumdigit(int x){
   int sum = 0;
    while(x != 0){
        sum += x % 10;
        x /= 10;    
    }
    return sum;
}
/// 最大公約数 
int gcd(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }
      int r = x % y;
       while(r!=0){
           x = y;
           y = r;
           r = x % y;
       }
      return y;
   }



int main(){
int A,B;
cin >> A >> B;
int ans = 0;
REP(i,2){
    if(A >= B){
        ans+=A;
        A--;
    }
    else {
        ans+=B;
        B--;
    }
}
cout << ans << endl;

}

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

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  if(a+b<=k){
    cout << 0 << " " << 0 << endl;
    return 0;
  }
  b = min(b, b+a-k);
  a = max(0ll, a-k);
  
  cout << a << " " << b << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // ll は long long　と同じとする。
int main() {
    int64_t N;
    cin >> N;
    int64_t srt = 10e15;
    for(int64_t i = 1; i * i <= N; i++) {
        if(N % i == 0){
            srt = min(srt , i + N / i - 2);
        }
    }
    cout << srt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n, p;
    cin >> n >> p;

    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        s[i] -= '0';
    }

    ll r = 0;
    if (10 % p == 0) {
        for (int i = 0; i < n; i++) {
            if (s[i] % p == 0) r += i + 1;
        }

    } else {
        vector<int> c(p, 0);
        int t = 0, d = 1;

        for (int i = n - 1; i >= 0; i--) {
            c[t]++;
            t += s[i] * d;
            t %= p;
            d *= 10;
            d %= p;

            r += c[t];
        }
    }

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
int main() {
	long long h, a=0;
  	int n;
  	cin >> h >> n;
  	while (n--) {
     	long long x; cin >> x;
      	a += x;
    }
  	cout << (a >= h ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
import numpy as np

a=input()
arr_a = np.array([int(x) for x in list(a)])
arr_1 = np.array([0 if i%2 == 0 else 1 for i in range(len(a))])
arr_2 = np.array([1 if i%2 == 0 else 0 for i in range(len(a))])

print(min(np.abs(arr_1 - arr_a).sum(), np.abs(arr_2 - arr_a).sum()))

Measured memory_bytes: 16604
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

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

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

type circle struct {
	x, y, r int
}

func calc(a, b circle) float64 {
	dx := abs(a.x - b.x)
	dy := abs(a.y - b.y)
	r := abs(a.r + b.r)
	d := dx*dx + dy*dy
	if d < a.r || d < b.r {
		return 0.0
	}

	ret := math.Max(math.Sqrt(float64(dx*dx+dy*dy))-float64(r), 0.0)
	return ret
}

// Priority Queue
type Item struct {
	priority     float64
	value, index int
}

type PQ []*Item

func (pq PQ) Len() int {
	return len(pq)
}

func (pq PQ) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PQ) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

// End Priority Queue

// Path
type Edge struct {
	to, cost int
}

type Path struct {
	edges []Edge
}

// Dijkstra
type Route struct {
	path []int
}

func Dijkstra(N, S int, path [][]float64) []float64 {
	pq := make(PQ, 0)
	heap.Init(&pq)
	d := make([]float64, N)
	// init
	for i := 0; i < N; i++ {
		d[i] = math.MaxFloat64
	}
	d[S] = 0
	heap.Push(&pq, &Item{0, S, 0})
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		v := item.value
		if d[v] < item.priority {
			continue
		}
		for i := 0; i < len(path); i++ {
			if d[i] > d[v]+path[i][v] {
				d[i] = d[v] + path[i][v]
				heap.Push(&pq, &Item{d[i], i, 0})
			}
		}
	}
	return d

}

func main() {
	sc.Split(bufio.ScanWords)
	xs, ys, xt, yt := getInt(), getInt(), getInt(), getInt()
	N := getInt()
	c := make([]circle, N+2)
	c[0] = circle{xs, ys, 0}
	for i := 1; i <= N; i++ {
		c[i] = circle{getInt(), getInt(), getInt()}
	}
	c[N+1] = circle{xt, yt, 0}

	// out(xs, ys, xt, yt)
	// out(N, c)
	N = N + 2

	t := make([][]float64, N)
	for i := 0; i < N; i++ {
		t[i] = make([]float64, N)
	}
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			t[i][j] = calc(c[i], c[j])
			t[j][i] = t[i][j]
			// out(i, j, t[i][j])
			// out(j, i, t[j][i])
		}
	}

	// for i := 0; i < N; i++ {
	// 	out(t[i])
	// }
	// out("----")
	cost := Dijkstra(N, 0, t)
	out(cost[N-1])

}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define RREP(i,s,n) for(lli i=s;i>=n;i--)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)

string create(string s,int i){
	lli size = s.size();
	if(i==0)return s;
	return s.substr(size-i) + s.substr(0,size-i);
}

signed main(){

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

	REP(i,0,s.size()){
		string now = create(s,i);
		//cout<<now<<endl;
		if(now==t){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	

	return 0;
}

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

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

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

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;
const ll INF = 1e9 + 7;

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


/////////////////////////////////////////////////////////////////////////////////////////
int main(){
    int n;
    cin >> n;
    int MAX = 100001;
    vector<int> v(n);
    vector<pair<int,int>> odd(MAX),even(MAX);
    int tmp_1 = 0,tmp_2 = 0,a,b;
    for (int i = 0;i < n;i++){
        cin >> v[i];
        if (i % 2 == 0){
            odd[v[i]].first++;
            odd[v[i]].second = v[i];
        }
        else {
            even[v[i]].first++;
            even[v[i]].second = v[i];
        }
    }
    sort(odd.begin(),odd.end(),greater<pair<int,int>>());
    sort(even.begin(),even.end(),greater<pair<int,int>>());

    int ans;
    if (odd[0].second == even[0].second){
        ans = n - max(odd[0].first + even[1].first,odd[1].first + even[0].first);
    }
    else {
        ans = n - odd[0].first - even[0].first;
    }

    cout << ans << endl;
}

Measured memory_bytes: 2176
import java.util.*;

public class Main{
	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] X = new int[N];
		for(int i = 0; i < N; i++) {
			X[i] = sc.nextInt();
		}
		int count = 0;
		for(int i = 1; i < N - 1; i++) {
			if((X[i - 1] < X[i] && X[i] < X[i + 1])||(X[i + 1] < X[i] && X[i] < X[i - 1]))count++;
		}
		System.out.println(count);
	}
}

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

using namespace std;
#define ll long long
#define mod 1000000007

vector<int> g[100001];
ll dp[1000001];

ll f(ll i) {
    if (g[i].empty()) return 0;

    if (dp[i] != -1) return dp[i];

    ll ans = 0;
    for (int j : g[i]) {
        ans = max(ans, 1 + f(j));
    }
    dp[i] = ans;
    return ans;
}

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

    memset(dp, -1, sizeof(dp));
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f(i));
    }
    cout << ans << "\n";
}


Measured memory_bytes: 18984
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        int K = scan.nextInt();
        for (int i = A; i <= Math.min(B,A+K-1); i++) {
            System.out.println(i);
        }
        for (int i = Math.max(B-K+1, A+K); i <= B; i++) {
            System.out.println(i);
        }

    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#define loop(i,a,b) for(int i = a; i < b ; i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(void){
	int mery[8]={1,2,1,2,1,4,1,4};
	
	vector<int> p(8),c(mery,mery+8);
	
	while(cin>>p[0]){
		loop(i,1,8)cin>>p[i];
		int max = -1;
		vector<int> ans,t(8);
		rep(i,8){
			int s=0;
			rep(j,8){
				s+=p[j]>c[(i+j)%8]?c[(i+j)%8]:p[j];
				t[j]=c[(i+j)%8];
			}
			if(max<s || max ==s && t<ans){
				ans = t;
				max = s;
			}
		}
		
			cout<<ans[0];
			loop(i,1,8)cout<<" "<<ans[i];
			cout<<endl;
	}
}

Measured memory_bytes: 1216
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
 
#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
using namespace std;
 
int main(void) {
	string s;
	cin >> s;
	s.insert(s.begin() + 4, ' ');
	cout << s << endl;
	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();
        long[] res = new long[10001];
        for(int x=1; x<=100; x++) {
            for(int y=1; y<=100; y++) {
                for(int z=1; z<=100; z++) {
                    int num = x*x + y*y + z*z + x*y + y*z + z*x;
                    if(num > 10000) continue;
                    res[num]++;
                }
            }
        }
        for(int i=1; i<=n; i++) {
            System.out.println(res[i]);
        }

    }


}

Measured memory_bytes: 38988
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
string str[110];
int main()
{
    int n,l;
    while(scanf("%d%d",&n,&l)!=EOF){
        for(int i=0;i<n;i++){
            cin>>str[i];
        }
        sort(str,str+n);
        for(int i=0;i<n;i++) cout<<str[i];
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

#pragma warning(disable:4996)

char S[100000 + 1];
int zeroS[100000];
int zeroE[100000];

int main(void) {
	int N, K;
	scanf("%d %d", &N, &K);

	scanf("%s", &S[0]);
	int zeroNum = 0;
	char prev = '\0';
	int oi = 0;
	for (int i = 0; i < N; ++i) {
		if (S[i] == '0') {
			if (prev != '0') {
				if (zeroNum > 0) {
					zeroE[zeroNum - 1] = i-1;
				}
				zeroS[zeroNum++] = oi;
			}
		}
		else {
			if (prev != '1') {
				oi = i;
			}
		}
		prev = S[i];
	}
	zeroE[zeroNum-1] = N-1;
	int max = 0;
	for (int i = 0; i < zeroNum; ++i) {
		int index = i + K - 1;
		if (index >= zeroNum) index = zeroNum - 1;
			int len = zeroE[index] - zeroS[i]+1;
			if (len > max) {
				max = len;
			}
	}
	if (zeroNum == 0) {
		max = N;
	}

	printf("%d", max);

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
        int n,a,b;
        scanf("%d",&n);
        if(n==1){
                printf("Hello World\n");
                return 0;
        }
        else {
                scanf("%d%d",&a,&b);
                printf("%d\n",a+b);
                return 0;
        }
}


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


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    string s;cin>>s;
    string ans=s;
    int nl=0,nr=0;
    rep(i,n){
        if(s[i]=='(')nl++;
        else nr++;
        if(nl<nr){ans="("+ans;nr--;}
    }
    rep(i,nl-nr)ans=ans+")";
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int ans=0;
    string s;
    cin>>s;
    for(int i=0;i<6;i++){
        if(s[i]=='1')ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1,
    x=-x;
  }
  while(x){
    f[s++]=x%10,
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
const int SZ=100001;
int a[SZ], cnt[SZ];
int main(){
  int ans, i, n;
  rd(n);
  {
    int lhxun_Zi;
    for(lhxun_Zi=0;lhxun_Zi<n;lhxun_Zi++){
      rd(a[lhxun_Zi]);
    }
  }
  sort(a,a+n);
  for(i=0;i<n;i++){
    if (a[i] >= SZ){
      continue;
    }
    cnt[a[i]]++;
  }
  ans = n;
  for(i=0;i<SZ;i++){
    if (cnt[i] >= i){
      ans -= i;
    }
  }
  wt_L(ans);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20170910-1

// --- original code ---
// const int SZ = 100001;
// int a[SZ];
// int cnt[SZ];
// {
//   int n, ans;
//   rd(n, a(n));
//   sort(a,a+n);
//   rep(i,n) {
//     if (a[i] >= SZ) continue;
//     cnt[a[i]]++;
//   }
//   ans = n;
//   rep(i,SZ) if (cnt[i] >= i) ans -= i;
//   wt(ans);
// }

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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

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

    int N, M;
    cin >> N >> M;
    if(N == 1 && M == 1) cout << 1 << endl;
    else if(N == 1) cout << M - 2 << endl;
    else if(M == 1) cout << N - 2 << endl;
    else cout << N * M - N * 2 - M * 2 + 4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;
int main() {
	int n, a, b;
	int x[100000];
	ll ans = 0;
	scanf("%d%d%d", &n, &a, &b);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x[i]);
	}
	for (int i = 0; i < n - 1; i++) {
		if ((ll)a * (x[i + 1] - x[i]) >= b) {
			ans += b;
		} else {
			ans += (ll)a * (x[i + 1] - x[i]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main(){
	// sengen
	int k;
	string s;
	// nyuryoku
	cin >> k >> s;
	// keisan
	int n = s.size();
	if(n <= k){
		cout << s;
	}else{
		string t = s.substr(0,k);
		cout << t << "...";
	}
	// syutsuryoku
}

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

using namespace std;

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   cin >> n;
   int xr = 0;
   while (n--) {
      int x;
      cin >> x;
      xr ^= x;
   }
   if (xr) {
      puts("No");
   } else {
      puts("Yes");
   }
}


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

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0);
    cin.tie(0);
    long n, m;
    cin >> n >> m;
    priority_queue<long> pq;
    for(long i = 0; i < n; i++) {
        long a;
        cin >> a;
        pq.push(a);
    }
    while(m --){
        long x = pq.top();
        pq.pop();
        pq.push(x/2);

    }
    long price = 0;
    for(long i = 0; i < n; i++){
        price += pq.top();
        pq.pop();
    }
    cout << price;
    return 0;
}


Measured memory_bytes: 1400
N, M = map(int,input().split())

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

R.sort(key=lambda x : x[1])

ans = 0
for i in range(M):
  if i == 0:
    temp = R[i][1]-1 #0個目の終点。この直前で切ればよい。
    ans += 1
  else:
    if R[i][0] > temp:
      temp = R[i][1]-1
      ans += 1
print(ans)

Measured memory_bytes: 18232
import itertools

n=int(input())
a=[]
b=[]
a=tuple(map(int,input().split()))
b=tuple(map(int,input().split()))

aa=0
bb=0
cou=0
c=[]
for i in range(n):
  c.append(i+1)
  
for x in itertools.permutations(c):
  if a==x:
    aa=cou
  if b==x:
    bb=cou
  cou=cou+1
  
print(abs(aa-bb))

Measured memory_bytes: 39280
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef vector<int> vec;
int main(){
  string s; int ans=0; cin>>s;
  rep(i,4){if(s[i]=='+') ans++; else ans--;}
  cout<<ans;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n==0 && m==0) break;
			
			int[] p = new int[n+1];
			for(int i=1;i<=n;i++) p[i] = sc.nextInt();
			
			int[] q = new int[((n+2)*(n+1))/2];
			int r = 0;
			for(int i=0;i<=n;i++){
				for(int j=i;j<=n;j++){
					q[r] = p[i]+p[j];
					r++;
				}
			}
			Arrays.sort(q);
			
			int ans = 0;
			r--;
			for(int i=0;i<r;i++){
				while(r>=0 && q[i]+q[r]>m) r--;
				if(r>=0) ans = Math.max(ans, q[i]+q[r]);
			}
			System.out.println(ans);
		}	
	}	
}

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

int main(){
  int a,b;
  cin >> a >> b;
  int pro = (a+b);
  cout << (pro+1)/2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int main(){
  int a,b=-1;
  scanf("%d",&a);
  int c[a];
  for(int i=0; i<a; i++){
    scanf("%d",&c[i]);
  }
  for(int i=0; i<a; i++){
    for(int j=i+1; j<a; j++){
      if(b<abs(c[i]-c[j])){b=abs(c[i]-c[j]);}
    }
  }
  printf("%d",b);
  return 0;}


Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<cmath>

using namespace std;

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


typedef pair<int,int> pii;

class Line{
	public:
	int sx,sy;
	Line(){}
	Line(int sx,int sy):sx(sx),sy(sy){}
	
	vector<pii> body;
	void add(int x,int y){
		body.push_back(pii(x-sx,y-sy));
	}
	
	void rotate(){
		rep(i,body.size()){
			pii next;
			next.first = -1*body[i].second;
			next.second = body[i].first;
			
			body[i]=next;
		}
	}
	
	void chosei(){
		int dx = body[1].first - body[0].first;
		int dy = body[1].second - body[0].second;
		
		if(dy>0){
			rotate();
			rotate();
			rotate();
		}
		if(dx<0){
			rotate();
			rotate();
		}
		if(dy<0){
			rotate();
		}
	}
	
	void print(){
		puts("print");
		rep(i,body.size()){
			printf("%d %d\n",body[i].first,body[i].second);
		}puts("");
	}
	
	bool equal(Line line){
		if(body.size()!=line.body.size())return false;
		rep(i,line.body.size()){
			if(body[i]!=line.body[i])return false;
		}
		return true;
	}
	bool invequal(Line line){
		if(body.size()!=line.body.size())return false;
		rep(i,body.size()){
			if(body[body.size()-i-1]!=line.body[i])return false;
		}
		return true;
	}
};
int main(){
	while(1){
		int n;
		cin>>n;
		if(n==0)break;
		
		Line lines[111];
		Line invlines[111];
		rep(i,n+1){
			int m;
			cin>>m;
			
			rep(j,m){
				int x,y;
				cin>>x>>y;
				
				if(j==0)lines[i] = Line(x,y);
				lines[i].add(x,y);
			}
			lines[i].chosei();
			
			rep(j,m){
				int x = lines[i].body[m-j-1].first;
				int y = lines[i].body[m-j-1].second;
			
				if(j==0)invlines[i] = Line(x,y);
				invlines[i].add(x,y);
			}
			invlines[i].chosei();
		}
		
		int ans = 0;
		reps(i,1,n+1){
			if(lines[0].equal(lines[i]) || lines[0].equal(invlines[i])){
				ans++;
				printf("%d\n",i);
			}
		}
		
		printf("+++++\n");
	}
}

/*
5
5
0 0
2 0
2 1
4 1
4 0
5
0 0
0 2
-1 2
-1 4
0 4
5
0 0
0 1
-2 1
-2 2
0 2
5
0 0
0 -1
2 -1
2 0
4 0
5
0 0
2 0
2 -1
4 -1
4 0
5
0 0
2 0
2 1
4 1
4 0

*/

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

int main(){
    int64_t N;
    cin >> N;
    
    if(N % 2 == 1 || N < 10){
        cout << 0 << endl;
    } else {
        int64_t ans = 0;
        rep(i, floor(log(N) / log(5))){
            ans += N / ((int64_t)pow(5, i + 1) * 2);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 512