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

template <uint32_t Modulus>
struct modular {
  static_assert(int(Modulus) > 0, "Modulus must be in the range [1, 2^31)");
  static constexpr int modulus() { return Modulus; }

  modular() : v(0) {}
  modular(int64_t x) : v(x % Modulus) {
    if (int(v) < 0) v += Modulus;
  }

  explicit operator int() const { return v; }
  modular& operator++() { return ++v == Modulus ? v = 0 : 0, *this; }
  modular& operator--() { return --(v ? v : v = Modulus), *this; }
  modular operator+() const { return *this; }
  modular operator-() const {
    modular res;
    res.v = v ? Modulus - v : 0;
    return res;
  }
  modular& operator*=(modular b) {
    v = uint64_t(v) * b.v % Modulus;
    return *this;
  }
  modular& operator/=(modular b) {
    auto [x, gcd] = extgcd(b.v, Modulus);
    assert(gcd == 1);
    return *this *= x;
  }
  modular& operator+=(modular b) {
    v += b.v - Modulus;
    if (int(v) < 0) v += Modulus;
    return *this;
  }
  modular& operator-=(modular b) {
    v -= b.v;
    if (int(v) < 0) v += Modulus;
    return *this;
  }

  friend modular operator++(modular& a, int) {
    return std::exchange(a, ++modular(a));
  }
  friend modular operator--(modular& a, int) {
    return std::exchange(a, --modular(a));
  }
  friend modular operator*(modular a, modular b) { return a *= b; }
  friend modular operator/(modular a, modular b) { return a /= b; }
  friend modular operator+(modular a, modular b) { return a += b; }
  friend modular operator-(modular a, modular b) { return a -= b; }
  friend std::istream& operator>>(std::istream& is, modular& b) {
    int64_t x;
    return is >> x, b = x, is;
  }
  friend std::ostream& operator<<(std::ostream& os, modular b) {
    return os << b.v;
  }
  friend bool operator==(modular a, modular b) { return a.v == b.v; }
  friend bool operator!=(modular a, modular b) { return a.v != b.v; }

 private:
  static std::pair<int, int> extgcd(int a, int b) {
    std::array x{1, 0};
    while (b) {
      int q = a / b;
      std::swap(x[0] -= q * x[1], x[1]);
      std::swap(a -= q * b, b);
    }
    return {x[0], a};
  }

  uint32_t v;
};

template <class T, class U, class BinaryOperation = std::multiplies<>>
constexpr T power(T a, U n, T init = 1,
                  BinaryOperation binary_op = BinaryOperation{}) {
  static_assert(std::is_integral_v<U> and not std::is_same_v<U, bool>);
  assert(n >= 0);
  while (n) {
    if (n & 1) init = binary_op(init, a);
    if (n >>= 1) a = binary_op(a, a);
  }
  return init;
}

int main() {
  using namespace std;
  cin.tie(nullptr)->sync_with_stdio(false);
  using mint = modular<int(1e9) + 7>;
  int n;
  cin >> n;
  mint ans = power<mint>(9, n) * 2 - power<mint>(8, n);
  ans = power<mint>(10, n) - ans;
  cout << ans << '\n';
}


Measured memory_bytes: 3644
#include <stdio.h>
int main(void){
	int s;
	while(1){
		int num=0,sign=0,p=0,q[100]={0},o=1;
	while((s=fgetc(stdin)) != '\n'){
		if(num==0 && s=='.'){
			p=1;break;
		}
	       	num=1;
		if(o==0)
			sign=1;
		if(s=='('){
			q[o]=1;o++;
		}
		if(s=='['){
			q[o]=2;o++;
		}
		if(s==')'){
			if(q[o-1]==1)
				o--;
			else
				sign=1;
		}
		if(s==']'){
			if(q[o-1]==2)
				o--;
			else
				sign=1;
		}
	}
	if(p==1)
		break;
	else if(sign==1 || o!=1)
			printf("no\n");
	else if(o==1)
			printf("yes\n");
	}
	return 0;
}

