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

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

template<class T>
inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T>
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T>
T GCD(T a, T b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
template<class T>
T LCM(T a, T b) {
	return a / GCD(a, b) * b;
}
template<class T>
inline T round_int(T a, T b) {return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	ll n;
	cin >> n;
	vl t(n);
	rep(i, n) cin >> t[i];

	if (n == 1) {
		cout << t[0] << endl;
	}
	else if (n == 2) {
		cout << LCM(t[0], t[1]) << endl;
	}
	else {
		ll ans = LCM(t[0], t[1]);
		for(ll i = 2; i < n; ++i) {
			ans = LCM(ans, t[i]);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<algorithm>
#include<complex>
#include<cstdlib>
#include<cctype>

#define REP(i,n) for(int i = 0;i < (n);i++)
#define PB push_back
#define MP make_pair
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cout << v[i] << ' ';cout << endl << endl;}
#define SHOW2d(v,i,j) {for(int a = 0;a < i;a++){for(int b = 0;b < j;b++)cout << v[a][b] << ' ';cout << endl;}cout << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int main()
{
	int n,m;
	
	cin >> n >> m;
	
	iiv v(n+1);
	
	REP(i,m)
	{
		int a,b;
		cin >> a >> b;
		v[a].PB(b);v[b].PB(a);
	}
	
	REP(i,v[1].size())
	{
		
		int tmp = v[1][i];
		REP(j,v[tmp].size())
		{
			if(v[tmp][j] == n)
			{
				cout << "POSSIBLE" << endl;
				return 0;
			}
		}
	}
	
	cout << "IMPOSSIBLE" << endl;
	
	
	
	
	return 0;
}

Measured memory_bytes: 12016
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    cout << n * n * n << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <cstring>
const int MAX_W = 100, MAX_H = 100;

typedef std::pair<int,int> P;
int map[MAX_H + 1][MAX_W + 1];

int bfs(P sp, P gp, int w, int h, int c){
	//½±Æª é©ði[
	int f[MAX_H + 1][MAX_W + 1] = {{0}};
	std::queue<P> q;
	q.push(P(sp.first, sp.second));
	
	while(q.size()){
		P p = q.front(); q.pop();
		//S[Å«½ç¬÷
		if(p.first == gp.first && p.second == gp.second && map[p.second][p.first] == c)return 1;
		
		int vy[4] = {-1,1,0,0}, vx[4] = {0,0,-1,1};
		for(int i=0;i<4;i++){
			int nx = p.first + vx[i],
				ny = p.second + vy[i];
			if(nx >= 0 && nx <= w && ny >= 0 && ny <= h && 
				 map[ny][nx] == c && !f[ny][nx]){
				q.push(P(nx,ny));
				f[ny][nx] = 1;
			}
		}
	}

	//ÅãÜÅS[Å«È¢Èç¸s
	return 0;
}

int main(){
	int w, h, xs, ys, xg, yg;
	while(std::cin >> w >> h, w&&h){
		memset(map,0,sizeof(map));
		std::cin >> xs >> ys;
		std::cin >> xg >> yg;

		int n;
		std::cin >> n;

		//ubNÌÝu
		while(n--){
			int c, d, x, y;
			std::cin >> c >> d >> x >> y;
			
			int mx, my;
			if(d)//w < h
				{my = 4, mx = 2;}
			else//w > h
				{mx = 4, my = 2;}
			for(int i=y;i<y+my;i++){
				for(int j=x;j<x+mx;j++){
					map[i][j] = c;
				}
			}
		}

		//bfsÅS[Å«é©mF
		P sp = P(xs,ys), gp = P(xg,yg);
		int c = map[ys][xs];
		if(bfs(sp, gp, w, h, c))std::cout << "OK" << std::endl;
		else{std::cout << "NG" << std::endl;}
	}
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#define FR first
#define SE second
#define MOD 1000000007

using namespace std;

typedef pair<int,int> pr;

int f[2][305][305];

inline void update(int &x,int y) {
  x=(x+y)%MOD;
}

vector <pr> vt[305];

bool check(int x,int y,int z) {
  for(int i=0;i<vt[x].size();i++) {
  	pr t=vt[x][i];
    if ((x>=t.FR)+(y>=t.FR)+(z>=t.FR)!=t.SE) return 0;
  }
  return 1;
}

int dp(int n) {
  int cur=0;
  f[0][0][0]=1;
  for(int i=0;i<n;i++) {
    cur^=1;
    memset(f[cur],0,sizeof(f[cur]));
    for(int j=0;j<=i;j++)
    for(int k=0;k<=j;k++)
    if (f[cur^1][j][k]) {
    	if (check(i+1,j,k)) update(f[cur][j][k],f[cur^1][j][k]);
    	if (check(i+1,i,k)) update(f[cur][i][k],f[cur^1][j][k]);
    	if (check(i+1,i,j)) update(f[cur][i][j],f[cur^1][j][k]);
	}
  }
  int ans=0;
  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++) update(ans,f[cur][i][j]);
  return ans;
}

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++) {
  	int x,y,z;
  	scanf("%d%d%d",&x,&y,&z);
  	vt[y].push_back(pr(x,z));
  }
  printf("%d\n",dp(n));
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long  
#define mod 1000000007
#define am 998244353
#define INFi 2147483647
#define INFl 9223372036854775807LL
#define fi first
#define se second
#define be begin()
#define en end()
int abs(int a,int b){ 
  int c=max(a,b)-min(a,b);
  return c;
}
int gcd(int a,int b){//最大公約数
  int c=a%b;
  while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
  }
  return b;
}
bool IsPrime(int num){
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;
  double sqrtNum = sqrt(num);
  for(int i=3;i<=sqrtNum;i+=2){
    if(num%i==0){
      return false;
    }
  }
}
int lcm(int a,int b){//最小公倍数
    return (a*b)/gcd(a,b);
}	    
string w[1000];
queue<pair<int,int> > q;
signed main(){
// __builtin_ctz(N);      Nを２で何回割り切れるかを返す
//(n+1)*n/2;              １からNまでの総和を求める式
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a;
    cin>>a;
    cout<<a*a<<"\n";
}



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

typedef long long ll;

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

    int h,w;
    cin >> h >> w;
    char s[2050][2050];
    for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin >> s[i][j];
    int l[2050][2050],r[2050][2050],d[2050][2050],u[2050][2050];
    for(int i=0;i<2050;i++){
        for(int j=0;j<2050;j++){
            l[i][j] = 0;
            r[i][j] = 0;
            d[i][j] = 0;
            u[i][j] = 0;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                l[i][j] = 0;
            }
            else if(j==0) l[i][j] = 1;
            else if(j>0) l[i][j] = l[i][j-1] + 1;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=w-1;j>=0;j--){
            if(s[i][j]=='#'){
                r[i][j] = 0;
            }
            else if(j==w-1) r[i][j] = 1;
            else if(j<w-1) r[i][j] = r[i][j+1] + 1;
        }
    }
    for(int i=h-1;i>=0;i--){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                d[i][j] = 0;
            }
            else if(i==h-1) d[i][j] = 1;
            else if(i<h-1) d[i][j] = d[i+1][j] + 1;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                u[i][j] = 0;
            }
            else if(i==0) u[i][j] = 1;
            else if(i>0) u[i][j] = u[i-1][j] + 1;
        }
    }
    int ans = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ans = max(ans,l[i][j]+r[i][j]+d[i][j]+u[i][j]-3);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 70016
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = 0
j = 0
f = []
while (j < len(a)):
    f.append(a[j])
    j += 1

