akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int A[2000],f,l[2000],n,j,M[2000];
void slove(int,int);
main()
{
  int q,i;  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&M[i]);
  }
  for(j=0;j<q;j++){
    slove(0,M[j]);
  }
  for(j=0;j<q;j++){
    if(l[j]==1)printf("yes\n");
    else  printf("no\n");
  }
  return 0;
}



void slove (int a  ,int b){
  if(b==0){
    l[j]=1;
  }
  else if( b>0 && a<n){
    slove(a+1,b-A[a]);
    slove(a+1,b);
  }
  
  
}

Measured memory_bytes: 588
#include <iostream>
#include <map>
#include <cmath>

using namespace std;
typedef long long ll;

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

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

int main(){
  ll a, b, c, d;
  std::cin >> a >> b >> c >> d;
  ll c_div = b / c - (a-1) / c;
  ll d_div = b / d - (a-1) / d;
  ll common = lcm(c, d);
  ll cd_div = b / common - (a-1) / common;
  std::cout << b - (a-1) - c_div - d_div + cd_div << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	i64 w, h, x, y; scanf("%lld%lld%lld%lld", &w, &h, &x, &y);
	
	bool ans = false;
	if(!(w % 2 or h % 2)) ans = (x == w / 2 and y == h / 2);
	printf("%.12Lf %d\n", (long double)h * (long double)w / (long double)2, ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> H;
    map<int, int> mp;
    for (int i = 0; i < N; i++) {
        int h;
        cin >> h;
        H.push_back(h);
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        mp[a] = max(mp[a], H[b-1]);
        mp[b] = max(mp[b], H[a-1]);
    }
    long long int ans = 0;
    for (int i = 0; i < N; i++) {
        if(mp[i+1] < H[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8320
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iterator>
#include <cstring>

using namespace std;
const int INF = (1<<30);
typedef pair<int, int> P;
typedef long long ll;
#define PB push_back
#define rep(i, a) for (int i = 0; i < a; i++)

int sx, sy;

int gx, gy;

int qqq;

//各座標までの最短距離
int d[100][100];


//移動方向のベクトル
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

//汎用
ll ans = 0;
pair<int, int> red[101], blue[101];
ll BIG = 10000000000;

//累乗
ll POW(ll a, ll b) {
ll c = 1;
for (int i = 0; i < b; ++i) {
c *= a;
}
return c;
}

//階乗
int Kaijou(int a) {
if (a < 2) return 1;
return a * Kaijou(a - 1);
}


int A[200000];
int kinds[200001];


int main() 
{
	int n,p;
	
	while(1){
		cin >> n>> p;
		if (n == 0&&p==0) break;

		int stone = p;
		vector<int> s(n);
		rep(i, n) s[i] = 0;
        int turn = 0;

		while (1) {

			if (stone) {
				s[turn]++;
				stone--;
				if (s[turn] == p) break;
			}
			else {
				if (s[turn]) {
					stone += s[turn];
					s[turn] = 0;
				}
			}

			turn = (turn + 1) % n;
		}

		cout << turn << endl;
	}

	cin >> qqq;
}



Measured memory_bytes: 3104
N = int(input())
P = list(map(float, input().split()))

dp = [0 for _ in range(N + 1)]
dp[0] = 1

for i in range(N):
    p = P[i]
    for j in range(N)[::-1]:
        dp[j + 1] += dp[j] * p
        dp[j] *= 1 - p

print(sum(dp[N // 2 + 1:]))

Measured memory_bytes: 71060
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define itn int
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sort(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=9e18;

int main(){
  int n,k; cin >> n >> k;
  set<pll> st;
  set<pll> st0;
  rep(i,n){
    ll x,y;
    cin >> x >> y;
    st.insert(pll(x,y));
  }
  for(auto a:st){
    for(auto b:st){
      st0.insert(pll(a.first,a.second));
      st0.insert(pll(a.first,b.second));
      st0.insert(pll(b.first,a.second));
      st0.insert(pll(b.first,b.second));
    }
  }
  ll ans=lnf;
  for(auto a:st0){
    for(auto b:st0){
      ll area=(a.first-b.first)*(a.second-b.second);
      int cnt=0;
      for(auto c:st){
        if(a.first<=c.first&&a.second<=c.second&&c.first<=b.first&&c.second<=b.second) cnt++;
      }
      if(cnt>=k) chmin(ans,area);
    }
  }
  cout << ans << endl;
}

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

int main(){
int N, K;
cin >> N >> K;
ll sum = 0;
for (ll i = K; i <= N + 1; i++)
{
    sum += i * (N - i + 1) + 1;
    sum %= (1000000000LL + 7);    
}


cout << sum << endl;

}


Measured memory_bytes: 3648
from io import StringIO


UP = 0
LEFT = 1
LEFTUP = 2


def lcs(s, t):
    m = len(s)
    n = len(t)
    # dp[i][j] = LCS-length of (s[:i], t[:j])
    dp = [[(0, None)] * (n + 1) for i in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                continue
            elif s[i - 1] == t[j - 1]:
                dp[i][j] = (dp[i - 1][j - 1][0] + 1, LEFTUP)
            elif dp[i - 1][j][0] >= dp[i][j - 1][0]:
                dp[i][j] = (dp[i - 1][j][0], UP)
            else:
                dp[i][j] = (dp[i][j - 1][0], LEFT)
    buf = StringIO()
    i = m
    j = n
    while i > 0 and j > 0:
        if dp[i][j][1] == LEFTUP:
            buf.write(t[j - 1])
            i -= 1
            j -= 1
        elif dp[i][j][1] == UP:
            i -= 1
        else:
            j -= 1
    buf.seek(0)
    ans = buf.read()[::-1]
    return ans


if __name__ == "__main__":
    print(lcs(input(), input()))


Measured memory_bytes: 307076
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define ld long double
#define zeros(x) x^(x-1)&x
#define pii pair<ll,ll>
#define cd complex<double>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define Nmax 200005
#define OFF 100001
using namespace std;

int n,v[Nmax],R[Nmax],L[Nmax],mn,lst;
vector<pii> st;


int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> v[i];
    mn = 1e9;
    lst = 0;
    st.push_back({-1, 0});
    for (int i=1;i<=n;i++){
        while (st.back().first > v[i]) st.pop_back();
        L[i] = st.back().second;
        st.push_back({v[i],i});
    }
    st.clear();
    st.push_back({-1,n+1});
    for (int i=n;i>=1;i--){
        while (st.back().first > v[i]) st.pop_back();
        R[i] = st.back().second;
        st.push_back({v[i],i});
    }
    ll ans = 0;
    for (int i=1;i<=n;i++){
        ans = ans + 1LL * v[i] * (i - L[i]) * (R[i] - i);
    }

    cout << ans << '\n';

    return 0;
}


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

int main(void)
{
  int N=0;

  cin >> N;
  int Nx =N;
  int Sn=0;
  while(Nx!=0)
  {
    Sn+=Nx%10;
    Nx/=10;
  }

  if(N%Sn==0)
  {
    cout << "Yes";
  }
  else
  {
    cout << "No";
  }

  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll MOD = 1000000007LL;
ll inv(ll K) {
  ll A = MOD - 2;
  ll ret = 1;
  ll D = K;
  while (A > 0) {
    if (A % 2 == 1) {
      ret = (ret * D) % MOD;
    }
    D = (D * D) % MOD;
    A /= 2;
  }
  return ret;
}

ll FC[100005];
ll IFC[100005];
ll initFC(int N) {
  FC[0] = 1;
  for (ll i=1; i<=N; i++) {
    FC[i] = (FC[i-1] * i) % MOD;
  }
  IFC[N] = inv(FC[N]);
  for (ll i=N; i>=0; i--) {
    IFC[i-1] = (IFC[i] * i) % MOD;
  }
}

ll A[100005];
int main() {
  ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;
  initFC(N);
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  sort(A, A+N);
  ll ret = 0;
  for (int i=N-1; i>=K-1; i--) {
    ll d = (FC[i] * IFC[i-K+1]) % MOD;
    d = (d * IFC[K-1]) % MOD;
    d = (A[i] * d) % MOD;
    //cout << d << endl;
    ret = (ret + d) % MOD;
  }
  for (int i=0; i<N-K+1; i++) {
    ll d = (FC[N-i-1] * IFC[N-i-K]) % MOD;
    d = (d * IFC[K-1]) % MOD;
    d = (A[i] * d) % MOD;
    //cout << -d << endl;
    ret = ((ret - d) % MOD + MOD) % MOD;
  }
  cout << ret << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,i;
    cin>>n>>k;
    int ar[n];
    for(i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    int sum=0;
    for(i=0;i<n;i++){
        if(ar[i]>=k)sum++;
    }
    cout<<sum;
    return 0;
    
}

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

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

void get_N1234 (int64 *n1, int64 *n2, int64 *n3, int64 *n4)
{
  int cnt;

  if (n2 == NULL) {
    cnt = scanf("%lld", n1);
    return;
  }
  if (n3 == NULL) {
    cnt = scanf("%lld %lld", n1, n2);
    return;
  }
  if (n4 == NULL) {
    cnt = scanf("%lld %lld %lld", n1, n2, n3);
    return;
  }
  cnt = scanf("%lld %lld %lld %lld", n1, n2, n3, n4);
  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;
  int  cnt;

  buf = malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;
  int  cnt;

  buf = malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;


int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

int main()
{
  int64 h,w;
  int64 s,r;
  
  get_NK(&h, &w);

  s = h*w;

  if ((h == 1) ||
      (w == 1)) {
    r = 1;
    printf("%lld", r);
    return 0;
  }

  if (s & 1)  {
    r = s/2 + 1;
  } else {
    r = s / 2;
  }

  printf("%lld", r);
  return 0;
}



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

using namespace std;

int main(){
  int N,M,C; cin>>N>>M>>C;
  vector<int>B(M,0);
  for(int i=0;i<M;i++) cin>>B[i];
  vector<vector<int> > A(N,vector<int>(M,0)); 
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>A[i][j];
    }
  }

  int ans=0;

  for(int i=0;i<N;i++){
    int temp=0;
    for(int j=0;j<M;j++){
      temp+=A[i][j]*B[j];
    }
    if(temp+C>0) ans++;
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    ans=0
    for i in range(1,N+1):
        if i>=K:
            ans+=1/N
            continue
        p=1/N
        j=i
        while  j<K:
            p*=0.5
            j*=2
        ans+=p
    print(ans)
    





if __name__ == "__main__":
    main()

Measured memory_bytes: 77668
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int> >;

int main() {
    int num[2005]={0};

    // 頂点数と辺数
    int N, X, Y; cin >> N >> X >> Y;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        //int a, b;
        //cin >> a >> b;
        G[i].push_back(i+1);
        G[i+1].push_back(i);
    }
    G[X-1].push_back(Y-1);
    G[Y-1].push_back(X-1);

    for (int j = 0; j < N; j++)
    {

    // BFS のためのデータ構造
    vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[j] = 0;
    que.push(j); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }

    // 結果出力 (各頂点の頂点 0 からの距離を見る)
    for (int v = 0; v < N; ++v) num[dist[v]] += 1;
    }

    for (int i = 1; i < N; i++)
    {
        cout << num[i]/2 << endl;
    }

}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

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

ll mod(ll a) {
	if (a > 0) return a % MOD;
	if (a % MOD == 0) return 0;
	ll x = -a / MOD + 1;
	a += x * MOD;
	return a % MOD;
}

template <typename T> void dump(T x) { cout << x << endl; }
void dumpf(double x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
// ll dx[4]    = {1, 0, -1, 0};
// int dy[4]    = {0, 1, 0, -1};
// ll pas[5001][5002];
ll dp[114514][12] = {};
vector<ll> g[114514];
ll n, m;

void rec(int v, int d, int c) {
	if (dp[v][d] != 0) return;
	// cout << v << " " << d << endl;
	dp[v][d] = c;
	if (d == 0) return;
	for (int i = 0; i < g[v].size(); ++i) {
		int u = g[v][i];
		rec(u, d - 1, c);
	}
	rec(v, d - 1, c);
}

int main() {
	IOS();
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	ll q;
	cin >> q;
	vector<ll> v(q), d(q), c(q);
	for (int i = 0; i < q; ++i) { cin >> v[i] >> d[i] >> c[i]; }
	for (int i = q - 1; i >= 0; --i) { rec(v[i], d[i], c[i]); }
	for (int i = 1; i <= n; ++i) { dump(dp[i][0]); }
}

Measured memory_bytes: 19188
#include<bits/stdc++.h>
using namespace std;
long long n,m,x,ans,z;
long long gcd(long long a,long long b){
    if (a%b==0) return b;
    return gcd(b,a%b);
}
bool prime[10000010];
vector<long long> p;
int main(){
	for (long long i=2;i<=10000000;i++) if (prime[i]==0) for (long long j=i+i;j<=10000000;j+=i) prime[j]=1;
	for (long long i=2;i<=10000000;i++) if (prime[i]==0) p.push_back(i);
	cin>>n>>m;
	x=gcd(n,m);z=x;
	for (long long i=0;i<p.size();i++)
		if (x%p[i]==0){
			ans++;
			while (x%p[i]==0) x/=p[i];
		}
	if (x>=1000000) ans+=1;
	cout<<ans+1<<endl;
	return 0;
}

Measured memory_bytes: 20332
#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;
#define mem(x,y) memset(x,y,sizeof(x))  
#define lli long long int
#define ll long long 
#define ld long double
#define pb push_back
#define mp make_pair
#define F first
#define S second 
#define LB lower_bound
#define UB upper_bound
#define BS binary_search
#define pii pair<lli,lli>
const long long int mod=1000000009;
//const long long int mod=998244353;
const long double PI=3.141592653589793;
const long long int inf=1e18;
const long long int inf2=LLONG_MAX;
#define setBitCount(x) __builtin_popcountll(x)
#define all(a) (a).begin(), (a).end()
#define all_r(a) (a).rbegin(), (a).rend()
lli gcd(lli a,lli b)
{
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
}
// calculating (x^y)%p
lli power(lli x,lli y,lli p)
{
    lli res = 1;      
    x = x % p;  
    while (y > 0)
    {
        if (y & 1) //y is odd  
        res = (res*x) % p;
        y = y>>1; 
        x = ( (x%p)*(x%p) )% p;  
    }
    return res%p;
}
// calculating modular inverse using fermat little theorem
lli modInverse(lli n,lli p) 
{
    return power(n, p-2, p)%p;
}

// policy based data structures !!
#define ordered_set tree<lli, null_type,less<lli>, rb_tree_tag,tree_order_statistics_node_update>
// s.order_of_key (k) : Number of items strictly smaller than k
// *(s.find_by_order(k)) : K-th element in a set (counting from zero)
ld a[3005];
ld dp[3005][3005][3];
void solve()
{
   lli n;
   cin>>n;
   
   
   for(lli i=1;i<=n;i++)
   cin>>a[i];
   
   
   for(lli i=0;i<=n;i++)
   for(lli j=0;j<=n;j++)
   for(lli k=0;k<2;k++)
   dp[i][j][k]=0.0;
   
   dp[1][1][0]=a[1];
   dp[1][1][1]=1.0-a[1];
   
   dp[1][0][0]=1.0-a[1];
   dp[1][0][1]=a[1];
   
   ld pa=a[1],pb=(1.0-a[1]);
   for(lli i=2;i<=n;i++)
   {
      pa=pa*1.0*a[i];
      pb=pb*1.0*(1.0-a[i]);
      dp[i][0][0]=pb;
      dp[i][0][1]=pa;
      for(lli j=1;j<=i;j++)
      {
         dp[i][j][0]=dp[i-1][j-1][0]*a[i]+dp[i-1][j][0]*(1.0-a[i]);
         dp[i][j][1]=dp[i-1][j-1][1]*(1.0-a[i])+dp[i-1][j][1]*(a[i]);
      }
   }
   ld ans=0.0;
   for(lli i=n/2+1;i<=n;i++)
   {
      ans+=dp[n][i][0];
   }
   cout<<fixed<<setprecision(10)<<ans;
}
int main()
{
   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    lli T;
    //cin>>T;
    T=1;
    while(T--)
    {
        solve();
    }




    return 0;
}

Measured memory_bytes: 422912
import java.util.Scanner;

public class Main {

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

		if (s.matches("^A[a-z][a-z]*C[a-z]*[a-z]")) {
			System.out.println("AC");
		} else {
			System.out.println("WA");
		}

		sc.close();
	}
}

Measured memory_bytes: 23252
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
    int a,b;
    cin >> a >> b;
    if(a > b) cout << a-1 << endl;
    else cout << a << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  string s;
  cin >> s;
  int n = s.size();
  bool ok = true;
  rep(i, (n - 1) / 2 + 1) if(s[i] != s[n - 1 - i]) ok = false;
  string s1 = s.substr(0, (n - 1) / 2);
  string s2 = s.substr((n - 1) / 2 + 1, (n - 1) / 2);
  n = s1.size();
  rep(i, (n - 1) / 2 + 1) if(s1[i] != s1[n - 1 - i]) ok = false;
  n = s2.size();
  rep(i, (n - 1) / 2 + 1) if(s2[i] != s2[n - 1 - i]) ok = false;
  cout << (ok ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <fstream>


using namespace std;

const int INIVAL = (1<<31) -1;

class SegmentTree{
public:
    int n; //array size
    vector<int> D; //minimum values for the range represented by node i of the segment tree
    //
    void initRMQ(int n_);
    void update(int k, int x);
    int findMin(int a, int b);
    int query(int a, int b, int k, int l, int r);
    //
    void printTree();
};

int main()
{
    // input from cmd window
    SegmentTree ist;
    int n, q;
    cin >> n >> q;
    ist.initRMQ(n);
    vector<int> out;
    int x, y, z;
    for (int i = 0; i < q; i++) {
        cin >> x >> y >> z;
        if (x == 0) { // update()
            ist.update(y, z);
        }
        else if (x == 1) { // findMin()
            out.push_back(ist.findMin(y, z));
        }
    }

//    // input from file
//    SegmentTree ist;
//    ifstream infile("in6.txt");
//    int n, q;
//    infile >> n >> q;
//    ist.initRMQ(n);
//    vector<int> out;
//    int x, y, z;
//    for (int i = 0; i < q; i++) {
//        infile >> x >> y >> z;
//        if (x == 0) { // update()
//            ist.update(y, z);
//            //ist.printTree();
//        }
//        else if (x == 1) { // findMin()
//            out.push_back(ist.findMin(y, z));
//            //ist.printTree();
//        }
//    }

    // output
    for (int i = 0; i < out.size(); i++) {
        cout << fixed << out[i] << "\n";
    }

    return 0;
}

void SegmentTree::initRMQ(int n_) {
    n = 1;
    while (n < n_) {n *= 2;}
    D = vector<int>(2*n-1, INIVAL);
}

void SegmentTree::printTree() {
    for (int i = 0; i < n; i++) {
        cout << fixed << this->D[i] << "\n";
    }
}


void SegmentTree::update(int k, int x) {
    k += n - 1;
    D[k] = x;
    while (k > 0) {
        k = (k-1)/2;
        D[k] = min(D[k*2+1], D[k*2+2]);
    }
}

int SegmentTree::findMin(int a, int b) {
    return query(a, b+1, 0, 0, n);
}

int SegmentTree::query(int a, int b, int k, int l, int r) {
    if ((r <= a) || (b <= l)) { // case 1
        return INIVAL;
    }
    else if ((a <= l) && (r <= b)) { // case 2
        return D[k];
    }
    else { // case 3
        int vl = query(a, b, k*2+1, l, (l+r)/2);
        int vr = query(a, b, k*2+2, (l+r)/2, r);
        return min(vl, vr);
    }
}



Measured memory_bytes: 4996
#include <bits/stdc++.h>
#define CYES cout << "Yes" \
                  << "\n";
#define CNO cout << "No" \
                 << "\n";
#define CFS           \
    cin.tie(nullptr); \
    ios::sync_with_stdio(false);
#define CST(x) cout << fixed << setprecision(x);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
const int IINF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = (int)1e9 + 7;
const string MM = " ";

int main()
{
    string s;
    cin >> s;
    if (s == "AAA" || s == "BBB") {
        cout << "No" << "\n";
    }
    else {
        cout << "Yes" << "\n";
    }
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if reduce(gcd, A) != 1:
    print("not coprime")
    exit()
ma = max(A)
p = list(range(ma+1))
for x in range(2, int(ma ** 0.5) + 1):
    if p[x]:
        for i in range(x + x, ma+1, x):
            p[i] = x

s = [set() for _ in range(N)]
t = set()

for i, x in enumerate(A):
    while x != 1:
        s[i].add(x)
        t.add(x)
        x //= p[x]
l = sum(len(x) for x in s)
print("pairwise coprime" if l == len(t) else "setwise coprime")


Measured memory_bytes: 435144
#include<iostream>
using namespace std;
 
int main(){
  int n, a;
  cin >> n >> a;
  int s = 0;
  while(1){
    if(n - 500 * s < 0){
      break;
    }
    s++;
  }
  if(n - 500 * (s - 1) > a){
    cout <<"No";
  }
  else{
    cout << "Yes";
  }
}

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

int main()
{
	int y1, m1, d1, y2, m2, d2;
	const int md[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30 ,31, 30, 31 };

	cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;

	while (y1 >= 0 && m1 >= 0 && d1 >= 0 && y2 >= 0 && m2 >= 0 && d2 >= 0) {
		int d = d2 - d1;

		if(m1 <= m2) {
			d += 365 * (y2 - y1);

			for (int i = m1 - 1; i < m2 - 1; i++)
				d += md[i];
		}
		else {
			d += 365 * (y2 - y1 - 1);

			for (int i = m1 - 1; i < 12; i++)
				d += md[i];

			for (int i = 0; i < m2 - 1; i++)
				d += md[i];
		}

		for (int i = y1; i <= y2; i++) {
			if (i % 4 == 0 && i % 400 != 100 && i % 400 != 200 && i % 400 != 300) {
				if (!(i == y1 && m1 > 2) && !(i == y2 && m2 < 3))
					d++;
			}
		}

		cout << d << endl;

		cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
	}

	return 0;
}



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

signed main(){
    int n;
    //ofstream cout("out.txt");
    while(cin>>n){
        if(n == 0)break;
        string s[n];
        for(int i=0;i<n;i++){
            cin>>s[i];
        }
        for(int i=0;i<n;i++){
            if(s[i][0]!='.')continue;
            for(int j=1;j<s[i].size();j++){
                if(s[i][j] != '.'){
                    s[i][j-1] = '+';
                    break;
                }
            }
        }

        for(int i=1;i<n;i++){
            for(int j=0;j<s[i].size();j++){
                if(s[i][j] == '.')s[i][j] = ' ';
            }
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<s[i].size();j++){
                if(s[i][j] == '+'){
                    int now = i-1;
                    while(now>0 && s[now][j]==' '){
                        s[now][j] = '|';
                        now--;
                    }
                }
            }
        }
        for(int i=0;i<n;i++)cout << s[i] << "\n";
    }
}



Measured memory_bytes: 3872
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
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;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int N;
    cin >> N;
    string pre;
    bool ok = true;
    map<string,int> mp;
    REP(i,N) {
        string W; cin >> W;
        if(i == 0) {
            pre = W;
            mp[W] = 1;
        } else {
            if(pre[pre.size()-1] != W[0]) {
                ok = false;
            } else if(mp.count(W)) {
                ok = false;
            } else {
                mp[W] = 1;
                pre = W;
            }
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;

#pragma GCC optimize("O3")
#define MOD 1000000007
#define pb push_back
#define fi first
#define se second
#define fr front()
#define ba back()
#define tp top()
#define mem(x,n) memset(x,n,sizeof(x));
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,l) for(auto it=l.begin();it!=l.end();it++)
#define pnl printf("\n")
#define len(x) x.length()

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> pii;
typedef pair<pii,int> piii;
const int inf=(1<<30);
const LL llinf=(1ll<<60);
const double eps=(1e-10);
//const double pi=2*acos(0.0);
//const double GOLD=((1+sqrt(5))/2);
const int xx[8]={1,0,-1,0,1,-1,1,-1};
const int yy[8]={0,1,0,-1,-1,1,1,-1};
const int kx[8]={1,1,2,2,-1,-1,-2,-2};
const int ky[8]={2,-2,1,-1,2,-2,1,-1};

/* \( ·w·)~ Clapie ~(·w· )/ */

vector<int> adjlist[100005];
bool vis[100005];
int memo[100005],n,m;

int dp(int idx){
	if(vis[idx]==1) return 0;
	if(memo[idx]!=-1) return memo[idx];
	
	int ret=0;
	for(int i=0;i<adjlist[idx].size();i++){
		ret=max(ret,dp(adjlist[idx][i])+1);
	}
	
	return memo[idx]=ret;
}

int main(){
	mem(memo,-1);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		adjlist[x].pb(y);
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			ans=max(ans,dp(i));
		}
	}
	
	printf("%d\n",ans);
}

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

const int nil = -1;
const int MAX = 26;

struct Node{int parent,left,right;};

Node node_array[MAX];
int height_array[MAX];
int depth_array[MAX];

int set_height(int node_number){
    
    int h1=0,h2=0;
    if(node_array[node_number].left != nil){
        h1 = set_height(node_array[node_number].left) + 1;
    }
    if(node_array[node_number].right != nil){
        h2 = set_height(node_array[node_number].right) + 1;
    }
    int h = max(h1,h2);
    height_array[node_number] = h;
    return h;
}

void set_depth(int node_number,int depth){
    depth_array[node_number] = depth;
    if(node_array[node_number].left != nil){
        set_depth(node_array[node_number].left,depth+1);
    }
    if(node_array[node_number].right != nil){
        set_depth(node_array[node_number].right,depth+1);
    }
}

int get_degree(int node_number){
    int cnt = 0;
    if(node_array[node_number].left != nil) cnt++;
    if(node_array[node_number].right != nil) cnt++;
    return cnt;
}

string get_kind(int node_number){
    if(node_array[node_number].parent == nil){
        return "root";
    }else if(node_array[node_number].left == nil && node_array[node_number].right == nil){
        return "leaf";
    }else{
        return "internal node";
    }
}


int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        node_array[i].parent = node_array[i].left = node_array[i].right = nil;
    }
    
    for(int i=0;i<n;i++){
        int node_number,left,right;
        cin >> node_number >> left >> right;
        node_array[node_number].left = left;
        node_array[node_number].right = right;
        if(left != nil) node_array[left].parent = node_number;
        if(right != nil) node_array[right].parent = node_number;
    }
    int root;
    for(int i=0;i<n;i++){
        if(node_array[i].parent == nil){
            root = i;
        }
    }
    
    set_height(root);
    set_depth(root,0);
    for(int i=0;i<n;i++){
        int sib,deg,parent;
        string kind;
        deg = get_degree(i);
        parent = node_array[i].parent;
        if(parent == nil) sib = nil;
        else{
            if(node_array[parent].left != i) sib = node_array[parent].left;
            else sib = node_array[parent].right;
        }
        kind = get_kind(i);
        printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s",
        i,parent,sib,deg,depth_array[i],height_array[i], kind.c_str());
        cout << endl;
    }
}


Measured memory_bytes: 3304
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N = i()
A = i()
r = N%500
if r <= A:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 10040
#include<iostream>
#include<stdio.h>
#include <algorithm>
#include<string.h>
#include <utility>
using namespace std;
int main(){
int m;
string in1,in2;
int a[1000],b[1000],ans[1000];
int f;
int alen,blen,mlen;
cin>>m;
while(m--){
for(int i=0;i<90;i++){
a[i]=b[i]=ans[i]=0;
}
in1="";
in2="";
cin>>in1;
cin>>in2;
alen=in1.size();
blen=in2.size();
mlen=max(alen,blen);
if(mlen>80){
cout<<"overflow"<<endl;
continue;
}
for(int i=0;i<alen;i++){
a[alen-1-i]=in1[i]-'0';
}
for(int i=0;i<blen;i++){
b[blen-1-i]=in2[i]-'0';
}
f=0;
for(int i=0;i<mlen+1;i++){
ans[i]=(a[i]+b[i]+f)%10;
f=(a[i]+b[i]+f)/10;
}
if(ans[mlen]!=0){
if(mlen>79){
cout<<"overflow"<<endl;
continue;
}
cout<<ans[mlen];
}
for(int i=0;i<mlen;i++){
cout<<ans[mlen-1-i];
}cout<<endl;
}
return 0;
}

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	double a, b, h, m;
	cin >>a >>b >>h >>m;
	
	const double PI = acos(-1);
	double fn = m /60.0 ;
	double jk = (h + m/60.0)/12.0;
	
	double x1 = a*cos(fn * PI *2);
	double y1 = a*sin(fn * PI *2);
	double x2 = b*cos(jk * PI *2);
	double y2 = b*sin(jk * PI *2);
	
	double ans = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
	cout <<setprecision(15) << ans <<"\n";
	return 0;
}


Measured memory_bytes: 4108
#include <iostream>
#include <vector>
using namespace std;
int dp[200005][3];
main()
{
    int n;
    cin >> n;
    for( int i = 0; i < n; i++ )
    {
        vector< int > a(3);
        cin >> a[0] >> a[1] >> a[2];
        for( int j = 0; j < 3; j++ )
        {
            for( int k = 0; k < 3; k++ )
            {
                if( j != k )
                  dp[i + 1][j] = max( dp[i + 1][j], dp[i][k] + a[j] );
            }
        }
    }
    int ans = 0;
    for( int i = 0; i < 3; i++ )ans = max( ans, dp[n][i] );
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int main()
{
    double R, G;
    cin >> R >> G;
    cout << 2 * G - R;
    return 0;
}

Measured memory_bytes: 256
//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

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

  string s;
	cin >> s;
  int n = (int)(s.length());

  FOR(i, 0, ((n-1)/4)-1) {
    if (s[i] != s[((n-3)/2)-i] || s[i] != s[((n+1)/2)+i] || s[i] != s[(n-1)-i]) {
      cout << "No" << "\n";
      return 0;
    }
  }
  if (((n-1)/2)%2 == 1) {
    if (s[(n-3)/4] != s[(3*n-1)/4]) {
      cout << "No" << "\n";
      return 0;
    }
  }

	cout << "Yes" << "\n";
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int K = scanner.nextInt();
    if (N == K) {
      System.out.println(1);
    } else {
      System.out.println(1 + (N - K - 1) / (K - 1) + 1);
    }
  }
}


Measured memory_bytes: 25556
N, M = gets.split.map(&:to_i)

battles = []
M.times do
  battles << gets.split.map(&:to_i)
end

battles.sort_by!{|a, b| b}
last_b = battles[0][1]
count = 1

battles.each do |a, b|
  if a >= last_b
    last_b = b
    count += 1
  end
end

puts count

Measured memory_bytes: 12664
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
using namespace std;
/****************************/
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define qi queue<int>
#define mii map<int,int>
#define msi map<string,int>
#define vs vector<string>
#define vc vector<char>
/****************************/
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define rep3(i,a,n) for(ll i=(a);i<(n);i++)
#define rep4(i,a,n) for(ll i=(n)-1;i>=a;i--)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define pi 3.1415926535897932384626433832795
#define zero(n) memset(n,0,sizeof(n));
#define SZ(n) n.size()
#define mod 1000000007
#define INF 1000000000000000000
/****************************/
int x,y,a,b,c;
int p[100010],q[100010],r[100010];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	cin>>x>>y>>a>>b>>c;
	rep(i,a)
	{
		cin>>p[i];
	}
	rep(i,b)
	{
		cin>>q[i];
	}
	int cnta=a+1,cntb=b+1;
	rep(i,c)
	{
		cin>>r[i];
	}
	sort(p,p+a,cmp);
	sort(q,q+b,cmp);
	sort(r,r+c,cmp);
	int taken=0,ta=0,tb=0;
	ll ans=0;
	rep(i,x)
	{
		ans+=p[i];
	}
	rep(i,y)
	{
		ans+=q[i];
	}
	x--,y--;
	int j=0;
	while(j<c)
	{
		if(x<0&&y<0) break;
		if(x<0&&q[y]>r[j]) break;
		if(y<0&&p[x]>r[j]) break;
		if(p[x]>r[j]&&q[y]>r[j]) break;
		if(x<0)
		{
			ans+=r[j]-q[y];
			y--,j++;
		}
		else if(y<0)
		{
			ans+=r[j]-p[x];
			x--,j++;
		}
		else
		{
			if(r[j]-p[x]>r[j]-q[y])
			{
				ans+=r[j]-p[x];
				x--,j++;
			}
			else
			{
				ans+=r[j]-q[y];
				y--,j++;
			}
		}
	}
	cout<<ans;
	return 0;
}

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

using ll = long long;

int main(){
    vector<ll> v;
    for(int i = 0; i < 3; i++){
        ll tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    cout << v[0] + v[1] << endl;
}

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

int main()
{
	string S;
  cin >> S;
  bool flag = false;
  
  for(int i = 0; i < S.size(); i++){
   if(i%2 == 0){
     if(S.at(i) == 'R' || S.at(i) == 'U' || S.at(i) == 'D'){
       flag = true;
     }	else {
       flag = false;
       break;
     }
   } else{
     if(S.at(i) == 'L' || S.at(i) == 'U' || S.at(i) == 'D'){
       flag = true;
     } else {
       flag = false;
       break;
     }
   }
  }    

  if(flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()


ll n;
vll a;
 
void solve(){
 cin >> n;
 a.resize(n);
 rep(i,0,n) cin >> a[i];
 vll d;
 rep(i,0,n){ 
  auto it=lower_bound(d.rbegin(),d.rend(),a[i]);
  if(it==d.rbegin()){
    d.eb(a[i]);
  }else{
   --it;
   *it=a[i]; 
    
  }
   
 }
  cout << d.size() << endl;
}

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

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

int main(){
   int a,b,c,t;
   cin >> a >> b >> c;
   
   if (a>b){t = a;a = b;b = t;}
   if (b>c){t = b;b = c;c = t;}
   if (a>b){t = a;a = b;b = t;}
   
   cout << a << " " << b << " " << c << endl;
return 0;
}   


Measured memory_bytes: 3080
H, W = map(int, input().split())
S = [input() for _ in range(H)]

# .を0に置き換え
grid = [[0 if cell=="." else "#" for cell in row] for row in S] 

import itertools
for r in range(H):
  for w in range(W):
    if S[r][w] != "#":
      continue
    for dx, dy in itertools.product([-1, 0, 1], repeat=2):
      x = r+dx
      y = w+dy
      if x < 0 or x >= H or y < 0 or y >= W:
        continue
      if S[x][y] == "#":
        continue
      grid[x][y] += 1
for row in grid:
  print(*row, sep="")

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  string S;
  cin>>S;
  for(int i=0;i<S.size()-1;i++){
    if(S[i]=='A'&&S[i+1]=='C'){
      cout<<"Yes"<<endl;
      break;
    }
    if(i==S.size()-2) cout<<"No"<<endl;
  }
}


Measured memory_bytes: 256
object Main{
  def outChars(args:Array[Char]){
    args.foreach(print)
  }

  def main(args:Array[String])={
    val sc = new java.util.Scanner(System.in)
    val H = sc.nextInt
    val W = sc.nextInt
    val table = Array.ofDim[Char](H,W)
    for(i <- 0 to H-1){
      val line = sc.next().toCharArray()
      for(j <- 0 to W-1){
        table(i)(j) = line(j)
      }
    }

    for(i <- 0 to H-1){
      for(j <- 0 to W-1){
        if(table(i)(j) == '#'){
          print(table(i)(j))
        }else{
          var cnt = 0
          for(dx <- -1 to 1){
            for(dy <- -1 to 1){
              val nx = i+dx
              val ny = j+dy
              if(nx>=0 && nx<H && ny>=0 && ny<W && table(nx)(ny)=='#'){
                cnt = cnt+1
              }
            }
          }
          print(cnt)
        }
      }
      println()
    }
  }
}


Measured memory_bytes: 28768
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    ll a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    bool yes = true;
    rep(i, a + b + 1) {
        if (i != a)
            if (!('0' <= s[i] && s[i] <= '9')) yes = false;
        if (s[a] != '-') yes = false;
    }

    if (yes)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(){
  int ans=100000;
  int n;
  int i;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    ans=ans*0.05+ans;
    ans+=999;
    ans/=1000;
    ans*=1000;
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 592
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cstdio>
#include<vector>
#include<iostream>
#include<string>
#include<algorithm> 
using namespace std;
int main(){
	string s,t;
	cin>>s;
	for(int i=s.size()-1;i>=0;i--){
		t+=s[i];
	}
	for(int i=0;i<s.size();i++){
		if(t[i]=='p'){
			t[i]='q';
		}else{
			if(t[i]=='q'){
				t[i]='p';
			}else{
				if(t[i]=='b'){
					t[i]='d';
				}else{
					t[i]='b';
				}
			}
		}
	}
	bool k=1;
	for(int i=0;i<s.size();i++){
		if(t[i]!=s[i]){
			k=0;
		}
	}
	if(k){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 512
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from operator import itemgetter

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
m = map(int, read().split())
bc = list(zip(m,m))

bc.sort(key = itemgetter(1), reverse=True)
bc.append((n,0))
diff = []
for b, c in bc:
    diff += [c] * b
    if len(diff) > n:
        break

a += diff
a.sort()
print(sum(a[-n:]))


Measured memory_bytes: 31520
from string import digits
from itertools import product
S = input() + "$"

def parse(pri):
    code = "+-*"

    cur = 0
    def number():
        nonlocal cur
        c = S[cur]
        if c == '(':
            cur += 1 # '('
            v = expr(0)
            cur += 1 # ')'
            return v
        num = 0
        while S[cur] in digits:
            num = 10*num + int(S[cur])
            cur += 1
        return num
    def expr(level):
        nonlocal cur
        op = '+'
        result = 0
        while 1:
            if level == 2:
                v = number()
            else:
                v = expr(level+1)
            if op == '+':
                result += v
            elif op == '-':
                result -= v
            else:
                result *= v
            c = S[cur]
            if code.find(c) == -1 or pri[code.index(c)] != level:
                break
            op = c
            cur += 1
        return result
    return expr(0)
ans = -10**30
for pri in product(range(3), repeat=3):
    ans = max(ans, parse(pri))
print(ans)

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

int main(){
    int K;
    cin >> K;
    int a,b;
    cin >> a >> b;
    for(int i =a; i <=b; i++){
        if(i%K == 0){
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3604