Measured memory_bytes: 524
def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    
    dp = [0] * n
    dp[0] = 0
    
    for i in range(1, n):
        dp[i] = min([dp[j] + abs(h[j] - h[i]) for j in range(max(0, i - k), i)])
                
    print(dp[-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 13980
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a = sorted(a)[::-1]
ans = sum(a[:(n+1)//2])*2-a[0]
ans = ans if n%2==0 else ans-a[(n+1)//2-1]

print(ans)

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

int main(){
    ll n, t;
    vector<ll> v;
    cin >> n;
    for (auto i = 0; i< n; i++){
        cin >> t;
        v.push_back(t);
    }
    auto pv = v;
    if(prev_permutation(pv.begin(), pv.end())){
        for (auto i = pv.begin(); i != pv.end(); i++){
            cout << (i == pv.begin() ? "" : " ") << *i;
        }
        cout << endl;
    }
    for (auto i = v.begin(); i != v.end(); i++){
        cout << (i == v.begin() ? "" : " ") << *i;
    }
    cout << endl;
    auto nv = v;
    if(next_permutation(nv.begin(), nv.end())){
        for (auto i = nv.begin(); i != nv.end(); i++){
            cout << (i == nv.begin() ? "" : " ") << *i;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.*;
public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		int q = in.nextInt();
		for(int i=0;i<q;i++)new CGL_2A().doIt();
	}

	class CGL_2A{
		final double EPS=1.0e-8;
		void doIt(){
			Line2D l1 = new Line2D.Double(in.nextDouble(),in.nextDouble(),in.nextDouble(),in.nextDouble());
			Line2D l2 = new Line2D.Double(in.nextDouble(),in.nextDouble(),in.nextDouble(),in.nextDouble());
			System.out.println(isParallel(l1, l2));
		}

		double cross(Point2D p1,Point2D p2){
			return p1.getX()*p2.getY()-p1.getY()*p2.getX();
		}

		Point2D diff(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()-p2.getX(),p1.getY()-p2.getY());
		}
		boolean intersectLL(Line2D l1,Line2D l2){
			return intersectLL(l1.getP1(),l1.getP2(),l2.getP1(),l2.getP2());
		}
		boolean intersectLL(Point2D a1,Point2D a2,Point2D b1,Point2D b2){
			return (Math.abs(cross(diff(a2, a1), diff(b2, b1)))>EPS)||(Math.abs(cross(diff(a2, a1), diff(a1, b1)))<EPS);
		}

		Point2D intersectionPoint(Line2D l1,Line2D l2){
			return intersectionPoint(l1.getP1(), l1.getP2(), l2.getP1(), l2.getP2()); 
		}

		Point2D intersectionPoint(Point2D a1,Point2D a2,Point2D b1,Point2D b2){
			Point2D a=diff(a2,a1),
					b=diff(b2,b1);
			return sum(a1, mul(cross(b, diff(b1,a1))/cross(b,a), a));
		}

		Point2D mul(double n,Point2D p1){
			return new Point2D.Double(p1.getX()*n,p1.getY()*n);
		}

		Point2D sum(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()+p2.getX(),p1.getY()+p2.getY());
		}

		boolean parallel(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){     
			double kata1=(y1-y2)/(x1-x2);
			double kata2=(y3-y4)/(x3-x4);
			if(kata1==kata2)return true;
			if((y1-y2==0&&y3-y4==0)||(x1-x2==0&&x3-x4==0))return true;
			return false;
		}
		boolean parallel(Line2D l1,Line2D l2){
			return parallel(l1.getP1().getX(), l1.getP1().getY(), l1.getP2().getX(),l1.getP2().getY(),
					l2.getP1().getX(),l2.getP1().getY(),l2.getP2().getX(),l2.getP2().getY());
		}
		boolean orthogonal(Line2D l1,Line2D l2){
			return orthogonal(l1.getP1().getX(), l1.getP1().getY(), l1.getP2().getX(),l1.getP2().getY(),
					l2.getP1().getX(),l2.getP1().getY(),l2.getP2().getX(),l2.getP2().getY());
		}
		boolean orthogonal(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4){
			double a=(y1-y2)/(x1-x2);
			double b=(y3-y4)/(x3-x4);
			if(Math.abs(a-(-(1/b)))<EPS||Math.abs((-(1/a)-b))<EPS)return true;
			if(Math.abs((-(1/b))-a)<EPS||Math.abs(b-(-(1/a)))<EPS)return true;
			return false;
		}
		int isParallel(Line2D l1,Line2D l2){
			if(parallel(l1, l2))return 2;
			if(orthogonal(l1, l2))return 1;
			return 0;
		}
	}

}

Measured memory_bytes: 50344
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int main(){
    long long n,i,b,mn[100010];
    pair<long long,long long> a[100010];
    long long ans[100010];
    cin >> n;
    for(i=1;i<=n;i++){
        cin >> b;
        a[i] = make_pair(b,i);
        ans[i] = 0;
    }
    a[0] = make_pair(0,0);
    sort(a,a+n+1);
    mn[n+1] = 1000010;
    for(i=n;i>=0;i--){
        mn[i] = min(a[i].second,mn[i+1]);
    }

    for(i=n;i>=1;i--){
            ans[mn[i]] += (n+1-i)*(a[i].first-a[i-1].first);
    }

    for(i=1;i<=n;i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4224
#include <iostream>
#include <vector>

int main(void){
    int n, ans=1000001;
    std::cin >> n;
    std::vector<int> x(n);
    for(int i=0; i<n; ++i) std::cin >> x.at(i);

    for(int i=1; i<101; ++i){
        int tmp = 0;
        for(int j=0; j<n; ++j){
            tmp += (x.at(j) - i) * (x.at(j) - i);
        }
        if(tmp < ans) ans = tmp;
    }

    std::cout << ans << std::endl; 

    return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] T = new int[N];
        int[] A = new int[N];

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

        System.out.println( solve(N, T, A) );
    }

    private static long solve(int N, int[] T, int[] A) {
        long t_result = T[0];
        long a_result = A[0];

        for (int i = 1; i < N; i++) {
            long t = T[i];
            long a = A[i];

            // 昔の票数以上になる比の数まで大きくする
            long td = bairitsu(t, t_result);
            long ad = bairitsu(a, a_result);
            long d = Math.max(td, ad);

            t_result = d * t;
            a_result = d * a;
        }
        return t_result + a_result;
    }

    // i を何倍したら n 以上になるか
    private static long bairitsu(long i, long n) {
        long d = n / i;
        long r = n % i;

        if( r == 0 ) {
            return d;
        } else {
            return d + 1;
        }
    }
}

Measured memory_bytes: 25476
from collections import deque
K = int(input())
d = deque(list(range(1, 10)))
for i in range(K - 1):
  a = d[0]
  b = 10 * a + a % 10
  if a % 10 != 0:
    d.append(b - 1)
  d.append(b)
  if a % 10 != 9:
    d.append(b + 1)
  d.popleft()
  
print(d[0])

Measured memory_bytes: 11992
from math import factorial
from itertools import permutations

N = int(input())
n_p = factorial(N)

p_list=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

ans = []
for p1,p2,p3 in permutations(p_list,3):
    n1 = (p1 ** 4) * (p2 ** 4) * (p3 ** 2)
    n2 = (p1 ** 14) * (p2 ** 4)
    n3 = (p1 ** 24) * (p2 ** 2)
    n4 = p1 ** 74
    
    for v in [n1,n2,n3,n4]:
        if n_p % v == 0:
            ans.append(v)
            
print(len(set(ans)))

Measured memory_bytes: 3188
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
    
    
N=int(input())
l=list(map(int,input().split()))
cnt=0
a=0
for i in range(N-1):
	if l[i]>=l[i+1]:
		cnt+=1
	else:
		if cnt>=a:
			a=cnt
			cnt=0
		else:
			cnt=0
	
if cnt>=a:
	a=cnt	
print(a)

Measured memory_bytes: 15020
#include <stdio.h>
#include <vector>
using namespace std;
int n,k;int inline gcd(int a, int b) {while (b) {int c=a%b;a=b,b=c;} return a;}
vector<vector<int> >g;
vector<int>mt;
vector<char>used;
bool try_kuhn(int v) {
	if (used[v]) return false;
	used[v]=1;
	for (int i=g[v].size()-1;i>=0;i--) {
		int to=g[v][i];
		if (mt[to]==-1 || try_kuhn(mt[to])) {
			mt[to]=v;return true;
		}
	}
	return false;
}
int A[505],B[505];
int main() {
	int i,j;
	while (scanf("%d %d",&n,&k)!=EOF && (n || k)) {
		g.clear();mt.assign(k,-1);g.resize(n+k);
		for (i=0;i<n;scanf("%d",&A[i++]));
		for (i=0;i<k;scanf("%d",&B[i++]));
		for (i=0;i<n;i++) for (j=0;j<k;j++) if (gcd(A[i],B[j])>1) g[i].push_back(j);
		for (i=0;i<n;i++) {
			used.assign(n,false);
			try_kuhn(i);
		}
		for (i=0,j=0;i<k;i++) if (mt[i]!=-1) j++;
		printf("%d\n",j);
	}
	return 0;
}

Measured memory_bytes: 1780
n, m = map(int, input().split())
ship = []
flag = False
for i in range(n):
  ship.append([])

for i in range(m):
  temp = list(map(int, input().split()))
  ship[temp[0]-1].append(temp)

for i in range(len(ship[0])):
  now = ship[0][i]
  if [now[1], n] in ship[now[1]-1]:
    flag = True
    break

if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

int main(int argc,char *argv[]){
        int H,W;
        while(1) {
                cin >> H >> W;
                if (H == 0 && W == 0) break;
                for(int i = 0; i < H; i++){
                        for (int j = 0; j < W; j++){
                                if (i == 0 || i == H - 1 || j == 0 || j == W - 1){
                                        cout << "#";
                                } else {
                                        cout << ".";
                                }
                        }
                        cout << "\n";
                }
                cout << "\n";
        }
        return 0;
}

Measured memory_bytes: 3024
// 6/18 振り返り
#include <iostream>
#include <vector>
#include <string>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

ll INF = 1e18;
ll dp[200005][4];

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int k = 1 + n % 2;  // 何個余分な×を入れられるか？偶数なら１個、奇数なら２個。
    rep(i, n+1) rep(j, k+1) dp[i][j] = -INF;
    dp[0][0] = 0;
    rep(i, n) {
        rep(j, k+1) {
            // ×を一個挿入する場合
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]);
            ll now = dp[i][j];
            if ((i+j)%2 == 0) now += a[i];
            dp[i+1][j] = max(dp[i+1][j], now);
        }
    }
    ll ans = dp[n][k];
    cout << ans << endl;
}

Measured memory_bytes: 10380
n = gets.chomp.to_i
h = gets.chomp.split.map(&:to_i)

dp = Array.new(n, Float::INFINITY)
dp[0] = 0

for i in 1..n-1
  dp[i] = [dp[i], dp[i - 1] + (h[i] - h[i - 1]).abs].min
  dp[i] = [dp[i], dp[i - 2] + (h[i] - h[i - 2]).abs].min if i > 1
end

puts dp.last


Measured memory_bytes: 11780
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

  def find(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.r[x] > self.r[y]:
      x, y = y, x
    self.n[y] += self.n[x]
    self.n[x] = y
    if self.r[x] == self.r[y]:
      self.r[y] += 1
    self.co -= 1

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def size(self, x):
    return -self.n[self.find(x)]

  def set_count(self):
    return self.co

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
print(uf.set_count()-1)


Measured memory_bytes: 11440
#include <iostream>
#include <string>
//#include <cstring>
//#include <sstream>
#include <fstream>
#include <vector>
#include <algorithm>
//#include <stack>
//#include <queue>
//#include <chrono>
//#include <numeric>
//#include <set>
//#define _USE_MATH_DEFINES
//#include <cmath>
//#include <math.h>
//#include <iomanip>
//#include <list>
//#include <limits>

using namespace std;
const int infty = static_cast <int> (pow(256, sizeof(int)) / 2 - 1);

class cDisjointSet
{
	vector<int> vp;
	vector<int> vrank;
public:
	cDisjointSet(int n);
	void makeSet(int x);
	void uunionn(int x, int y);
	int findSet(int x);
	bool isSameSet(int x, int y);
	void link(int x, int y);
};

cDisjointSet::cDisjointSet(int n)
{
	vp.resize(n);
	vrank.resize(n);
	for (int i = 0; i < n; ++i)
		makeSet(i);
}
void cDisjointSet::makeSet(int x)
{
	vp[x] = x;
	vrank[x] = 0;
}

void cDisjointSet::uunionn(int x,int y)
{
	link(findSet(x), findSet(y));
}

int cDisjointSet::findSet(int x)
{
	if(x!=vp[x])
		vp[x] = findSet(vp[x]);
	return vp[x];
}

bool cDisjointSet::isSameSet(int x, int y)
{
	return findSet(x) == findSet(y);
}

void cDisjointSet::link(int x, int y)
{
	if (vrank[x] > vrank[y])
		vp[y] = x;
	else
	{
		vp[x] = y;
		if (vrank[x] == vrank[y])
			vrank[y]++;
	}
}

int main()
{
	////ifstream fin("DPL_1_C-in40.txt");
	//ifstream fin("test.txt");
	//if (!fin.is_open())
	//{
	//	cout << "File not found." << endl;
	//	return 0;
	//}

	//fin.tie(0);
	//ios::sync_with_stdio(false);

	//int n,q;
	//fin >> n >> q;
	//fin.ignore();

	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;
	cin.ignore();

	int com, x, y;
	cDisjointSet cd(n);

	for (int i = 0; i < q; ++i)
	{
		cin >> com >> x >> y;
		//fin >> com >> x >> y;
		switch(com)
		{
		case 0:
			cd.uunionn(x, y);
			break;
		case 1:
			cout << (cd.isSameSet(x, y) ? 1 : 0) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3280
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if(a == b) System.out.println(c);
        else if(a == c) System.out.println(b);
        else if(b == c) System.out.println(a);
    }
}

Measured memory_bytes: 35808
#include <bits/stdc++.h>
using namespace std;
#define X ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


// long long p = 1e9+7;

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<ll, ll> pi;
typedef unordered_map<ll, ll> UMP;
#define FOR(i,b) for(i=0;i<b;i++)
#define pb push_back


void printa(VI &x,ll n){
    ll i;
    FOR(i, n){
        cout<<x[i]<<" ";
    }
    cout<<endl;
}


/////GLOABLS VARS

//////FUNCTIONS

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
    #endif
    ll n,i,j;
    cin>>n;
    VL arr(n);
    
    FOR(i,n){cin>>arr[i];}
    sort(arr.begin(), arr.end());
    unordered_set <ll>mp;
    // debug(arr);
    ll ans=0;
    for(i=0;i<n;i++){
        if (i<n-1){if(arr[i]==arr[i+1]){mp.insert(arr[i]);continue;}}
        bool flag = true;
        ll lim = sqrt(arr[i])+3;
        for(j=1;j<lim;j++){
            if(arr[i]%j){continue;}
            if(mp.find(j)!=mp.end() || mp.find(arr[i]/j)!=mp.end()){
                flag = false; 
                // debug(j, arr[i]);
                break;}
        }
        if(flag){ans+=1;}
        mp.insert(arr[i]);
    }
    cout<<ans;
}

Measured memory_bytes: 12892
#include <iostream>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int t, a;

    if(C % B == 0) t = C / B;
    else t = C/B + 1;

    if(A%D == 0) a = A/D;
    else a = A/D+1;

    if(t <= a) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 3636
#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, int> P;
const int MAX_NM = 100005;
P req[MAX_NM];

int main()
{
	int N,M;
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int a,b;
		cin >> a >> b;
		req[i] = P(b,a);
	}

	sort(req,req+M);

	int now = -1;
	int ans = 0;

	for (int i = 0; i < M; ++i)
	{
		if (now <= req[i].second)
		{
			ans++;
			now = req[i].first;
		}
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
// Example program
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int x=0,a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,y=0;
    cin>>a>>b>>c>>d;
    cin>>e>>f>>g>>h;
    x=a+b+c+d;
    y=e+f+g+h;
    if(x>y){
        cout<<x<<endl;
    }else{
        cout<<y<<endl;
    }
    
}

Measured memory_bytes: 1160
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<functional>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll a,b,k,cnt=0;;
    cin>>a>>b>>k;
    for(ll i=100000;i>0;i--){
        if(a%i==0&&b%i==0){
            cnt++;
            if(cnt==k){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    return 0;
}

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

struct PMA{
    PMA* next[256];
    vector<int> matched;
    PMA(){memset(next,0,sizeof(next));}
};
PMA *buildPMA(vector<string> p){
    PMA *root=new PMA,*t;
    rep(i,p.size()){
        t=root;
        rep(j,p[i].size()){
            if(t->next[(int)p[i][j]]==0) t->next[(int)p[i][j]]=new PMA;
            t=t->next[(int)p[i][j]];
        }
        t->matched.pb(i);
    }
    queue<PMA*> que;
    FOR(i,'a','z'+1){
        if(!root->next[i]) root->next[i]=root;
        else{
            root->next[i]->next[0]=root;
            que.push(root->next[i]);
        }
    }
    while(!que.empty()) {
        t=que.front();que.pop();
        FOR(i,'a','z'+1){
            if(t->next[i]){
                PMA *nx=t->next[0];
                while(!nx->next[i]) nx=nx->next[0];
                t->next[i]->next[0]=nx->next[i];
                vector<int> rv;
                set_union(t->next[i]->matched.begin(),t->next[i]->matched.end(),
                nx->next[i]->matched.begin(),nx->next[i]->matched.end(),back_inserter(rv));
                t->next[i]->matched=rv;
                que.push(t->next[i]);
            }
        }
    }
    return root;
}
void match(PMA* &pma,const string s,vector<int> &ret){
    rep(i,s.size()){
        int c=s[i];
        while(!pma->next[c]) pma=pma->next[0];
        pma=pma->next[c];
        rep(j,pma->matched.size()) ret[pma->matched[j]]=true;
        //rep(j,pma->matched.size()) ret[pma->matched[j]]++;
    }
}
vector<string> p;
vector<int> v(100001);
int main(){
    string s,pi;
    int n;
    cin>>s>>n;
    rep(i,n){
        cin>>pi;
        p.pb(pi);
    }
    PMA *r=buildPMA(p);
    PMA *cur=r;
    int ans=0;
    rep(i,s.size()){
        int c=s[i];
        while(!cur->next[c]) cur=cur->next[0];
        cur=cur->next[c];
        if(cur->matched.size()>0)++ans,cur=r;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 174140
#include <bits/stdc++.h>
using namespace std;
int a,b,c,d;

int main(){
	cin>>a>>b>>c>>d;
	if(a+b>c+d){
		cout<<"Left"<<endl;
	}else if(a+b<c+d){
		cout<<"Right"<<endl;
	}else{
		cout<<"Balanced"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int i;
	int input;
	int mozi;
	int kazu;
	while((input=getchar())!=-1) {
		if(input!='@')putchar(input);
		else {
			kazu=getchar();
			mozi=getchar();
			for(i='0';i<kazu;i++)putchar(mozi);
		}
	}
	return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
typedef ll i1;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

class UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<int> size;
    vector<vector<int>> group;
public:
    UnionFind(int n = 1) {
        par.resize(n + 1);
        rank.resize(n + 1);
        size.resize(n + 1);
        group.resize(n + 1);
        for (int i = 0; i <= n; ++i) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
            group[i].push_back(i);
        }
    }

    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            int r = find(par[x]);
            return par[x] = r;
        }
    }

    bool is_same(int x, int y) {
        return find(x) == find(y);
    }

    bool unit(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        } else {
            if (rank[x] < rank[y]) {
                swap(x, y);
            }
            if (rank[x] == rank[y]) {
                ++rank[x];
            }
            par[y] = x;
            size[x] += size[y];
            return true;
        }
    }

    int get_size(int x) {
        return size[find(x)];
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (group[x].size() > group[y].size()) {
            swap(x, y);
        }
        copy(group[y].begin(), group[y].end(), back_inserter(group[x]));
        group[y].clear();
        par[y] = x;
    }
};

void Main() {
    ll N, M, K;
    cin >> N >> M >> K;
    UnionFind unionFind(N);
    vector<ll> ans(N, 0);
    vector<vector<ll>> friends(N);
    vector<vector<ll>> blocks(N);
    rep(i, M) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        unionFind.unit(a, b);
        friends[a].push_back(b);
        friends[b].push_back(a);
    }
    rep(i, K) {
        ll c, d;
        cin >> c >> d;
        c--;
        d--;
        blocks[c].push_back(d);
        blocks[d].push_back(c);
    }

    rep(i, N) {
        ll s = unionFind.get_size(i);
        ll t = friends[i].size();
        ll b = 0;
        for (ll bb: blocks[i]) {
            if (unionFind.is_same(i, bb)) b++;
        }
        cout << max(0LL, s - t - b - 1) << ' ';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 20340
#include <iostream>
#include <list>
#include <stack>
#include <set>
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	ll n, a[310][310], dis[310][310];
	bool f[310][310] = {};
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			dis[i][j] = a[i][j];
		}
		dis[i][i] = 0;
	}
	for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		if (a[i][j] != dis[i][j]) {
			cout << -1 << endl;
			return 0;
		}
	}
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++) {
		if (i == j || i == k || j == k)continue;
		if (dis[i][j] == dis[i][k] + dis[k][j])f[i][j] = 1;
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		if (!f[i][j])ans += dis[i][j];
	}
	cout << ans / 2 << endl;
	return 0;
}



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