while (i < n):
    if (a[i]-b[i] < 0):
        b[i] -= a[i]
        a[i] = 0
        if (a[i+1] < b[i]):
            a[i+1] = 0
        else:
            a[i+1] -= b[i]
    else:
        a[i] -= b[i]
    i += 1
print (sum(f) - sum(a))

Measured memory_bytes: 18752
#include <iostream>
#include <cmath>
#include <valarray>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {
	ll n, k;
	cin >> n >> k;
	ll ans = 0;
	while (n / k != 0) {
		n /= k;
		++ans;
	}
	cout << ans+1 << endl;
}

Measured memory_bytes: 256
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()


def dfs(v):
    visit[v] = True
    for v2 in range(n):
        if not g[v][v2]:
            continue
        if visit[v2]:
            continue
        dfs(v2)



n, m = na()
g = [[False] * n for i in range(n)]
li = []
for i in range(m):
    a, b = na()
    a -= 1
    b -= 1
    g[a][b] = g[b][a] = True
    li.append((a, b))

visit = [False] * n

ans = 0

for i in range(m):
    a, b = li[i]
    g[a][b] = g[b][a] = False
    for j in range(n):
        visit[j] = False
    dfs(0)
    flag = False
    for j in range(n):
        if not visit[j]:
            flag = True
    if flag:
        ans += 1
    g[a][b] = g[b][a] = True

print(ans)

Measured memory_bytes: 3572
//Name: Square Searching
//Level: 2
//Category: 累積和,連続区間
//Note:

/*
 * あるマスについて，そのマスを含めてそれより上にいくつ白マスが連続しているかを記憶しておく．
 * すると，大きさ s の正方形ができるためには，1行の中で s 以上の値が s 個以上連続していればよいことが分かる．
 *
 * これはスタックを使い，ある高さの区間がいくつ連続しているかを高さの昇順で管理すると求められる．
 * 1行を左から右になめながら値をpushしていくが，このとき
 * ・スタックトップより大きい値であればそのままpushする．
 * ・スタックトップより小さい値 s' であれば，このマスを含んで s' より大きい正方形は作れないため，スタックトップを s' に揃えてしまう．
 *   つまり， s' より小さい値が出てくるまでスタックを巻き戻しながらその個数を数え，最後に s' を同数追加すればよい．
 *   以前にpushした値が正方形を構成できるかどうかは，巻き戻しの途中で個数と値を比べることで判定できる．
 * 
 * また， s' を同数追加するという処理は (値, 長さ) のペアを管理するようにすると効率的に処理できる．
 * この処理をした上でのオーダーは，各マスを1回ずつなめる操作でO(N^2)，スタック操作は高々2N回しかpushされず，したがってpopも2N回であるからO(N)．
 * よって全体のオーダーは O(N^2)．
 */
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

