akhauriyash/Code-Regression huggingface dataset:
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define forab(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define fst first
#define snd second
 
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<pii>;

#ifdef LOCAL
#define eprintf(args...) fprintf(stderr, args), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define FILE_NAME "a"
 
string s;
 
bool read() {
    if (!(cin >> s)) {
        return 0;
    }
    return 1;
}

const int mod = (int)1e9 + 7;

void add (int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub (int &a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
}
int mult (int a, int b)
{
    return (ll)a * b % mod;
}
 
int solve() {
    const int n = sz(s);
    assert(n % 2 == 1);

    vi cnt(n + 1);
    ford (i, n)
        cnt[i] = cnt[i + 1] + (s[i] == '?');

    vi pws(n + 1, 1);
    forn (i, n)
        pws[i + 1] = mult(pws[i], 2);

    const int max_one = 6;

    vector<vvi> dp(n + 1, vvi(3, vi(max_one)));
    dp[0][0][0] = 1;

    int ans = 0;
    forn (i, n) forn (zero, 3) forn (one, max_one)
    {
        int cur = dp[i][zero][one];
        if (!cur)
            continue;

        forn (j, 2) if (s[i] != (j ^ 1) + '0')
        {
            if (one == max_one - 1 && j == 1)
            {
                add(ans, mult(cur, pws[cnt[i + 1]]));
                continue;
            }

            if (j == 1)
            {
                int none = one + 1;
                int nzero = zero;
                if (nzero && none)
                    nzero--, none--;

                add(dp[i + 1][nzero][none], cur);
            }
            else
            {
                assert(j == 0);
                int nzero = zero + 1;
                if (nzero == 3) nzero = 1;
                int none = one;

                add(dp[i + 1][nzero][none], cur);
            }
        }
    }

    forn (zero, 3) forn (one, max_one)
    {
        int cur = dp[n][zero][one];
        int nzero = zero, none = one;
        while (nzero && none)
            nzero--, none--;

        if (none)
            add(ans, cur);
    }

    return ans;
}
 
int main() {
#ifdef LOCAL
    freopen(FILE_NAME ".in", "r", stdin);
    freopen(FILE_NAME ".out", "w", stdout);
#endif

    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    while (read()) {
        int ans = solve();
        cout << ans << endl;
//        break;
    }
 
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            ans += d[i] * d[j];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 200228;


int n;
ll a[MAXN];
int cntk[20][20];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		bool was = false;
		for (int j = 0; j < sz(s); j++) {
			if (s[j] == '.') {
				was = true;
			}
		}
		if (!was) {
			a[i] = 0;
			for (int j = 0; j < sz(s); j++) {
				a[i] *= 10;
				a[i] += s[j] - '0';
			}
			a[i] *= 1000000000;
		} else {
			for (int j = 0; j < sz(s); j++) {
				if (s[j] == '.') {
					for (int k = 0; k < j; k++) {
						a[i] *= 10;
						a[i] += s[k] - '0';
					}
					a[i] *= 1000000000;
					ll b = 0;
					int cnt = 0;
					for (int k = j + 1; k < sz(s); k++) {
						b *= 10;
						b += s[k] - '0';
						cnt++;
					}
					for (int k = 0; k < 9 - cnt; k++) {
						b *= 10;
					}
					a[i] += b;
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		int cnt1 = 0;
		while (a[i] % 2 == 0) {
			cnt++;
			a[i] /= 2;
		}
		while (a[i] % 5 == 0) {
			cnt1++;
			a[i] /= 5;
		}
		chkmin(cnt, 18);
		chkmin(cnt1, 18);
		cntk[cnt][cnt1]++;
	}
	ll ans = 0;
	for (int t = 0; t < 19; t++) {
		for (int t1 = 0; t1 < 19; t1++) {
			if (t * 2 >= 18 && t1 * 2 >= 18) {
				ans += (ll)cntk[t][t1] * (cntk[t][t1] - 1) / 2;
			}
			for (int nt = t; nt < 19; nt++) {
				int beg = (nt == t ? t1 + 1: 0);
				for (int nt1 = beg; nt1 < 19; nt1++) {
					if (nt + t >= 18 && nt1 + t1 >= 18) {
						ans += (ll)cntk[t][t1] * cntk[nt][nt1];
					}
				}
			}
		}
	}
	cout << ans << '\n';
}


Measured memory_bytes: 5168
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    let mut v2 = Vec::new();
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        let v = s.trim().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect();
        v2.push(v);
    }
    v2
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main(){
    let stdin = read_vec::<isize>();
    println!("{:?}", 3*stdin[0]*stdin[0]);
}

Measured memory_bytes: 4352
# https://arc061.contest.atcoder.jp/tasks/arc061_a

import sys
import itertools as it

sys.setrecursionlimit(2000)


def solve(s, i):
    # print(s, i)
    if s == "":
        yield 0
    elif i == len(s):
        yield int(s)
    else:
        for x in solve(s[i:], 1):
            yield x + int(s[:i])
        yield from solve(s, i + 1)


S = input().strip()
res = sum(solve(S, 1))
print(res)


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

int main() {
	int		h,a,b,c,i,j,k,n,m,x,y,ans = 0;
	string	str;
	
	cin >> str;
	
	for(i=0;i<str.size();i++) {
		cout << 'x';
	}
	cout << endl;

}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
class people{
public:
    long long int place;
    int dotti;
};
int main(){
    int n;
    long long int T;
    int Q;
    cin>>n>>T>>Q;
    people *house;
    house=new people[n+2];
    for(int i=1;i<=n;++i){
        cin>>house[i].place>>house[i].dotti;
    }
    long long int dummy;
    house[0].dotti=2;
    house[n+1].dotti=1;
    for(int i=1;i+1<=n;++i){
        if(house[i].dotti==1&&house[i+1].dotti==2){
        if(house[i+1].place-house[i].place<=2*T){
            dummy=(house[i].place+house[i+1].place)/2;
            house[i].place=dummy;
            house[i+1].place=dummy;
            for(int j=i-1;j>=1;--j){
                if(house[j+1].place-house[j].place<=T&&house[j].dotti==1){
                    house[j].place=house[j+1].place;
                    house[j].dotti=3;
                }else{
                    break;
                }
            }
            for(int j=i+2;j<=n;++j){
                if(house[j].place-house[j-1].place<=T&&house[j].dotti==2){
                    house[j].place=house[j-1].place;
                    house[j].dotti=3;
                }else{
                    break;
                }
            }
        }else{
            house[i].place+=T;
            house[i+1].place-=T;
        }
        house[i].dotti=3;
        house[i+1].dotti=3;
        }
    }
    for(int i=1;i<=n;++i){
        if(house[i].dotti==2){
            house[i].place-=T;
        }else if(house[i].dotti==1){
            house[i].place+=T;
        }
    }
    int doll;
    for(int i=0;i<Q;++i){
        cin>>doll;
        cout<<house[doll].place<<endl;
    }
    return 0;
}

Measured memory_bytes: 4656
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] a = new int[N];
		int[] res = new int[N];
		int ballCount = 0;

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

		for(int i=N-1; i>=0; i--) {

			int sum = 0;
			for(int j=1; (i+1)*j<=N; j++) {
				sum+= res[(i+1)*j-1];
			}
			if(sum%2==a[i]) {
				res[i] = 0;
			} else {
				res[i] = 1;
				ballCount++;
			}
		}

		System.out.println(ballCount);
		for(int i=0; i<res.length; i++) {
			if(res[i]==1) {
				System.out.println(i+1 + " ");
			}
		}
	}

}

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