int N, M;
string s[100], t[100];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> s[i];
	cin >> M;
	for (int i = 0; i < M; i++) cin >> t[i];

	int ans = 0;
	for (int i = 0; i < N; i++) {
		int tmp = 1;
		for (int j = 0; j < N; j++) {
			if (i != j && s[i] == s[j]) tmp++;
		}
		for (int j = 0; j < M; j++) {
			if (s[i] == t[j]) tmp--;
		}

		ans = max(ans, tmp);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

  int a,b,c,i;

  int count;


  scanf("%d %d %d\n",&a,&b,&c);


  for(i=a,count=0;i<=b;i++){


      if(c%i==0) count ++;


  }


  printf("%d\n",count);


return 0;


}

Measured memory_bytes: 600
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#define rep(i,n) for(int i = 0;i < (n); ++i)
using namespace std;

typedef long long LL;
typedef long double LD;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n)cin >> a[i];

    vector<int> road;
    vector<int> seen(n + 1, -1);
    int c = 1, l = 0;
    int pos = 1;
    while(seen[pos] == -1){
        seen[pos] = road.size();
        road.push_back(pos);
        pos = a[pos - 1];
    }
    c = road.size() - seen[pos];
    l = seen[pos];
    if(k < l)cout << road[k] << endl;
    else{
        k -= l;
        k %= c;
        cout << road[l + k] << endl;
    }
}