int acc[1024][1001];

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

    while(true) {
        int N;
        cin >> N;
        if(!N) break;
        for(int i = 0; i < N; ++i) {
            acc[0][i] = 0;
        }
        for(int i = 0; i < N; ++i) {
            string line;
            cin >> line;
            for(int c = 0; c < N; ++c) {
                if(i > 0) acc[i][c] = acc[i-1][c];
                if(line[c] == '*') acc[i][c] = 0;
                else acc[i][c]++;
            }
        }
        int ans = 0;
        for(int r = 0; r < N; ++r) {
            // 番兵
            acc[r][N] = 0;
            // スタックの中身は常に昇順になっている．
            stack<pair<int,int> > stk;
            for(int c = 0; c <= N; ++c) {
                int len = 0;
                const int cur = acc[r][c];
                while(!stk.empty() && stk.top().first >= cur) {
                    len += stk.top().second;
                    if(len >= stk.top().first) {
                        ans = max(ans, stk.top().first);
                    }
                    stk.pop();
                }
                ++len;
                if(len >= cur) {
                    ans = max(ans, cur);
                }
                stk.push(make_pair(cur, len));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 5124
#include<stdio.h>
#include<iostream>

using namespace std;

int main()
{
  int N,K;
  int i;
  int result = 1;

  cin >> N;
  cin >> K;

  for(i=0;i<N;i++)
  {
    if(result < K){ result = result*2;}
    else {result = result + K;}
  }

  cout << result << endl;

}



Measured memory_bytes: 256
s = str(input())
strFindA = ''
strFindZ = ''

for i in range(len(s)):
  if s[i] == "A":
    strFindA = s[i:]
    break

for i in reversed(range(len(strFindA))):
  if strFindA[i] == "Z":
    strFindZ = strFindA[:i+1]
    break

print(len(strFindZ))

Measured memory_bytes: 9308
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define fin(ar,k,n) for(int i=k;i<n;i++) cin>>ar[i]
#define fout(ar,k,n) for(int i=k;i<n;i++) cout<<ar[i]<<' '
#define all(z) z.begin(),z.end()
#define mcc ((int)1e9+7)
#define mcf 998244353
#define mi map<int,int>
#define mem(a,n) memset(a,n,sizeof(a))
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> fst;

const int N=1e5+4;
ll dp[N],n,w,sum=0;
pii ar[N];
ll minl(ll a,ll b) {return (a<b)? a:b;}


void solve()
{
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		int u,v;
		cin>>u>>v;
		ar[i]=mp(u,v);
		sum+=v;
	}
	mem(dp,0x3f);
	dp[0]=0;
	for (int i=1;i<=n;i++)
	{
		for(int j=sum-ar[i].second;j>=0;j--)
		{
			dp[j+ar[i].second]=minl(dp[j]+ar[i].first,dp[j+ar[i].second]);
		}
	}
	for(int i=sum;i>=0;i--)
	{
		if (dp[i]<=w) 
		{
			cout<<i<<endl;
			break;
		} 
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 1024
class Dice
	attr_reader :pips

  def initialize(ary)
    @pips = ary
  end

  def _rot(ary, r)
		vals = ary.rotate(r).map{ |i| @pips[i-1] }
		ary.zip(vals).each{ |i, v| @pips[i-1] = v }
  end

	def rotate(ch)
    case ch
    when 'N'
      _rot([1, 2, 6, 5], +1)
    when 'S'
      _rot([1, 2, 6, 5], -1)
    when 'E'
      _rot([1, 4, 6, 3], +1)
    when 'W'
      _rot([1, 4, 6, 3], -1)
    when 'Z'
      _rot([2, 3, 5, 4], +1)
    end
	end

	def equal(dice_2)
		4.times do
      4.times do
				rotate('Z')
				return true if @pips == dice_2.pips
			end
      rotate('N')
    end
    rotate('E')
    4.times do
			rotate('Z')
			return true if @pips == dice_2.pips
		end
    rotate('W')
    rotate('W')
    4.times do
			rotate('Z')
			return true if @pips == dice_2.pips
		end
    return false
	end
end

dice_1 = Dice.new(gets.chomp.split(/\s/).map(&:to_i))
dice_2 = Dice.new(gets.chomp.split(/\s/).map(&:to_i))

puts dice_1.equal(dice_2) ? :Yes : :No

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

#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define ROF(i, a, b) for (int i = a; i >= (b); i--)

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<ll>; using vvll = vector<vll>;

int n, f[500005];

void add(int p, int val) {
    while (p <= n)
        f[p] += val, p += (p & -p);
    return;
}

int qry(int p) {
    int rt = 0;
    while (p)
        rt += f[p], p -= p & -p;
    return rt;
}

int main() {
    int q; cin >> n >> q;
    vi c(n + 1), lst(n + 1);
    FOR(i, 1, n) cin >> c[i];
    vector <vpii> cnt(n + 1);
    vi ans(q + 1);
    FOR(i, 1, q) {
        int l, r; cin >> l >> r;
        cnt[r].pb({l, i});
    }
    FOR(i, 1, n) {
        add(i, 1);
        if (lst[c[i]]) add(lst[c[i]], -1);
        lst[c[i]] = i;
        for (pii p : cnt[i])
            ans[p.se] = qry(i) - qry(p.fi - 1);
    }
    FOR(i, 1, q)
        cout << ans[i] << endl;
}

Measured memory_bytes: 33176
#include<bits/stdc++.h>
#define tmp(x) std::cout<<"& "<<(x)<<" &\n"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

using namespace std;
const int maxn=2e5+100;
int n,t;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int l=s.size(),ans=0;
    rep(i,0,l-1){
        int now=i;
        while(s[now]=='R')++now;
        if(now!=i){
        	--now;
        	ans=max(ans,now-i+1);
		}
//        tmp(now-i+1);
        i=now;
    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 3608
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var abcd = ReadLongs();
            var a = abcd[0];
            var b = abcd[1];
            var c = abcd[2];
            var d = abcd[3];
            var lcm = Lcm(c, d);

            //1-200
            var sbaia = b / c;
            var sbaib = b / d;
            var kbaia = (a-1) / c;
            var kbaib = (a-1) / d;

            //一番
            var q = sbaia - kbaia;
            //WriteLine(q);

            //二番
            var w = sbaib - kbaib;
            //WriteLine(w);

            //三番
            var e = b / lcm - (a-1) / lcm;
            //WriteLine(e);

            //四番
            var r = q + w - e;
            //WriteLine(r);

            //碁盤
            var tmp = b - (a - 1);
            WriteLine(tmp - r);

        }


        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        //最大公約数

        public static long Gcd(long a, long b)
        {
            if (a < b)
            {
                return Gcd(b, a);
            }
            while (b != 0)
            {
                var reminder = a % b;
                a = b;
                b = reminder;
            }
            return a;
        }

        //最小公倍数
        public static long Lcm(long a, long b)
        {
            return a * b / Gcd(a, b);
        }

        //文字数を数える
        public static int CountChar(string s, char c)
        {
            return s.Length - s.Replace(c.ToString(), "").Length;
        }
        static long fibonacci(int n)
        {
            switch (n)
            {
                case 0:
                case 1:
                    return n;
                default:
                    return fibonacci(n - 2) + fibonacci(n - 1);
            }
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n';

int main(){
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int n; cin>>n;
    int k, r=0;
    for(int i=1; i<=n; i++){
    	cin>>k;
    	if(i&1 && k&1) r++;
    }
    cout<<r<<endl;
    return 0;
}

Measured memory_bytes: 3644
from itertools import accumulate
n, k = map(int, input().split())
s = [i for i in input()]
zero_one = [0]
if s[0] == "0":
    zero_one.append(0)
s_ = s[0]
cnt = 0
for i in range(n):
    if s_ == s[i]:
        cnt += 1
    else:
        zero_one.append(cnt)
        cnt = 1
        s_ = s[i]
zero_one.append(cnt)
if s[-1] == "0":
    zero_one.append(0)
ans = 0
l = len(zero_one)
zero_one = list(accumulate(zero_one))
for i in range(0, l, 2):
    ans = max(ans, zero_one[min(l-1, i+2*k+1)] - zero_one[i])
print(ans)

Measured memory_bytes: 8604
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll INF = -4e18;
ll n, m;
ll u[2005], v[2005], w[2005];
ll a[1005];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%lld%lld", &n, &m);
    for(ll i = 1; i <= n; i++) a[i] = INF;
    a[1] = 0;
    for(ll i = 0; i < m; i++)
    {
        scanf("%lld%lld%lld", &u[i], &v[i], &w[i]);
    }
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < m; j++)
        {
            if(a[u[j]] != INF) if(a[v[j]] < a[u[j]] + w[j]) a[v[j]] = a[u[j]] + w[j];
        }
    }
    ll t = a[n];
    for(ll j = 0; j < m; j++)
    {
        if(a[u[j]] != INF) if(a[v[j]] < a[u[j]] + w[j]) a[v[j]] = a[u[j]] + w[j];
    }
    if(t < a[n])
    {
        printf("inf");
    }
    else
    {
        printf("%lld", a[n]);
    }
    return 0;
}



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

int main() {
    int N, K;  cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    long long ans = 1LL << 60;
    for (int i = 0; i < (1 << N); ++i) {
        bitset<15> bset(i);
        int color = 0;
        for (int j = 0; j < N; ++j) if (bset[j]) ++color;
        if (color >= K) {
            long long cost = 0;
            int highest = 0;
            for (int j = 0; j < N; ++j) {
                if (bset[j] && a[j] <= highest) {
                    cost += highest - a[j] + 1;
                    ++highest;
                }
                else {
                    highest = max(highest, a[j]);
                }
            }
            ans = min(ans, cost);
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<numeric>
#include<stack>
#include<map>
#include<queue>
#include<unordered_map>
#include<cmath>
#include<utility>

using ULL = unsigned long long;
using LL = long long;
using String = std::string;
using Ints = std::vector<int>;
using Doubles = std::vector<double>;
using Bools = std::vector<bool>;
using Strings = std::vector<std::string>;
using ULLs = std::vector<ULL>;
using LLs = std::vector<LL>;

// pythonのdictionary相当
template <typename T1, typename T2>
using Dict = std::unordered_map<T1,T2>;



int main(void) {
    int N;
    String s;
    int cnt=0;
    int res=0;
    std::cin >> N >> s;

    for(auto c:s){
        if(c=='R') cnt++;
    }
    for(int i=0;i<cnt;i++){
        if(s[i]!='R') res++;
    }
    std::cout << res << std::endl;

    return 0;
}

Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
#define pb push_back
#define eb emplace_back
const  int MAX=1000000;

int main()
{
   ll t;

   t=1;

   while(t--)
   {
       string str;

       cin>>str;

       ll i=0;
       if(str[i]>='A' && str[i]<='Z')cout<<"A"<<endl;
       else cout<<"a"<<endl;


   }

    }











Measured memory_bytes: 3604
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9; 
const int N = 6e5+5;                                         
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
ll ans, sum;
	
int main () {
	SpeedForce;
	ll n, x, m;
	cin >> n >> x >> m;
	x %= m;
	int len = 0;
	vector < int > u(m, -1);
	vector < ll > f(m);
	while(len < n && u[x] == -1) {
		u[x] = len;
		if(len) f[len] = f[len-1];
		f[len] += x;
		ans += x;
		x = x*(ll)x%m;
		++len;
	} 
	n -= len;
	ll sum = f[len-1];
	if(u[x]) sum -= f[u[x]-1];
	
	len -= u[x];
	
	ans += (n/len) * (ll)sum;
	n %= len;
	
	while(n > 0) {
		ans += x;
		x = x*(ll)x%m;
		--n;
	} 
	cout << ans << '\n';
	
	return Accepted;
}

// B...a


Measured memory_bytes: 4544
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  int N;
  cin >> N;
  vector<P> sorted;
  rep(i, N) {
    ll p;
    cin >> p;
    sorted.emplace_back(p, i); // first is value, second is index
  }
  sort(all(sorted));
  reverse(all(sorted));

  set<ll> st; // Contains the indices of larger values in each step.
  st.insert(-2); st.insert(-1); // left guard
  st.insert(N); st.insert(N+1); // right guard

  ll ans = 0;
  for (auto e : sorted) {  // Check value and index order by decreasing.
    ll v = e.first;
    ll i = e.second;

    auto it = st.upper_bound(i);
    --it; --it;
    ll l2 = *(it++);
    ll l1 = *(it++);
    ll r1 = *(it++);
    ll r2 = *it;

    if (r1 < N) { // r1 must be in [0, N-1]
      ans += v * (i - l1) * (r2 - r1);
    }
    if (l1 >= 0) { // l1 must be in [0, N-1]
      ans += v * (l1 - l2) * (r1 - i);
    }
    st.insert(i);
  }

  cout << ans << endl;
}


Measured memory_bytes: 7024
n = input()
a = list(map(int, input().split()))
colored = [0,0,0,0,0,0,0,0]
god = 0
for i in a:
  if i >= 3200:
    god += 1
  else:
    colored[i // 400] += 1
color = 8 - colored.count(0)
if color == 0:
  print(1,god)
else:
  print(color, color+god)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,a,b,p=0,i;
    double f,d;
    cin>>n>>d;
    for(i=0;i<n;i++)
    {
        cin>>a>>b;

             f=sqrt(a*a+b*b);
            if(d>=f){
                    p++;
            }

    }



    cout<<p;
}


Measured memory_bytes: 3744
def counting_sort(A, k):
    B = [0]*len(A)
    C = [0]*(k+1)
    for j in range(0, len(A)):
        C[A[j]] += 1
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for j in range(len(A)-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    print(*B)

k = int(input())
A = list(map(int, input().split()))
counting_sort(A, max(A)+1)



Measured memory_bytes: 224600
#![allow(unused_imports, unused_macros, dead_code)]
use std::f64::*;
use std::cmp::*;
use std::collections::*;

macro_rules! dump{
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

const INF: i64 = 0x3f3f3f3f3f3f3f3f;
const MOD: i64 = 1000000007;
const NOTHING: usize = std::usize::MAX;
const DX: [usize; 4] = [1, 0, std::usize::MAX, 0];
const DY: [usize; 4] = [0, 1, 0, std::usize::MAX];

fn main() {
    let (h, w): (usize, usize) = readln();
    let mut d: Vec<Vec<i64>> = Vec::with_capacity(10);
    let mut a: Vec<Vec<isize>> = Vec::with_capacity(h);
    for _ in 0..10 {
        let x: Vec<i64> = readln();
        d.push(x);
    }

    for _ in 0..h {
        let x: Vec<isize> = readln();
        a.push(x);
    }

    for k in 0..10 {
        for i in 0..10 {
            for j in 0..10 {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    let mut res = 0;
    for i in 0..h {
        for j in 0..w {
            if a[i][j] >= 0 {
                res += d[a[i][j] as usize][1];
            }
        }
    }
    println!("{}", res);
}

trait Read {
    fn read(s: &str) -> Self;
}

fn readln<T: Read>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

macro_rules! read_impl{
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl Read for String {
    fn read(s: &str) -> Self {
        s.to_string()
    }
}

impl Read for Vec<char> {
    fn read(s: &str) -> Self {
        s.chars().collect()
    }
}

impl<T: Read> Read for Vec<T> {
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

impl<A: Read, B: Read, C: Read, D: Read> Read for (A, B, C, D) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]), D::read(tokens[3]))
    }
}


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

int main() {
    int N, P; cin >> N >> P;
    string s; cin >> s;

    if(P==2 || P==5){
        ll ans = 0;
        for (int i = 0; i < N; i++)
        {
            if(((int)s[N-i-1] - '0') % P == 0) ans += N - i;
        }
        cout << ans << endl; 
        return 0;
    }

    map<ll, ll> m;
    m[0]++;
    ll tenfactor = 1;
    ll a = 0;
    for (int i = 0; i < N; i++)
    {
        a = (a + tenfactor * (int) (s[N-1-i]-'0')) % P;
        m[a]++;
        tenfactor = tenfactor * 10 % P;
    }
    
    ll ans = 0;
    for (auto iter = m.begin(); iter != m.end(); ++iter)
    {
        ans += iter->second * (iter->second-1) / 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1028
n, w = map(int, input().split())
wd = {}
minw, v = map(int, input().split())
wd[minw] = [v]
wd[minw+1] = []
wd[minw+2] = []
wd[minw+3] = []
for _  in range(n-1):
  _w, v = map(int, input().split())
  wd[_w].append(v)

for k, v in wd.items():
  wd[k] = list(sorted(v))[::-1]

maxw = 0
for i in range(w // minw + 1):
  for j in range((w - minw * i) // (minw + 1) + 1):
    for k in range((w - minw * i - (minw + 1) * j) // (minw + 2) + 1):
      l = (w - minw * i - (minw + 1) * j - (minw + 2) * k) // (minw + 3)
      tmp = sum(wd[minw][:i]) + sum(wd[minw+1][:j]) + sum(wd[minw+2][:k]) + sum(wd[minw+3][:l])
      if tmp > maxw:
        maxw = tmp
print(maxw)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    if(i<(n+2)/2) cout<<0;
    else cout<<m;
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3116
n = int(input())
a = map(int, input().split())
l = list(a)
nl = [0]*n

for i in range(n-1):
    if l[i] > l[i+1]:
        nl[i+1] += l[i] - l[i+1]
        l[i+1] = l[i]
    else:
        nl[i+1] += 0
print(sum(nl))


Measured memory_bytes: 32144
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ll       long long
#define DS       pair<ll, ll>
#define READ(f)  freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

const int N = 55;
const int MOD = 1e9 + 7;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

string s;

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin >> s;
    int n = s.size();
    int x = (n - 1) / 2;
    string tmp = s;
    reverse(tmp.begin(), tmp.end());
    if (tmp != s) {
        puts("No");
        return 0;
    }
    tmp = "";
    for (int i = 0; i < x; i++) {
        tmp += s[i];
    }
    string fmp = tmp;
    reverse(fmp.begin(), fmp.end());
    if (fmp != tmp) {
        puts("No");
        return 0;
    }
//    cout << tmp << endl;
    x = (n + 3) / 2;
    tmp = "";
    for (int j = x - 1; j < n; j++) {
        tmp += s[j];
    }
    fmp = tmp;
//    cout << tmp << endl;
    reverse(fmp.begin(), fmp.end());
    puts(fmp != tmp ? "No" : "Yes");
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int const M=2e5+10,inf=1e9+10,mod=1e9+7;
int a[M];
main()
{
	for(int i=1;i<=3;i++)cin>>a[i];
	sort(a+1,a+4);
	bool flag=0;
	if(a[3]%2!=a[2]%2 || a[3]%2!=a[1]%2)
	{
		for(int i=1;i<=3;i++)
		{
			for(int j=i+1;j<=3;j++)
			{
				if(a[i]%2==a[j]%2)
				{
					a[i]++,a[j]++,flag=1;
					break;
				}
			}
			if(flag)break;
		}
	}
	sort(a+1,a+4);
	cout<<(a[3]-a[1]+a[3]-a[2])/2+flag;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    ll H,W;
    cin >> H >> W;
    bool m[H][W];
    ll tmpm[H][W];
    for(int yi = 0; yi < H; yi++){
        string s;
        cin >> s;
        for(int xi = 0; xi < W; xi++){
            m[yi][xi] = (s[xi] == '.');
            tmpm[yi][xi] = -1;
        }
    }
    queue<pair<ll,ll>> q = queue<pair<ll,ll>>();
    ll M = 0;
    for(int Ys = 0; Ys < H; Ys++){
        for(int Xs = 0; Xs < W; Xs++){
            if(!m[Ys][Xs]){
                continue;
            }
            q.push(make_pair(Ys,Xs));
            tmpm[Ys][Xs] = 0;
            while(!q.empty()){
                auto p = q.front(); q.pop();
                int Y = p.first;
                int X = p.second;
                if(Y !=0 && tmpm[Y - 1][X] == -1 && m[Y - 1][X]){
                    tmpm[Y - 1][X] = tmpm[Y][X] + 1;
                    q.push(make_pair(Y - 1,X));
                }
                if(Y != H-1 && tmpm[Y + 1][X] == -1 && m[Y + 1][X]){
                    tmpm[Y + 1][X] = tmpm[Y][X] + 1;
                    q.push(make_pair(Y + 1,X));
                }
                if(X != 0 && tmpm[Y][X - 1] == -1 && m[Y][X - 1]){
                    tmpm[Y][X - 1] = tmpm[Y][X] + 1;
                    q.push(make_pair(Y,X - 1));
                }
                if(X != W-1 && tmpm[Y][X + 1] == -1 && m[Y][X + 1]){
                    tmpm[Y][X + 1] = tmpm[Y][X] + 1;
                    q.push(make_pair(Y,X + 1));
                }
            }
            for(int yi = 0; yi < H; yi++){
                for(int xi = 0; xi < W; xi++){
                    M = max(M,tmpm[yi][xi]);
                    tmpm[yi][xi] = -1;
                }
            }
        }
    }
    cout << M;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		int ans = 0;
		int a = 0;
		for(int i = 0; i < s.length(); ++i) {
			if(i % 2 == 0) {
				if('0' != s.charAt(i))++a;
			}
			else {
				if('1' != s.charAt(i))++a;
			}
		}
		ans = a;
		a = 0;
		for(int i = 0; i < s.length(); ++i) {
			if(i % 2 == 0) {
				if('1' != s.charAt(i))++a;
			}
			else {
				if('0' != s.charAt(i))++a;
			}
			
		}
		ans = Math.min(ans,  a);
		System.out.println(ans);
	}

}


Measured memory_bytes: 25512
n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
    print(0)
elif abs(n-m)==1:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    for i in range(1,m+1):
        ans=(ans*i)%mod
    print(ans)
else:
    ans=2
    for i in range(1,n+1):
        ans=(ans*i)%mod
    for i in range(1,m+1):
        ans=(ans*i)%mod
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, k; cin >> n >> k;
    vector<vector<int> > tmp(n);
    rep(i, n) {
        int t0, d0;
        cin >> t0 >> d0;
        t0--;
        tmp[t0].push_back(d0);
    }

    rep(i, n) sort(all(tmp[i]), greater<int>()); //各ネタごとに美味しさ降順でソート

    vector<int> y1, y0;
    rep(i, n) {
        if (sz(tmp[i]) == 0) continue;
        y1.push_back(tmp[i][0]); //各寿司の一番美味しいやつの味を格納
        for (int j=1; j<sz(tmp[i]); j++) {
            y0.push_back(tmp[i][j]); //一番美味しいやつ以外の味を格納
        }
    }
    sort(all(y1), greater<int>());
    sort(all(y0), greater<int>());
    //以降、各寿司を食う場合は一番美味しいやつを食えばよく
    //その一番美味しいやつを何個食うかで調べていけば良い
    ll ans = 0;
    for (int i=1; i<=min(sz(y1), k); i++) {
        ll tmp = (ll)i*i; //何種類の寿司を食うか
        rep(j, i) tmp += y1[j];
        int m = k-i; //あと何個一番美味しい寿司以外食うか
        if (sz(y0) < m) continue;
        rep(j, m) {
            tmp += y0[j];
        }
        chmax(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 8312
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 100005; 
const lo mod = 1000000007; 

lo n,m,b,a[li],k,flag,cev,r,l,PS[li+10];
string s;
vector<lo> v;

int main(void){
	scanf("%lld %lld",&n,&m);
	for(lo i=1;i<=m;i++){
		scanf("%lld %lld",&l,&r);
		PS[l]++;
		PS[r+1]--;
	}
	for(int i=1;i<=n;i++){
		PS[i]=PS[i-1]+PS[i];
		if(PS[i]==m) cev++;
	}
	printf("%lld\n",cev);
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<map>
using namespace std;
using ll = long long;

int main(){
    int n;
    cin>>n;
    map<int,int> m;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        m[a[i]]++;
    }
    int k=m.size();
    bool ans=false;
    if(m[0]==n){
        ans=true;
    }else if(n%3==0&&m[0]==n/3&&k==2){
        ans=true;
    }else if(n%3==0&&k==3){
        ll s=0;
        bool flag=true;
        for(auto p : m){
            if(p.second&&p.second!=n/3) flag=false;
            s^=p.first;
        }
        if(flag&&s==0) ans=true;
    }
    if(ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

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

  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    if (A.at(i) == 0) {
      cout << 0 << endl;
      return 0;
    }
  }

  long long ans = 1;
  for (int i = 0; i < N; i++) {
    if (A.at(i) > 1000000000000000000 / ans) {
      cout << -1 << endl;
      return 0;
    } else {
      ans *= A.at(i);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3968
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod

#define N 100010
ll h,w,k;
string s[810];
ll d[810][810];
int main(){
    cin>>h>>w>>k;
    queue<pair<ll,pair<ll,ll> > >Q;
    for(int i=0;i<h;i++){
	cin>>s[i];
	for(int j=0;j<w;j++){
	    if(s[i][j]=='S'){
		Q.push(make_pair(0LL,make_pair(i,j)));
	    }
	    d[i][j]=1e17;
	}
    }
    while(!Q.empty()){
	ll cost=Q.front().first;
	ll x=Q.front().second.first;
	ll y=Q.front().second.second;
	Q.pop();
	if(d[x][y]<=cost)continue;
	d[x][y]=cost;
	ll dx[]={0,1,0,-1},dy[]={1,0,-1,0};
	for(int r=0;r<4;r++){
	    ll xx=x+dx[r],yy=y+dy[r];
	    if(0<=xx&&xx<h&&0<=yy&&yy<w&&s[xx][yy]=='.'){
		Q.push(make_pair(cost+1,make_pair(xx,yy)));
	    }
	}
    }
    ll ans=1e17;
    for(ll i=0;i<h;i++){
	for(ll j=0;j<w;j++){
	    if(d[i][j]<=k){
		ll dist=1e17;
		chmin(dist,i);
		chmin(dist,j);
		chmin(dist,h-1-i);
		chmin(dist,w-1-j);
		chmin(ans,(dist+k-1)/k);
	    }
	}
    }
    cout<<ans+1<<endl;
}




Measured memory_bytes: 6272
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    string S;
    cin >> S;
    int K;
    cin >> K;
    int N = S.size();
    set<string> strs;
    for(int i = 0; i < N; i++) {
        string s = "";
        for(int j = i; j < N; j++) {
            s += S[j];
            strs.insert(s);
            if(s.size() == 5)
                break;
        }
    }
    auto it = strs.begin();
    rep(i, K - 1) it++;
    cout << *it << endl;
    return 0;
}

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

typedef std::pair<int, int> ipair;
#define pb push_back
#define ff first
#define ss second
#define fr(i, j, k) for (int i = j; i < k; i++)
#define rf(i, j, k) for (int i = j; i >= k;i--)
#define int long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define mp make_pair

const int mod = 1000000007;
const ld pi = acos(-1);
const int maxn = 2001;

template<class T> ostream& operator <<(ostream &out,vector<T> &A){for(auto x:A) out<<x<<" ";return out;}
template <class T1,class T2>T1 powr(T1 a,T2 b){T1 res = 1;fr(i,1,b+1)res = res*a;return res;}
#define IOS  std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int32_t main(){
  int n;  cin>>n;
  vector<int>A(n);  fr(i,0,n) cin>>A[i];
  sort(all(A));
  double ans = A[0];
  fr(i,1,n)
    ans = (ans+(double)A[i])/2;
  cout<<ans<<endl;
}


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

int main() {
  int H, W, A, B;
  cin >> H >> W >> A >> B;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (j < A && i < B) cout << 1;
      else if (j >= A && i < B) cout << 0;
      else if (j < A && i >= B) cout << 0;
      else cout << 1;
    }
    cout << endl;
  }
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100001;
const int inf = 1<<24;

int dp[MAXN];

int solve(int N) {
  if(dp[N] != -1) return dp[N];
  dp[N] = inf;
  dp[N] = min(dp[N],solve(N-1)+1);
  for(int k = 6;k <= N;k*=6) {
    dp[N] = min(dp[N],solve(N-k)+1);
  }
  for(int k = 9;k <= N;k*=9) {
    dp[N] = min(dp[N],solve(N-k)+1);
  }
  return dp[N];
}

int main() {
  int N;
  cin >> N;
  memset(dp,-1,sizeof dp);
  dp[0] = 0;
  dp[1] = 1;
  cout << solve(N) << endl;
  return 0;
}


Measured memory_bytes: 3712
#include<stdio.h>
int main(void){
  int n, i, ans=0, x=0;
  scanf("%d", &n);
  int a[n];
  for(i=0;i<n;i++){
    scanf("%d", &a[i]);
  }
for(;;){
  for(i=0;i<n;i++){
    if(a[i]%2==1){
      printf("%d\n", ans);
      return 0;
    }
  }
  ans++;
  for(i=0;i<n;i++){
    a[i]/=2;
  }
}
}


Measured memory_bytes: 128
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		std::vector<int> num;
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (; x; x /= 10) {
			num.push_back(x % 10);
		}
		while (!num.empty()) {
			putchar(num.back() ^ '0');
			num.pop_back();
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int N = 100005, P = 998244353;

int n, m, d[N], c[N];

int main() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(d[i]);
		m = std::max(m, d[i]);
		++c[d[i]];
	}
	int ans = d[1] == 0 && c[0] == 1;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= c[i]; ++j) {
			ans = 1ll * ans * c[i - 1] % P;
		}
	}
	print(ans);
}


Measured memory_bytes: 4308