int main() {
	int n;
	bool flg = false;
	while(cin >> n, n) {
		int a[4], b[4];
		int c[] = {10,50,100,500};
		int s = 0;
		for(int i = 0; i < 4; i++) {
			cin >> a[i];
			s += a[i] * c[i];
		}
		s-=n;
		for(int i = 0; i < 4; i++) {
			b[3-i] = s/c[3-i];
			s%=c[3-i];
		}

		if(flg) cout << endl;
		flg = true;
		for(int i = 0; i < 4; i++) {
			if(b[i]<a[i])
				cout << c[i] << " " << a[i]-b[i] << endl;
		}
	}
}

Measured memory_bytes: 1160
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

cnd = []
if N%2 == 0:
    for i in range(N//2):
        cnd.append(2*i+1)
        cnd.append(2*i+1)
else:
    for i in range(N//2+1):
        if i == 0:
            cnd.append(0)
        else:
            cnd.append(2*i)
            cnd.append(2*i)
            
B = sorted(A)
if cnd != B:
    print(0)
    exit()

print(pow(2,N//2,mod))

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

int main(){
  long long int n,d,a;
  cin>>n>>d>>a;
  vector<pair<int,int> > v;
  for(int i=0;i<n;i++){
    int x,h;
    cin>>x>>h;
    v.push_back({x,h});
    //v[i].first=x;
    //v[i].second=h;
   }
   sort(v.begin(),v.end());
  long long res=0,temp=0;
  long long a1[n+5];
  memset(a1,0,sizeof(a1));
  d=d*2;
  for(int i=0;i<n;i++){
	  //cout<<v[i].second<<endl;
    v[i].second-=temp;
    if(v[i].second>0){
      long long n1=(v[i].second+a-1)/a;
      temp+=(n1*a);
      res=res+n1;
      int l=i,r=n+1;
      while(l<r-1){
        int mid=(r+l)/2;
        //cout<<mid<<endl;
        if(v[i].first+d>=v[mid].first)
          l=mid;
        else
          r=mid;
      }
      //cout<<l<<endl;
      a1[l]+=n1*a;
    }
    //cout<<res<<endl;
    temp-=a1[i];
  }
  cout<<res;
}


Measured memory_bytes: 3440
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		// ユークリッドの互除法
		long tmp = 0;
		if (A < B) {
			tmp = A;
			A = B;
			B = tmp;
		} // Aが常に大きい

		long r = -1;
		while (r != 0) {
			r = A % B;
			if (r == 0)
				break;
			else {
				A = B;
				B = r;
			}
		} // このときのBが２入力値の最大公約数

		long C = 1;
		Set<Long> memo = new HashSet<Long>();
		long goal = (long)Math.sqrt(B);
		while (Math.sqrt(B) >= C) {
			if (C == 1) {
				memo.add(C);
				C++;
			} else {
				if (B % C == 0) {
					while(B % C == 0) {
						B = B / C;
					}
					memo.add(C);
				}
					C++;
			}
		}
		long ans =0;
		if(B!=1)ans++;
		ans += memo.size();
		System.out.println(ans);
	}
}


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

struct Point {double x, y;};
struct Square {double left, right, top, bottom;};

bool include(const Square& s, const Point& p) {
  return s.left <= p.x && p.x <= s.right && s.bottom <= p.y && p.y <= s.top;
}

bool ok(const vector<Point>& point, double d) {
  Square A = {point.front().x, point.front().x + d, 0, 0};
  Square B = {point.back().x - d, point.back().x, 0, 0};
  double lowA = 1e9, highA = -1e9;
  double lowB = 1e9, highB = -1e9;
  for(const auto& p: point) {
    if(p.x <= A.right) {
      lowA = std::min(lowA, p.y);
      highA = std::max(highA, p.y);
    }
    if(B.left <= p.x) {
      lowB = std::min(lowB, p.y);
      highB = std::max(highB, p.y);
    }
  }
  A.top = highA;    A.bottom = highA - d;
  B.top = lowB + d; B.bottom = lowB;
  if(all_of(begin(point), end(point), [&](const Point& p){return include(A, p) || include(B, p);})) return true;
  A.top = lowA + d; A.bottom = lowA;
  B.top = highB;    B.bottom = highB - d;
  if(all_of(begin(point), end(point), [&](const Point& p){return include(A, p) || include(B, p);})) return true;
  return false;
}

int main() {
  int N;
  cin >> N;
  vector<Point> point(N);
  for(auto& p: point) cin >> p.x >> p.y;
  for(auto& p: point) p = {p.x / sqrt(2) - p.y / sqrt(2), p.x / sqrt(2) + p.y / sqrt(2)};
  sort(begin(point), end(point), [](const Point& lhs, const Point& rhs){return lhs.x < rhs.x;});
  double low = 0, high = 3e5;
  while(1e-3 < high - low) {
    double middle = (low + high) / 2.0;
    ok(point, middle) ? (high = middle) : (low = middle);
  }
  cout << int(high * sqrt(2)) << endl;
}

Measured memory_bytes: 2584
n=int(input())
l=[]
l1=[]
flag=0
for i in range(n):
    a,b=[int(i) for i in input().split()]
    l.append(a)
    l1.append(b)
for i in range(0,len(l)-2):
    if((l[i]==l1[i]) and (l[i+1]==l1[i+1]) and (l[i+2]==l1[i+2])):
        print('Yes')
        flag=1
        break
    else:
        pass
if(flag==0):
    print('No')

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

int main() {
  string x;
  string y;
  cin >> x >> y;

  int X = stoi(x, nullptr, 16);
  int Y = stoi(y, nullptr, 16);

  if(X>Y) {
    cout << ">" << endl;
  } else if (X == Y) {
    cout << "=" << endl;
  } else {
    cout << "<" << endl; 
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main (int argc, char const *argv[])
{
    int64_t N, K;
    char S[51];
    int64_t ans = 0;

    scanf("%"PRId64"%"PRId64, &N, &K);
    scanf("%s", S);

    S[K - 1] |= 0x20;

    printf("%s\n", S);

    return 0;
}


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

vector<string>V;
int find(string s){
	for(int i=0;i<V.size();i++)if(V[i]==s)return 1;
	return 0;
}

int d[3][6]={
	{3,0,1,2,4,5},
	{4,1,5,3,2,0},
	{0,4,2,5,3,1}
};
string rot(string s,int n){
	string S=s;
	for(int i=0;i<6;i++)S[i]=s[d[n][i]];
	return S;
}
int step[12]={0,1,0,1,0,1,0,1,2,0,2,0};
int STEP[12]={4,1,4,1,4,1,4,1,1,4,2,4};

string cng(string s){
	string S=s;
	S[0]=s[3];
	S[1]=s[0];
	S[2]=s[2];
	S[3]=s[5];
	S[4]=s[4];
	S[5]=s[1];
	return S;
}

int main(){
	
	for(int n;cin>>n,n;){
		V.clear();
		for(int i=0;i<n;i++){
			string s="",t;
			for(int j=0;j<6;j++){
				cin>>t;
				s+=t[0];
			}
			s=cng(s);
			int f=1;
			for(int j=0;j<12;j++){
				for(int k=0;k<STEP[j];k++){
					s=rot(s,step[j]);
					if(find(s))f=0;
				}
			}
			if(f)V.push_back(s);
		}
		cout<<n-V.size()<<endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 1216
import java.util.Scanner;

public class Main {
	public static void main(String[]args){
		//????????£????????????
		Scanner sc = new  Scanner(System.in);
		//??¨ ?????° ???
		int r = sc.nextInt();
		//??¨ ?????° ???
		int c= sc.nextInt();
		//??¨?????????
		int [][] table = new int [r+1][c+1];
		//int i =0;
		//int j = 0;
		for(int i =0; i<r;i++){
			for(int j =0;j<c;j++){
				//??¨?????????????´?
				table[i][j] = sc.nextInt();
			}
		}
		//
		for(int i =0;i<r;i++){
			for(int j=0;j<c;j++){
				table[i][c] += table[i][j];
				table[r][j] += table[i][j];
				table[r][c]+= table[i][j];
			}
		}
		//??¨?????????
		for(int i= 0; i<=r; i++){
			System.out.print(table[i][0]);
			for(int j =1;j<=c;j++){
				System.out.print(" " +table[i][j]);
			}
		System.out.println();
		}
	}
}

Measured memory_bytes: 42032
def gcd(a, b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

N = int(input()) 
A = [0] + list(map(int, input().split()))

# L[i]: gcd(A1,...,Ai)
# R[i]: gcd(Ai,...,AN)
L = [0]*(N+2)
R = [0]*(N+2)

L[1] = A[1]
R[N] = A[N]
for i in range(N-1):
    L[i+2] = gcd(L[i+1], A[i+2])
    R[N-i-1] = gcd(A[N-i-1], R[N-i])

res = 0
for i in range(1, N+1):
    rm_i = gcd(L[i-1], R[i+1])
    if res < rm_i:
        res = rm_i
print(res)

Measured memory_bytes: 14436
#include<bits/stdc++.h>
using namespace std;
const long long md=998244353;
const int maxn=300100;
long long fac[maxn],inv[maxn];
long long powd(long long x,long long y){
	long long res=1;
	while(y){
		if(y&1) res=res*x%md;
		x=x*x%md;
		y>>=1;
	}
	return res;
}
void csh(){
	fac[0]=1;
	for(int i=1;i<=300000;i++)
		fac[i]=fac[i-1]*i%md;
	inv[300000]=powd(fac[300000],md-2);
	for(int i=300000;i>=1;i--)
		inv[i-1]=inv[i]*i%md;
}
long long C(int x,int y){
	return fac[x]*inv[y]%md*inv[x-y]%md;
}
int main(){
	csh();
	long long n,a,b,k;
	scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
	long long ans=0;
	for(int i=0;i<=n;i++){
		if(i*a>k||(k-i*a)%b!=0||(k-i*a)/b>n) continue;
		ans=(ans+C(n,i)*C(n,(k-i*a)/b))%md;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000009;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
vector<int>g[1100];
int c[1100];
int dp2[1100];
bool ok=true;
int dp[1100][5100];
void solve(int a){
	for(int i=0;i<g[a].size();i++){
		solve(g[a][i]);
	}
	if(!ok)return;
	int n=g[a].size();
	for(int i=0;i<=n;i++)for(int j=0;j<5100;j++)dp[i][j]=mod;
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		int A=c[g[a][i]];
		int B=dp2[g[a][i]];
		for(int j=0;j<5100;j++){
			if(dp[i][j]<mod){
				if(j+A<5100)dp[i+1][j+A]=min(dp[i+1][j+A],dp[i][j]+B);
				if(j+B<5100)dp[i+1][j+B]=min(dp[i+1][j+B],dp[i][j]+A);
			}
		}
	}
	int rm=mod;
	for(int i=0;i<=c[a];i++){
		rm=min(rm,dp[n][i]);
	}
	if(rm==mod)ok=false;
	dp2[a]=rm;
	//printf("%d: %d\n",a,dp2[a]);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=1;i<a;i++){
		int b;
		scanf("%d",&b);
		b--;g[b].push_back(i);
	}
	for(int i=0;i<a;i++)scanf("%d",c+i);
	solve(0);
	if(ok)printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
}

Measured memory_bytes: 20736
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long ll;
#define pb push_back

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

    int x;
    cin >> x;
    if (x == 0)
        cout << 1;
    else if (x == 1)
        cout << 0;

    return 0;
}


Measured memory_bytes: 3644
import math

n = int(input())
hL = list(map(int, input().split(" ")))

ans = 0
for i in range(1, 101):
    r = False
    for h in hL:
        if i <= h:
            if not r:
                ans += 1
            r = True
        else:
            r = False

print(ans)

Measured memory_bytes: 64856
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#define fi first
#define se second
#define pb push_back
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define L(i,u) for (int i=head[u]; i!=0; i=edge[i].nxt)
#define abs(a) ((a)>0 ? (a) : -(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
typedef long long ll;
typedef long double ld;
map<int,int> Map;
map<int,int> ::iterator it;
int n;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
	while (c>='0'&&c<='9') {x=10*x+c-'0'; c=getchar();} x*=f;
}

int main() {
	read(n); rep(i,1,n) {int x; read(x); Map[x]++;}
	int ans=0;
	while (!Map.empty()) {
		it=Map.begin();
		if ((*it).se>=(*it).fi) ans+=(*it).se-(*it).fi;
		else ans+=(*it).se;
		Map.erase(it);
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 4736
#include<algorithm>
#include<string>
#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
 
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
 
int main(){
    int n;
    cin >> n;
    vector<int> t(n);
    int sum=0;
    REP(i,n){
        cin >> t[i];
        sum += t[i];
    }
    int m;
    cin >> m;
    vector<int> p(m),x(m);
    REP(i,m){
        cin >> p[i] >> x[i];
    }
    int ans;
    REP(i,m){
        ans = sum;
        ans += x[i] - t[p[i]-1];
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ll N,M;
    cin>>N>>M;
    vll A(N),acc(N);
    for (size_t i = 0; i < N; i++)
    {
        cin>>A[i];
    }
    partial_sum(all(A),acc.begin());
    map<ll,ll> cnt;
    for (auto &&i : acc)
    {
        cnt[i%M]++;
    }
    ll ans=0;
    for (auto &&i : cnt)
    {
        if(i.first == 0)
        ans += i.second + i.second*(i.second-1)/2;
        else
        ans += i.second*(i.second-1)/2;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 5760
#include <iostream>

using namespace std;

int main(void) {

    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;

    bool over = false;

    if (x + r > W || x - r < 0 || y + r > H || y - r < 0) over = true;

    cout << (over ? "No" : "Yes") << endl;

    return 0;
}



Measured memory_bytes: 3104
#coding:utf-8

n = int(input())
p = list(map(int,input().split()))
#print(p)

counter = 0

for i in range(1, n-1):
    #print(i)
    if (p[i] < p[i+1] and p[i] > p[i-1]) or (p[i] > p[i+1] and p[i] < p[i-1]):
        counter += 1

print(counter)


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int testcase_ends() {
  intmax_t m, n;
  scanf("%jd %jd", &m, &n);

  if (m == 0 && n == 0)
    return 1;

  int N=7368800;
  std::vector<bool> res(N);
  for (int i=m; n; ++i) {
    if (res[i]) {
      continue;
    }

    --n;
    for (int j=i; j<N; j+=i) {
      res[j] = true;
    }
  }

  for (int i=m; i<N; ++i) {
    if (!res[i]) {
      printf("%d\n", i);
      break;
    }
  }
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 3568
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		String ans = "";
		n = n % 10;
		if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
			ans = "hon";
		if (n == 0 || n == 1 || n == 6 || n == 8)
			ans = "pon";
		if (n == 3)
			ans = "bon";

		System.out.println(ans);
	}
}



Measured memory_bytes: 35732
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
c = 0

pre = 0
for i in range(N):
    now = A[i] - 1
    c += B[now]
    if i != 0 and pre == now - 1:
        c += C[pre]
    pre = now
print(c)

Measured memory_bytes: 3188
use std::cmp::*;
use std::io::*;
use std::num::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn string() -> String {
    read()
}

fn int() -> i64 {
    read()
}

fn char() -> char {
    read::<String>().pop().unwrap()
}

fn vecchar() -> Vec<char> {
    string().chars().collect()
}

fn vecint(n: i64) -> Vec<i64> {
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(int())
    }
    vec
}

fn main() {
    let s1 = vecchar();
    let s2 = vecchar();
    for i in 0..3 {
        if s1[i] != s2[2 - i] {
            println!("NO");
            return;
        }
    }
    println!("YES")
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void)
{
    int i,j;
    int A[20];
    int B[20];
    int N,M,C;
    int ret = 0;
    int sum;
    scanf("%d %d %d",&N,&M,&C);
    for(i = 0 ; i < M ; i++){
        scanf("%d",&(B[i]));
    }
    for(i = 0 ; i < N; i++){
        sum = 0;
        for(j = 0 ; j < M ; j++){
            scanf("%d",&(A[j]));
            sum += B[j]*A[j];
        }
        //条件を満たすか判定する
        if((sum + C) > 0){
            ret++;
        }
    }
    printf("%d\n",ret);
    return 0;
}


Measured memory_bytes: 1724
def loadIcicle():
	icicles = []
	line = input().strip().split(" ")
	N, L = int(line[0]), int(line[1])
	while True:
		icicles.append(int(input().strip()))
		if len(icicles) == N: break
	return icicles, N, L
icicles, N, L = loadIcicle()

def calcDiff(icicles, N):
	diff_2times = [0]*N

	for idx in range(N):
		dif_right = icicles[idx+1] - icicles[idx] if idx != N-1 else -icicles[idx]
		dif_left = icicles[idx] - icicles[idx-1] if idx != 0 else icicles[idx]

		dif_right = 1 if dif_right > 0 else -1
		dif_left = 1 if dif_left > 0 else -1

		if dif_right - dif_left < 0: diff_2times[idx] = -1
		elif dif_right - dif_left > 0: diff_2times[idx] = 1
		else: diff_2times[idx] = 0

	return diff_2times

diff_2times = calcDiff(icicles, N)

time = [-1]*len(icicles)
peakX = [i for i in range(N) if diff_2times[i]==-1]
for i in peakX:
	time[i] = L - icicles[i]

	isLocalMinL, isLocalMinR = False, False
	posL = i
	posR = i
	while not (isLocalMinL and isLocalMinR):
		posL -= 1
		if posL < 0:
			isLocalMinL = True
		if not isLocalMinL:
			if time[posL] == -1:
				time[posL] = (L-icicles[posL]) + time[posL+1]
			else:
				time[posL] = (L-icicles[posL]) + max(time[posL-1], time[posL+1])

			if diff_2times[posL] == 1:
				isLocalMinL = True

		posR += 1
		if posR >= N:
			isLocalMinR = True
		if not isLocalMinR:
			if time[posR] == -1:
				time[posR] = (L-icicles[posR]) + time[posR-1]
			else:
				time[posR] = (L-icicles[posR]) + max(time[posR-1], time[posR+1])

			if diff_2times[posR] == 1:
				isLocalMinR = True
print(max(time))

Measured memory_bytes: 17784
#include<cstdio>
#include<cstring>
char str[100005];
int main()
{
    scanf("%s",str);
    int len=strlen(str);
    if(str[0]==str[1])
    {
        printf("1 2\n");
        return 0;
    }
    for(int i=2;i<len;i++)
    {
        if(str[i]==str[i-1])
        {
            printf("%d %d\n",i,i+1);
            return 0;
        }
        else if(str[i]==str[i-2])
        {
            printf("%d %d\n",i-1,i+1);
            return 0;
        }
    }
    printf("-1 -1\n");
    return 0;
}


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

int main(void) {

    long long int N;
    cin >> N;

    long long int minNum=1e15;
    vector<long long int> nums(5);
    for(int i=0;i<5;i++){
        cin >> nums[i];
        if( nums[i] < minNum )  minNum = nums[i];
    }

    long long int ans;
    if( N % minNum == 0 ) ans = N/minNum;
    else                ans = (N/minNum)+1;
    cout << ans + 4 << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

    static int countDivisors(int n)
    {
    	int count=0;
        for (int i=1; i<=Math.sqrt(n); i++)
        {
            if (n%i==0)
            {
                if (n/i == i) {
                	if(i%2!=0)
                		count++;
                }
                    
      
                else {
                	if (i%2!=0) count++;
                	if ((n/i)%2!=0) count++;
                } 
                    
            }
        }
        return count;
    }
    	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int count=0;
		if (A==105) System.out.println(1);
		else if(A>105) {
			while(A>105) {
				if(countDivisors(A)==8) {
					count++;
				}
				A--;
			}
			System.out.println(count+1);
		}
		else System.out.println(0);
		
	}

}


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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
int main() {
  int a,b,c;cin>>a>>b>>c;
  int ans=b/a;
  ans=min(ans,c);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
inline int msbp(int x) {return 31-__builtin_clz(x);}
inline int msb(int x) {return 1 << msbp(x);}
typedef long long ll;
typedef pair<int, int> pii;
// const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int INF = 0x3f3f3f3f;
// const int INF = INT_MAX;
// const int nINF = INT_MIN;
// const ll INF = LLONG_MAX;
// const ll nINF = LLONG_MIN;

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

const int N = 2e5+10;

int n;
ll ans;
pii p[N];
map<pii, int> m;

signed main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    cin >> n;
    REP(i, n) {
    	string a;
    	cin >> a;
    	int id = a.find(".");
    	int two = 0, five = 0;
    	ll num;
    	if(id != -1) {
	    	num = stoll(a.substr(0, id)+a.substr(id+1));
	    	int tens = a.size()-1-id;
	    	two = -tens, five = -tens;
    	} else {
    		num = stoll(a);
    	}
    	while(num % 2 == 0) {
    		++two;
    		num /= 2;
    	}
    	while(num % 5 == 0) {
    		++five;
    		num /= 5;
    	}
    	for(auto [pr, freq] : m) {
    		auto [j, k] = pr;
    		if(j+two >= 0 && k+five >= 0) {
    			ans += freq;
    		}
    	}
    	p[i] = {two, five};
    	++m[p[i]];
    }
    cout << ans << endl;

    return 0;
}

// Easy things to check:
// - LONG LONGS (WA)
// - const int N is correct (WA, RTE) CHECK IF IT SHOULD BE 2*N!!!!
// - .size()-k underflow (WA, RTE, TLE)
// - small n edge cases (WA)

// Rare mistakes made in the past:
// - division by 0 (WA)
// - negative arithmetic, ceiling division, modulo (WA)
// - setprecision (WA)
// - INF not big enough using ll (WA)
// - setting max to 0 instead of -INF/min to 0 instead of INF (WA)
// - outputting debug (WA)
// - allocating too much memory (locRTE, MLE)
// - stack size (locRTE)
// - round announcements (WA)
// - multiset::erase (WA)
// - forgetting to rename recursive call when copy/pasting recursive function (WA)
// - not clearing DS between test cases EVEN FOR INPUT (WA, RTE, TLE, MLE)


Measured memory_bytes: 5152
#include <bits/stdc++.h>
using namespace std;
long long int mod = 998244353;

int main() { 
  long long int n, d_, p, ans = 1;
  cin >> n;
  map<long long int, long long int> d;
  for(int i = 0; i < n; ++i) {
    cin >> d_;
    d[d_]++;
    if(d_ != 0 && i == 0) {
        cout << 0 << '\n';
        return 0;
    }
  }

  auto begin = d.begin(), end = d.end();
  if(begin->first != 0 || begin->second != 1) {
    cout << 0 << '\n';
    return 0;
  }

  for(auto iter = begin; iter != next(end, -1); iter++) {
    if(iter->first != (next(iter, 1)->first)-1) {
      cout << 0 << '\n';
      return 0;
    }
    p = 1;
    for(int i = 0; i < next(iter, 1)->second; ++i) {
      p *= iter->second;
      p %= mod;
    }
    ans *= p;
    ans %= mod;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 6528
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: n,k,i,j,ans
    logical,allocatable:: h(:)

    read*, n,k
    allocate(h(n))
    h(:) = .false.

    do i=1,k
        block
            integer(int32):: d
            integer(int32), allocatable:: a(:)

            read*, d
            allocate(a(d))
            read*, a(:)
            do j=1,d
                h(a(j)) = .true.
            end do
        end block
    end do

    ans=0
    do i=1,n
        if (.not.h(i)) ans=ans+1
    end do
    print'(i0)', ans
end program name

Measured memory_bytes: 2932
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <limits.h>

using namespace std;

int main(int argc, char const* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int sum = -N;
    for (int i=0; i<N; ++i) {
        int ai;
        cin >> ai;
        sum += ai;
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input) {
	input = input.split(" ");
	
	var a = parseInt(input[0], 10);
	var b = parseInt(input[1], 10);
	
    console.log("%d", Math.ceil((a + b) / 2));
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21192
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int top, S[1000];

void push(int x) {
  S[++top] = x;
}

int pop () {
  --top;
  return S[top + 1];
}

int main() {
  int a, b;
  top = 0;
  char s[100];
  while (scanf("%s", s) != EOF) {
    if (s[0] == '+') {
      a = pop();
      b = pop();
      push(a + b);
    } else if (s[0] == '-') {
      a = pop();
      b = pop();
      push(b - a);
    } else if (s[0] == '*') {
      a = pop();
      b = pop();
      push(b * a);
    } else {
      push(atoi(s));
    }
  }

  cout << pop() << endl;
  return 0;
}



Measured memory_bytes: 3148
def main():
    n = list(input())
    k = int(input())
    N = len(n)
    for i in range(N):
        n[i] = int(n[i])
    dp1 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp2 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp1[0][0] = 1
    for i in range(N):
        for j in range(k+1):
            dp2[i+1][j] += dp2[i][j]
            if j < k:
                dp2[i+1][j+1] += dp2[i][j]*9
            if n[i]:
                dp2[i+1][j] += dp1[i][j]
                if j == k:
                    continue
                dp1[i+1][j+1] += dp1[i][j]
                dp2[i+1][j+1] += dp1[i][j] * (n[i]-1)
            else:
                dp1[i+1][j] += dp1[i][j]
    print(dp1[N][k]+dp2[N][k])
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
import java.text.ParseException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();

		List<Integer> list = new ArrayList<>();

		for (int i = 1; i <= 100; i++) {

			if (a % i == 0 && b % i == 0) {

				list.add(i);


			}

		}

		System.out.println(list.get(list.size() - k));

		sc.close();
	}

}



Measured memory_bytes: 23380
N = int(input())

if N % 2 == 1:
  print(0)
else:
  a = 0
  '''for i in range(1, 19):
    a += N // (10**i)'''
  j = 1
  b = 1
  while b > 0:
    b = N // ((5 ** j) * 2)
    j += 1
    a += b
  print(a)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

#define INF 10000000000

ll a, b, c, n, m, x, y, z, w, h, ans = 0, cnt = 0, mx = 0, mn = INF;
string s;

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

    cin >> n >> m >> x;
    ll left = 0, right = 0;
    rep(i, m){
        cin >> a;
        if(a < x){
            left++;
        }else{
            right++;
        }
    }
    cout << min(left, right) << endl;
}



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

int main() {
  int N = 0, M = 0;
  cin >> N >> M;
  
  int lb = 0, rb = N;
  vector<int> L(M, 0), R(M, 0);
  for (int i = 0; i < M; ++i) {
    cin >> L[i] >> R[i];
    if (L[i] > lb) {
      lb = L[i];
    }
    if (R[i] < rb) {
      rb = R[i];
    }
  }
  
  cout << max(rb - lb + 1, 0) << endl;
  
  return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#include<set>
#include<utility>
#include<iomanip>
#define IO ios::sync_with_stdio(false)
#define eps 1e-7
#define int long long
using namespace std;
int n,m,k,a[200005],b[200005],suma[200005],sumb[200005],ans=-1;
signed main()
{
	IO;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		suma[i]=suma[i-1]+a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>b[i];
		sumb[i]=sumb[i-1]+b[i];
	}
	for(int i=0;i<=n;i++)
	{
		if(suma[i]>k)break;
		int x=upper_bound(sumb+1,sumb+m+1,k-suma[i])-sumb;
		ans=max(ans,i+x-1);
	}
	cout<<ans;
}

Measured memory_bytes: 9868
//こんな問題予選に出たら解きたくないわ〜





#include <cstdio>
#include <deque>
using namespace std;

int main(){

while(1){
	int n,m,p,q,r;
	deque<pair<int,int> > d;
	
	scanf("%d",&n);
	
	if(n == 0) break;
	
	scanf("%d%d%d%d",&m,&p,&q,&r);
	
	
	d.push_back(make_pair(1,n));
	
	for(int i = 0;i < m;i++){
		int x,y,g = 0;
		scanf("%d%d",&x,&y);
		
		deque<pair<int,int> > a,b;
		
		while(1){
			pair<int,int> nau = d.front(); d.pop_front();
			g += nau.second - nau.first + 1;

			
			if(g == x){
				a.push_back(nau);
				break;
			}else if(g < x){
				a.push_back(nau);
			}else{
				a.push_back(make_pair(nau.first,nau.second-(g-x)));
				d.push_front(make_pair(nau.second-(g-x)+1,nau.second));
				break;
			}
		}
		g = x;
		while(1){
			pair<int,int> nau = d.front(); d.pop_front();
			
			g += nau.second - nau.first + 1;
			
			if(g == y){
				b.push_back(nau);
				break;
			}else if(g < y){
				b.push_back(nau);
			}else{
				b.push_back(make_pair(nau.first,nau.second-(g-y)));
				d.push_front(make_pair(nau.second-(g-y)+1,nau.second));
				break;
			}
		}
		
		for(int i = 0;i < b.size();i++) d.push_back(b[i]);
		for(int i = 0;i < a.size();i++) d.push_back(a[i]);
		
	}
	
	int g = 0,pre = 0;
	int ans = 0;
	while(1){
		if(pre > q || d.empty()) break;
		pair<int,int> nau = d.front(); d.pop_front();
		g += nau.second - nau.first + 1;
		
		if(g < p){
			pre = g + 1;
			continue;
		}
		int st=nau.first,fi=nau.second;	
		
		if(pre < p) st += p - pre;
		
		if(g > q) fi -= (g - q);
		
		pre = g + 1;
		
		if(st > r)continue;
		
		if(fi <= r){
			ans += fi - st + 1;
		}else{
			ans += r - st + 1;
		}
	}
	
	printf("%d\n",ans);
	
	}	
	return 0;
	
}	


Measured memory_bytes: 1164
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
using namespace std;
 
int main(){
   int al=0,bl=0,cl=0,dl=0;
   int ar=0,br=0,cr=0,dr=0;
   double l,r;
   while(cin>>l>>r){
       if(l>=1.1) al++;
       else if(l>=0.6) bl++;
       else if(l>=0.2) cl++;
       else dl++;

       if(r>=1.1) ar++;
       else if(r>=0.6) br++;
       else if(r>=0.2) cr++;
       else dr++;
   }
   cout<<al<<" "<<ar<<endl;
   cout<<bl<<" "<<br<<endl;
   cout<<cl<<" "<<cr<<endl;
   cout<<dl<<" "<<dr<<endl;
    return 0;
}


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

typedef long long ll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define endl '\n'
#define mod 1000000007
#define PI 3.1415926535897932384626

#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()

void io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}

int main() {
	io();
	
	ll a;
	string b;
	cin>>a>>b;
	int bc=(b[0]-'0')*100+(b[2]-'0')*10+(b[3]-'0');
	cout<<(a*bc)/100;
	return 0;
}

Measured memory_bytes: 3660
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
long nCr(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
int a[100010], n, cnt;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		cnt += a[i];
		cnt -= i + 1;
	}
	cout << cnt << endl;
}


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

int main(){
    ll n,h,w,ans;
    cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1;
        return 0;
    }
    ans = (h * w + 1) / 2;
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    max_A = max(A)
    half_max_A = max_A / 2
    dist = [abs(half_max_A - a) for a in A]
    ans = 0
    best = 1000000005
    for i, d in enumerate(dist):
        if best > d and max_A > A[i]:
            best = d
            ans = A[i]

    print(max_A, ans)


Measured memory_bytes: 62956
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int ways = s.size();
  for(int rot = 0; rot < 2; rot++){
    int diff = 0;
    for(int i = 0; i < s.size(); i++){
      if((i+rot)%2 == 0 && s[i] == '0') diff++;
      if((i+rot)%2 == 1 && s[i] == '1') diff++;
    }
    ways = min(ways, diff);
  }
  cout << ways << endl;
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int n=0,a[100005]={0},m=0;
long long ans=0;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<n;i++)
	{
		if(m>=1 && a[i]>=1){a[i]--;ans++;}
		ans+=a[i]/2;
		m=a[i]%2;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 640
import bisect

N=int(input())
L=[int(i) for i in input().split()]

L.sort()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        x=L[i]+L[j]
        ans+=(bisect.bisect_left(L,x)-j-1)

print(ans)


Measured memory_bytes: 74464
<?php
 fscanf(STDIN, "%d", $n);
 $l[0] = 2;
 $l[1] = 1;
 for($i = 2; $i <= $n; $i++) {
     $l[$i] = $l[$i-2] + $l[$i-1];
 }
 //var_dump($l);
 echo $l[$n]."\n";

Measured memory_bytes: 4728
character(10) :: a,b,c
read*,a,b,c

i = len_trim( a )
if( a(i:i)/=b(1:1) ) goto 100

i = len_trim( b )
if( b(i:i)/=c(1:1) ) goto 100

print*,'YES'
stop

100 print*,'NO'
end


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <stack>
#define rep(i, s, g) for (i = s; i <= g; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1e9 + 7;

int main(void)
{
    string K;
    int D;
    int i, j, k, l;
    int d;
    static ll dp[10010][100][2];

    cin >> K >> D;

    l = K.size();

    dp[0][0][0] = 1;

    rep(i, 0, l - 1)
    {
        int nd = K[i] - '0';

        rep(j, 0, D - 1)
        {
            rep(k, 0, 1)
            {
                rep(d, 0, 9)
                {
                    int ni = i + 1, nj = (j + d) % D, nk = k;

                    if (k == 0)
                    {
                        if (nd < d)
                        {
                            continue;
                        }
                        else if (nd > d)
                        {
                            nk = 1;
                        }
                    }

                    dp[ni][nj][nk] += dp[i][j][k] % MOD;
                    dp[ni][nj][nk] %= MOD;
                }
            }
        }
    }

    cout << (dp[l][0][0] + dp[l][0][1] - 1 + MOD) % MOD << endl;
}

Measured memory_bytes: 15872