Measured memory_bytes: 5856
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        int n=Integer.parseInt(br.readLine());
        String str[]=br.readLine().split(" ");
        int arr[]=new int[n];
        for(int i=0;i<n;i++)
        arr[i]=Integer.parseInt(str[i]);
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    if(arr[i]!=arr[k]&&arr[i]!=arr[j]&&arr[j]!=arr[k])
                    {
                        if(arr[i]+arr[j]>arr[k]&&arr[k]+arr[j]>arr[i]&&arr[i]+arr[k]>arr[j])
                        cnt++;
                    }
                }
            }
        }
        pw.println(cnt);
        pw.flush();
        pw.close();
    }
}

Measured memory_bytes: 33568
x1, y1, x2, y2 = map(int, input().split())
x3 = x2 + y1 - y2
y3 = y2 - (x1 - x2)
x4 = (x1 + x3) - x2
y4 = (y1 + y3) - y2
print (x3,y3,x4,y4)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
int g[500][500];
int G[500][500];
using namespace std;

int main(){
  int H,W;
  cin>>H>>W;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>g[i][j];
      G[i][j]=g[i][j];
    }
  }
  int ans=0;
  for(int j=0;j<W;j++){
    for(int i=0;i<H-1;i++){
      if(g[i][j]%2){
        g[i][j]--;
        g[i+1][j]++;
        ans++;
      }
    }
  }
  for(int j=0;j<W-1;j++){
    if(g[H-1][j]%2){
      g[H-1][j]--;
      g[H-1][j+1]++;
      ans++;
    }
  }
  cout<<ans<<endl;
  for(int j=0;j<W;j++){
    for(int i=0;i<H-1;i++){
      if(G[i][j]%2){
        G[i][j]--;
        G[i+1][j]++;
        cout<<i+1<<" "<<j+1<<" "<<i+2<<" "<<j+1<<endl;
      }
    }
  }
  for(int j=0;j<W-1;j++){
    if(G[H-1][j]%2){
      G[H-1][j]--;
      G[H-1][j+1]++;
      cout<<H<<" "<<j+1<<" "<<H<<" "<<j+2<<endl;
    }
  }
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++) cin >> vec.at(i);
	int64_t answer = 10000000000;
	for (int i = 0; i <= 100; i++) {
		int64_t zan = 0;
		for (int j = 0; j < n; j++) {
			zan += (vec.at(j) - i) * (vec.at(j) - i);
		}
		(answer > zan) ? answer = zan: answer = answer;
	}
	cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define pq          priority_queue
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323

void solve()
{
    ll n,k;cin>>n>>k;
    if(n&1)
    {
        if(k>n/2+1) { cout<<"NO"; exit(0); }
    }
    else
    {
        if(k>n/2) { cout<<"NO"; exit(0);}
    }
    cout<<"YES";
}

int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


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

int main(){
string s;
  cin >> s;
  bool flag =true;
  rep(i,s.size()){
    if(flag){
      cout << s.at(i);
      flag = false;
    }else{
      flag = true;
    }
  }
  cout << endl;

	return 0;
}


Measured memory_bytes: 512
n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[0]*n

for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)


Measured memory_bytes: 54872
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1c(i, n) for (ll i = 1; i <= (ll)(n); i++)

typedef long long ll;

const int MAX_N = 100010, INF = 10000010;
int A, B, M;
int a[MAX_N], b[MAX_N], x, y, c;

int main() {
  cin >> A >> B >> M;
  int min_a = INF, min_b = INF;
  rep(i, A) {
    scanf("%d", &a[i]);
    min_a = min(min_a, a[i]);
  }
  rep(i, B) {
    scanf("%d", &b[i]);
    min_b = min(min_b, b[i]);
  }
  int ans = min_a + min_b;
  rep(i, M) {
    scanf("%d %d %d", &x, &y, &c);
    ans = min(ans, a[x-1] + b[y-1] - c);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Mod 1000000007
using namespace std;
int dp[300010][4][3];
char str[300010];
int main()
{
	int n;
	scanf("%s",str+1);
	n=strlen(str+1);
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<3;k++)
			{
				if(str[i]!='0')
				{
					if(k)dp[i][j][k-1]=(dp[i][j][k-1]+dp[i-1][j][k])%Mod;
					else if(j==3)dp[i][j-1][k]=(dp[i][j-1][k]+dp[i-1][j][k])%Mod;
					else dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k])%Mod;
				}
				if(str[i]!='1')
				{
					if(k==2)dp[i][j][k-1]=(dp[i][j][k-1]+dp[i-1][j][k])%Mod;
					else dp[i][j][k+1]=(dp[i][j][k+1]+dp[i-1][j][k])%Mod;
				}
			}
	int ans=0;
	for(int j=0;j<4;j++)
		for(int k=0;k<3;k++)
			if(j>k)ans=(ans+dp[n][j][k])%Mod;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 14592
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
int main(){
  int n,m,i;
  long long s=0,a,b=-1,c=1;
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++){
    scanf("%lld",&a);
    s=(s+a)%m;//printf("%lld\n",s);
    hin(s);
  }
  hin(1e9+10);
  b=N[hout()];
  c=1;//printf("\n%lld\n",b);
  //for(i=0;i<m;i++)printf("%lld\n",b[i]);
  for(i=s=0;i<n;i++){
    a=N[hout()];//printf("%lld\n",a);
    if(a==b)c++;
    else{//printf("%lld %lld\n",b,c);
      s+=(c*(c+1)/2);
      if(b)s-=c;
      b=a;
      c=1;
    }
  }
  printf("%lld\n",s);
  return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
	int n, result = 0;
	cin >> n;
	vector<int> a(n);
	double sum;
	for (int i = 0; i < n; i++) {
			cin >> a[i];
			sum += a[i];
	}
	int same = round(sum / n);
	for (int i = 0; i < n; i++) {
		result += pow(a[i] - same, 2);
	}
	cout << result;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    long long i, cnt=0, ans=0;
    cin>>s;
    for(i=0; i<s.size(); i++)
    {
        if(s[i]=='B')
            cnt++;
        else
            ans+=cnt;
    }
    cout<<ans;
}


Measured memory_bytes: 3728
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>
#include <random>
#include <chrono>
#include <numeric>
#include <cassert>
#include <iso646.h>
#include <exception>
#include <stdexcept>

using namespace std;

typedef long long i64;

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

    int rows, cols;
    cin >> rows >> cols;

    char grid[50][50];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            cin >> grid[r][c];

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (grid[r][c] == '.')
            {
                int bombs = 0;
                for (int dr = -1; dr <= 1; dr++)
                    for (int dc = -1; dc <= 1; dc++)
                    {
                        int r0 = r + dr;
                        int c0 = c + dc;

                        bool good_r = r0 >= 0 && r0 < rows;
                        bool good_c = c0 >= 0 && c0 < cols;

                        if (good_r && good_c)
                            bombs += grid[r0][c0] == '#';
                    }

                grid[r][c] = bombs + '0';
            }

    for (int r = 0; r < rows; r++)
    {
        for (int c = 0; c < cols; c++)
            cout << grid[r][c];
        cout << '\n';
    }
        
}

Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
A1 = []  
A2 = []
for i in range(N):
    if A[i] > 0:
        A1.append(A[i])
    if A[i] < 0:
        A2.append(-A[i])
A1.sort(reverse=True)
A2.sort(reverse=True)
ans = 1
if max(A)< 0:
    if K%2 == 0:
        for i in range(K):
            ans = (ans * A2[i])%mod
    else:
        A2.sort()
        for i in range(K):
            ans = (ans * A2[i])%mod
            ans = (mod - ans)%mod
elif max(A) == 0:
    if K%2 == 1:
        ans = 0
    else:
        if len(A2) >= K:
            for i in range(K):
                ans = (ans * A2[i])%mod
        else:
            ans = 0
else:
    A3 = []
    for i in range(len(A2)//2):
        A3.append(A2[2 * i] * A2[2 * i + 1])
    A4 = []
    A5 = []
    for i in range(len(A1)//2):
        A4.append(A1[2 * i] * A1[2 * i + 1])
    for i in range((len(A1) - 1)//2):
        A5.append(A1[2 * i + 1] * A1[2 * i + 2])
    if len(A1) + 2 * len(A3) < K:
        if N == K:
            for i in range(N):
                ans = (ans * A[i])%mod
        else:
            ans = 0
    else:
        if K%2 == 0:
            A6 = A3 + A4
            A6.sort(reverse=True)
            for i in range(K//2):
                ans = (ans * A6[i])%mod
        else:
            A6 = A3 + A5
            A6.sort(reverse=True)
            ans = A1[0]
            for i in range((K - 1)//2):
                ans = (ans * A6[i])% mod
print(ans)

Measured memory_bytes: 31692
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	s = input()
	print(min(s.count('1'),s.count('0'))*2)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(l):
	x = l.pop()
	y = l.pop()
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	l.append(min(x,y))
	return gcd(l) if len(l) > 1 else l[0]

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Measured memory_bytes: 64108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
struct edge{ll to,cost;};
const int inf = 1<<27;
const ll INF = 1LL<<60;
const int COMBMAX = 1001001;
const ll MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n, ll mod = MOD){ll res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}


int main(){
    ll N, K; cin >> N >> K;
    vector<ll> a(N + 1);
    rep(i, N) cin >> a[i + 1];
    rep(i, N) a[i + 1] += a[i];
    vector<ll> s;
    rep(i, N + 1) rep(j, i) s.emplace_back(a[i] - a[j]);
    N = (N * (N + 1)) / 2;
    ll ans = 0;
    for(int i = 60; 0 <= i; --i){
        vector<bool> store(N, false);
        ll cnt = 0;
        rep(j, N){
            if (s[j] >> i & 1LL){
                cnt++;
                store[j] = true;
            }
        }
        if (K <= cnt){
            ans += (1LL << i);
            rep(j, N) if(!store[j]) s[j] = 0;
        }
    }
    pt(ans);

    return 0;
}

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

if N == 3:
    print("2 5 63")
    import sys
    sys.exit()
    
ans=[]
for i in range(3,30001):
  if len(ans)==N-1:
    break
  if i%2==0 or i%3==0 or i%5==0:
    ans.append(i)

s=sum(ans)

if s%2==1:
  ans[0]=2
  s=sum(ans)

ans.append(30000 - s%30)

print(*ans)

Measured memory_bytes: 4564
N=int(input())
L=list(map(int,input().split()))
Left=[[0,0]]
Right=[[0,N]]
for i in range(N):
    Left.append([Left[i][0]+L[i],i+1])
for i in range(N):
    Right.append([Right[i][0]+L[i*(-1)-1],N-i-1])
Right=list(reversed(Right))
Left=sorted(Left, key=lambda x: x[0])
_sum_=Right[0][0]
Left=sorted(Left, key=lambda x: x[0],reverse=True)
Right=sorted(Right, key=lambda x: x[0])
Left.append([0,0])
Right.append([0,0])
 
j=0
s=0
ans=0
for i in range(N+1):
    if i != 0:
        if Left[i][0]!=Left[i-1][0]:
            s=0
    while(Left[i][0]+Right[j][0]<_sum_ and j<=N):
        j+=1
    if j>N:
        break
    elif Left[i][0]+Right[j][0]>_sum_:
        continue
    else:
        while(Left[i][0]+Right[j][0]==_sum_ and j<=N):
            if Left[i][1]>=Right[j][1]:
                j+=1
            else:
                s+=1
                ans+=s
                break
print(ans)

Measured memory_bytes: 84132
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int ans = 0;
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        boolean flag = true;
        while(flag){
            flag = false;
            for(int j = n-1; j > 0; j--){
                if(a[j] < a[j-1]){
                    int work = a[j];
                    a[j] = a[j-1];
                    a[j-1] = work;
                    ans ++;
                    flag =true;
                }
            }
        }
        for(int i = 0; i < n-1; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println(a[n-1]);
        System.out.println(ans);
    }
}



Measured memory_bytes: 26300
#include<cstdio>
#include<cstring>
#include<ctype.h>
using namespace std;

	int N, H;
	int T[1000];
	char S[1000][210];
	char c[20];
	int result[20] = {0};


int main() {
		
	scanf("%d%d", &N, &H);
	for(int i = 0; i < N; i++) {
		scanf("%s%d", S[i], &T[i]);
	}
	
	for(int i = 0; i < N; i++) {
		int len = strlen(S[i]);
		for(int j = 0; j < len; j++) {
			bool ac = false;
			while(!ac) {
				if(T[i] < 0) {
					j = len;
					H--;
					break;
				}
				printf("? %s\n", S[i]); fflush(stdout);
				scanf("%s", c);
				if(c[0] == S[i][j] || toupper(c[0]) == S[i][j]) {
					ac = true;
					S[i][j] = '_';
					result[0]++;
					result[1]++;
				} else {
					T[i]--;
					result[1]++;
				}
			}
		}
		if(H <= 0) {
			printf("! Game Over\n"); fflush(stdout);
			return 0;
		}
	}
	double x = (double)result[0] / result[1] * 100.0 * 10.0;
	long long u = (long long) x;
	double p = u;
	p = p / 10;
	printf("! Game Clear %.1lf\n", p);//(double)result[0] / result[1] * 100.0);
	fflush(stdout);
	
}

Measured memory_bytes: 1300