akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<complex>
#include<queue>
#include<stdlib.h>
#include<map>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
#include<set>

#define ll long long int
#define MOD 1000000007
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair

using namespace std;

int main(){
    int N,X;
    cin >> N >> X;
    vector<int> L(N);
    for(int i=0;i<N;i++){
        cin >> L[i];
    }
    int x=0;
    int cnt=1;
    for(int i=0;i<N;i++){
        x=x+=L[i];
        if(x<=X){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val inf = 10000000
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    val keys = (0 until m).map {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        val c = readLine()!!.split(' ')
                .map { 1 shl (it.toInt() - 1) }
                .reduce { acc, i -> acc or i }
        a to c
    }

    val dp = Array(m + 1) { IntArray(4096) { inf } }
    dp[0][0] = 0

    for (i in 0 until m) {
        for (j in 0 until 4096) {
            dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j])
            val j2 = j or keys[i].second
            dp[i + 1][j2] = Math.min(dp[i + 1][j2], dp[i][j] + keys[i].first)
        }
    }

    dp[m][(1 shl n) - 1].let { println(if (it < inf) it else -1) }
}


Measured memory_bytes: 68724
# -*- coding: utf-8 -*-
import heapq as hq

class Dijkstra:
    def __init__(self, node_size, inf):
        self.node_size = node_size
        self.inf = inf
        self.edges = [[] for _ in range(node_size)]
        self.dist = [inf for _ in range(node_size)]

    def add_edge(self, start, end, cost):
        self.edges[start].append((end, cost))

    def solve(self, init_node):
        self.dist[init_node] = 0
        init_dist = 0
        heap = []
        hq.heapify(heap)
        hq.heappush(heap, (init_node, init_dist))

        while heap:
            cur_node, cur_dist = hq.heappop(heap)
            for next_node, cost in self.edges[cur_node]:
                if cost + cur_dist < self.dist[next_node]:
                    self.dist[next_node] = cost + cur_dist
                    hq.heappush(heap, (next_node, cost + cur_dist))
        return self.dist

V, E, init_node = map(int, input().split())
INF = 10 ** 10

dk = Dijkstra(V, INF)

for _ in range(E):
    s, t, d = map(int, input().split())
    dk.add_edge(s, t, d)

result = dk.solve(init_node)

for res in result:
    if res == INF:
        print("INF")
    else:
        print(res)



Measured memory_bytes: 138196
N,K = gets.split(" ").map { |e| e.to_i }
A = gets.split(" ").map { |e| e.to_i }

min = A.min
a_index = []

for i in 0..N-1 do #minの場所を調べる
  if A[i] == min
    a_index << i
  end
end

count = 0

#まず戻る方に進む
a = a_index[0]/(K-1)
a += 1 if a_index[0] % (K-1) != 0
count += a
a_index[0] = (K-1) * count #どこまで最小化したか
nextmin = 1

#最後をやっちゃう
b = (N-1-a_index[-1])/(K-1)
# print [N-1, a_index[-1], K-1]
b += 1 if (N-1-a_index[-1]) % (K-1) != 0
count += b
a_index[-1] = N - (K-1) * b - 1 #どこまで最小化したか


while nextmin <= a_index.length-1 do
  count += (a_index[nextmin] - a_index[nextmin-1] - 1) /(K-1)
  nextmin += 1
end

# print [a,b]
puts count

Measured memory_bytes: 8084
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0);
 
    int N; cin >> N;
    int cur; cin >> cur; cur--;
    int data[N-1]; for(int i=1;i<N;i++)cin >> data[i-1];
    for(int i=1;i<N;i++) {
        int nxt = data[i-1];
        if (nxt > cur) {
            nxt--;
        }
        if (nxt < cur) {
            cout << "No" << endl;
            return 0;
        }
        cur = nxt;
    }
 
    cout << "Yes" << endl;
 
    return 0;
}

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

int main() {
  ll N;
  cin >> N;
  vector<ll> D(N);
  for(int i=0;i<N;i++)cin >> D[i];
  if(D[0]!=0){cout << 0 << endl; return 0;}
  if(N==1 && D[0]==0){cout << 1 << endl; return 0;}
  sort(D.begin(),D.end());
  ll ans=1;
  ll m=2;
  ll cnt=1;
  ll cnt2=1;
  if(N>1 && D[0]!=0 || D[1]!=1){cout << 0 << endl; return 0;}
  for(int i=2;i<N;i++){
    if(D[i]==0){cout << 0 << endl; return 0;}
    if(D[i]>m){cout << 0 << endl; return 0;}
    if(D[i]==m-1){cnt++;}
    if(D[i]==m){
      ll a=1; m++;
      for(int j=0;j<cnt;j++){a=(a*cnt2)%mod;}
      ans=(ans*a)%mod;
      //cout << cnt << endl;
      cnt2=cnt; cnt=1;
    }
  }
  ll ab=1;
  for(int j=0;j<cnt;j++){ab=(ab*cnt2)%mod;}
  ans=(ans*ab)%mod;
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main()
{
	int n, t, c[1000], x[1000];
	cin >> n >> t;
	for (int i = 0; i < n; i++) cin >> c[i] >> x[i];
	int ans = 10000;
	for (int i = 0; i < n; i++) {
		if (x[i] <= t && c[i] < ans) ans = c[i];
	}
	if (ans == 10000) cout << "TLE";
	else cout << ans;
}

Measured memory_bytes: 256
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

cost = []
value = []
for i in range(n):
    if v[i] / c[i] > 1:
        cost.append(c[i])
        value.append(v[i])

print(sum(value) - sum(cost))


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i, n) for (lint i = 0; i < (n); i++)
#define INF LLONG_MAX
#define all(x) (x).begin(), (x).end()
#define pb push_back
int main()
{

    int x, n;
    cin >> x >> n;
    set<int> p;
    rep(i, n)
    {
        int a;
        cin >> a;
        p.insert(a);
    }
    int i = 0;
    while (1)
    {
        if (p.find(x - i) == p.end())
        {
            cout << x - i << endl;
            break;
        }
        else if (p.find(x + i) == p.end())
        {
            cout << x + i << endl;
            break;
        }
        else
            i++;
    }

    return 0;
}


Measured memory_bytes: 3564
#define _GLIBCXX_DEBUG
typedef long long ll;
#include <bits/stdc++.h>

using namespace std;

ll mod = 1000000007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll modpow(ll a, ll n, ll mod)
{
	ll res = 1;
	while (0 < n)
	{
		if (n & 1)
		{
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	map<string, int> mp;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		mp[s]++;
	}

	ll ans = 0;
	for (auto item : mp)
	{
		ll s = item.second;
		ans += s * (s - 1) / 2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 11136
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, A, B, C = [int(x) for x in input().split()]
    S = [input().strip() for _ in range(N)]
    c = collections.Counter(S)


    ans = []
    for i in range(N):
        if S[i] == "AB":
            if A == B == 0:
                print("No")
                return
            elif A == B and i != N - 1:
                if S[i + 1] == "BC":
                    A -= 1
                    B += 1
                    ans.append("B")
                else:
                    A += 1
                    B -= 1
                    ans.append("A")
            elif A > B:
                A -= 1
                B += 1
                ans.append("B")
            else:
                A += 1
                B -= 1
                ans.append("A")
        elif S[i] == "AC":
            if A == C == 0:
                print("No")
                return
            elif A == C and i != N - 1:
                if S[i + 1] == "BC":
                    A -= 1
                    C += 1
                    ans.append("C")
                else:
                    A += 1
                    C -= 1
                    ans.append("A")
            elif A > C:
                A -= 1
                C += 1
                ans.append("C")
            else:
                A += 1
                C -= 1
                ans.append("A")
        else:
            if B == C == 0:
                print("No")
                return
            elif B == C and i != N - 1:
                if S[i + 1] == "AC":
                    B -= 1
                    C += 1
                    ans.append("C")
                else:
                    B += 1
                    C -= 1
                    ans.append("B")
            elif B > C:
                B -= 1
                C += 1
                ans.append("C")
            else:
                B += 1
                C -= 1
                ans.append("B")

    print("Yes")
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


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

int main() {
    string S;
    cin >> S;

    string ACGT("ACGT");
    int count = 0;
    int max_count = 0;

    for (int i = 0; i < S.size(); i++) {
        bool is_matched = false;
        for (int j = 0; j < ACGT.size(); j++) {
            if (S.at(i) == ACGT.at(j)) {
                count++;
                is_matched = true;
                break;
            }
        }

        if (!is_matched) {
            if (count > max_count) {
                max_count = count;
            }
            count = 0;
        }
    }

    if (count > max_count) {
        max_count = count;
    }

    cout << max_count << endl;
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#undef DEBUG
int32_t H,W,N;
int map[1000][1000];//h,W
int num[1100][1100]={};//h,W
int main()
{
	for(;;){
		
	scanf("%d%d%d", &H,&W,&N);
	if(H==0&&W==0&&N==0){break;}
	//getchar();//\n????????????
	for(int32_t i = 0;i < H;++i){
	for(int32_t j = 0;j < W;++j){
		scanf("%d", &map[i][j]);//map[i][j] -= '0';getchar();//\n\s????????????
	}}
		#ifdef DEBUG
		printf("\n----\n");
	for(int32_t i = 0;i < H;++i){
	for(int32_t j = 0;j < W;++j){
		putchar(map[i][j] +'0');
	}putchar('\n');}printf("----\n");
		#endif
	//?????£????????°
	for(auto& arr:num)for(auto& i:arr){i = 0;}
	num[0][0] = N;
	for(int32_t i = 0;i < H;++i){
	for(int32_t j = 0;j < W;++j){
		num[i+1][j] += num[i][j]>>1;
		num[i][j+1] += num[i][j]>>1;
		if(num[i][j]&1){
			if(map[i][j]){
				++num[i][j+1];
			}
			else{
				++num[i+1][j];
			}
		}
	}}
	int32_t npos_x=0,npos_y = 0;
	while(npos_x < W && npos_y < H)
	{
		#ifdef DEBUG
		printf("----\n");
		printf("%d %d %d\n", npos_x,npos_y, now_n);
		printf("%d %d %d\n", (now_n&1), map[npos_y][npos_x], (now_n&1) ^ (map[npos_y][npos_x]));
		printf("----\n");
		#endif
		if((num[npos_y][npos_x]&1) ^ map[npos_y][npos_x]){
			++npos_y;
		}
		else{
			++npos_x;
		}
	}
	printf("%d %d\n",npos_y+1, npos_x+1);
	
	}//for(;;)
}

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

int main(int argc, char const *argv[])
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int ans = 0;
    for(int pin = 0; pin <= 999; pin++) {
        int d = 100;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] - '0' ==  (pin % (d * 10) - pin % d) / d) {
                d /= 10;
                if(d == 0) {
                    ans++;
                    break;
                }
                continue;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()


using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;

//最大公約数
ll gcd(ll a, ll b){
    if(a % b == 0)return b;
    else return gcd(b, a % b);
}

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

    if(4 * a * b < (c - a - b) * (c - a - b))cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define int long long

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(a * a, N / 2);
	}
	else{
		return a * power(a, N - 1);
	}
}

signed main(){
	int N, i, j, f = 0, inf, sup, v;
	scanf("%lld", &N);
	if(N == 0){
		printf("0\n");
		return 0;
	}
	for(i = 32; i >= 0; i--){
		v = power(i % 2 == 0 ? 2 : -2, i);
		sup = v;
		inf = v;
		for(j = i - 1; j >= 0; j--){
			if(j % 2 == 0){
				sup += power(2, j);
			}
			else{
				inf += power(-2, j);
			}
		}
		if(inf <= N && N <= sup){
			printf("1");
			N -= v;
			f = 1;
		}
		else{
			if(f == 1){
				printf("0");
			}
		}
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int, p: "List[int]"):
    ng_check = [0]*N

    for i in range(N):
        if i+1 == p[i]:
            ng_check[i] = 1
    
    answer = 0
    from itertools import groupby
    group = groupby(ng_check)
    for key,gr in group:
        if key == 0:
            continue

        answer += ceil(len(list(gr))/2)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, p)

if __name__ == '__main__':
    main()


Measured memory_bytes: 15988
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii  = pair<int,int>;
const int INF=1001001001;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define MOD 1000000007
#define EPS 10e-8
int gcd(int a,int b){return b?gcd(b,a%b):a;}    //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数

int main(){
    int n;
    cin >> n;
    float a[n];
    float cnt = 0.0;
    rep(i, n)
    {
        cin >> a[i];
        cnt+=a[i];
    }
    cnt = round(cnt / n);
    ll ans = 0;
    rep(i,n){
        ans += pow(a[i]-cnt,2.0);
    }
    cout << ans << endl;
}

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

#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define fill(a,v)  memset(a, v, sizeof (a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N=501000;
const int MOD = 1e9 + 7 ;
const int INF = INT_MAX;
const ll LINF = LLONG_MAX;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

int main()
{
	faster;

    int a, b;

    cin >> a >> b;
    cout << max(a-2*b,0);

	return 0;
}

// READ
// THINK
// CODE 
// DEBUG 
// AC	

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int f(int x, vector<bool> &broken, vector<int> &memo) {
    if(x==0) return 1;
    if(x==1) return (broken.at(1) ? 0 : 1);
    int ans = 0;
    if(!broken.at(x-1)) {
        if(memo.at(x-1) == -1) {
            memo.at(x-1) = f(x-1, broken, memo) % 1000000007;
            ans += memo.at(x-1);
        }
        else ans += memo.at(x-1);
    }
    if(!broken.at(x-2)) {
        if(memo.at(x-2) == -1) {
            memo.at(x-2) = f(x-2, broken, memo) % 1000000007;
            ans += memo.at(x-2);
        }
        else ans += memo.at(x-2);
    }
    return ans % 1000000007;
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<bool> broken(N+1);
    for(int i = 0; i < M; i++) {
        int a; cin >> a;
        broken.at(a) = true;
    }
    
    vector<int> memo(N+10, -1);
    cout << f(N, broken, memo) << endl;
}

Measured memory_bytes: 6912
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif


using namespace std;

// #define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

signed main() {
    Fast();

    int a, b;
    cin >> a >> b;
    cout << (int)ceil((a + b) / 2.0) << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)

bool check(int a, int b) {
	return a > b;
}

int main() {
	int n;
	cin >> n;
	vector<llint>a(n);
	vector<llint>b(n);
	rep(i, n) {
		cin >> a[i] >> b[i];
	}
	llint ans = 0;
	rep(i, n) {
		ans += (b[n - 1 - i] - (a[n - 1 - i] + ans) % b[n - 1 - i]) % b[n - 1 - i];
	}
	cout << ans << endl;
	return 0;
}


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



 
int main(){
 int A,B,C,K;
 cin>>A>>B>>C>>K;
 string ans;

 for(int i=0;i<K;i++){
	 if(A>B&&B>C){C*=2;continue;}
	 if(A>C&&C>B){C*=2;continue;}
	 if(B>A&&A>C){C*=2;continue;}
	 if(B>C&&C>A){C*=2;continue;}
	 if(C>A&&A>B){B*=2;continue;}
	 if(A>B&&B==C){C*=2;continue;}
	 if(B>A&&A==C){C*=2;continue;}
	 if(C>A&&A==B){B*=2;continue;}
	 if(A==B&&A>C){C*=2;continue;}
	 if(A==C&&A>B){B*=2;continue;}
	 if(C==B&&B>A){C*=2;continue;}
	 if(A==B&&B==C){C*=2;continue;}
 	}
  if(C>B&&B>A){ans="Yes";}
  else{ans="No";}
  cout<<ans<<endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n,k;
    cin >> n >> k;
    int p[n];
    REP(i,n) cin >> p[i];
    int sumf=0,suml=0,maxs=0;
    REP(i,n){
        sumf+=p[i];
        if(i>=k){
            suml+=p[i-k];
            chmax(maxs,sumf-suml);
        }
    }
    if(n==k) maxs=sumf;
    double ans=(double)k/2 + (double)maxs/2;
    printf("%.7f\n",ans);

    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;
using li = __int128;
using uli = unsigned __int128;

#define fi first
#define se second

template <typename T> void s_min(T& a, T b) {
	if (a > b) a = b;
}

template <typename T> void s_max(T& a, T b) {
	if (a < b) a = b;
}

const int mod = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(0);

	int H, W;
	cin >> H >> W;
	vector<vector<char>> grid(H, vector<char> (W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) cin >> grid[i][j];
	}
	vector<vector<ll>> dp(H, vector<ll> (W, 0));
	dp[0][0] = 1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i == 0 && j == 0) continue;
			if (grid[i][j] == '#') continue;
			if (i - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
			if (j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
		}
	}
	cout << dp[H - 1][W - 1];

	return 0;
}

Measured memory_bytes: 12184
//author: Harsh :)
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll INF = 922337203685477;
#define pb push_back
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define maxN 100007
using namespace std;
int main(){
  fastio;
  ll a=0,b=0,c=0,k=0;
  cin>>a>>b>>c>>k;
  if(a>=k) cout<<k;
  else if(a+b>=k) cout<<a;
  else
    cout<<a-(k-(a+b));

  return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
constexpr int gcd(int a,int b){return b?gcd(b,a%b):a;}
constexpr int lcm(int a,int b){return a*b/gcd(a,b);}

int main(){
    int w,h;
    while(cin>>w>>h,w){
        cin.ignore();
        vvi v(h*2+1,vi(w*2+1,1));
        rep(i,h*2-1){
            string s;
            getline(cin,s);
            replace(all(s),' ','0');
            if(i%2==0)s+="0";
            s="1"+s+"1";
            rep(j,w*2+1){
                v[i+1][j]=(s[j]=='1')?1:0;
            }
        }
        for(int i=1;i<v.size()-1;i+=2)
            for(int j=2;j<v[0].size()-1;j+=2)
                    if(v[i][j] && i<v.size()-3 && v[i+2][j]) v[i+1][j]=1;
        for(int i=2;i<v.size()-1;i+=2)
            for(int j=1;j<v[0].size()-1;j+=2)
                if(v[i][j] && j<v[0].size()-3 && v[i][j+2]) v[i][j+1]=1;
        //for(auto l:v){for(auto i:l)cout<<(i?"#":" ");cout<<endl;}
        v[1][1]=1;
        queue<pii> spot;
        spot.emplace(1,1);
        while(!spot.empty()){
            vi vec={1,0,-1,0,1};
            auto c=spot.front();
            spot.pop();
            rep(i,4){
                if(v[c.fs+vec[i]][c.sc+vec[i+1]]==0 && v[c.fs+vec[i]*2][c.sc+vec[i+1]*2]==0){
                    v[c.fs+vec[i]*2][c.sc+vec[i+1]*2] = v[c.fs][c.sc]+1;
                    spot.emplace(c.fs+vec[i]*2, c.sc+vec[i+1]*2);
                }
            }
        }
        //for(auto l:v){for(auto i:l)if(i==1)cout<<"###";else cout<<setw(3)<<i;cout<<endl;}
        cout<<v[h*2-1][w*2-1]<<endl;
    }
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

int pow(int x, int n){
  if(n == 0)return 1;
  if(n % 2 == 0)return pow(x * x % MOD, n/2);
  else return x * pow(x, n-1) % MOD;
}

signed main(){
  int a,b;cin>>a>>b;
  if(a>b)swap(a,b);
  if(a==b){
    cout << 0 << endl;
  }else if((a+b)%2 == 0) {
    cout << (a+b)/2 << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n, k) for (int i = n; i < k; i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define vi vector<int>
#define printv(v)                      \
    for (int i = 0; i < v.size(); i++) \
        P(v[i]);
#define printt(a, b) cout << a << " " << b << endl;
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int MOD = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    vi v;
    rep(i, n)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    int mini = 1e9;
    rep(i, 101)
    {
        int sum = 0;
        rep(j, n)
        {
            sum += pow((v[j] - i), 2);
        }
        mini = min(sum, mini);
    }
    P(mini);
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		if(n<105){
			System.out.println(0);
		}else if(n<135){
			System.out.println(1);
		}else if(n<165){
			System.out.println(2);
		}else if(n<189){
			System.out.println(3);
		}else if(n<195){
			System.out.println(4);
		}else{
			System.out.println(5);
		}	
	}
}

Measured memory_bytes: 23764
use std::collections::{BinaryHeap, HashMap};

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn solve(v: Vec<(usize, usize)>) {
    let mut map = {
        let mut m = HashMap::new();
        for &(k, v) in v.iter() {
            if !m.contains_key(&k) {
                let mut b = BinaryHeap::new();
                b.push(v);
                m.insert(k, b);
            } else {
                m.get_mut(&k).unwrap().push(v);
            }
        }
        m
    };
    let n = map.clone();
    let townpage = {
        let mut ret = HashMap::new(); // <(usize, usize), String>
        for (k,_) in n.iter() {
            let v = map.get_mut(k).unwrap();
            let mut c = v.len();
            loop {
                if let Some(n) = v.pop() {
                    ret.insert((k, n), format!("{:06}{:06}", k, c));
                    c -= 1;
                } else {
                    break;
                }
            }
        }
        ret
    };
    for &(x, y) in v.iter() {
        println!("{}", townpage.get(&(&x, y)).unwrap());
    }
}

fn main() {
    input! {
        _n: usize,
        m: usize,
        pys: [(usize, usize); m]
    };
    solve(pys);
}


Measured memory_bytes: 34300
#include <iostream>
#include <string>
#include <functional>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 200000;

using i64 = long long;

int n, m;
i64 v[N];

struct Edge {
    int x, y;
    i64 v;
    void read() {
        scanf("%d%d%lld", &x, &y, &v);
    }
    int operator<(const Edge &o) const {
        return v < o.v;
    }
} e[N];

int f[N], inv[N];
i64 totv[N];

int getf(int x) {
    if (f[x] == x) return x;
    int tmp = getf(f[x]);
    return f[x] = tmp;
}

void log() {
    for (int i = 1; i <= n; i++) {
        printf("[i = %d] fa = %d, totv = %lld, inv = %d\n", i, f[i], totv[i], inv[i]);
    }
    cout << "=========\n";
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%lld", v + i);
    for (int i = 0; i < m; i++) e[i].read();
    sort(e, e + m);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        totv[i] = v[i];
        inv[i] = 0;
    }
    // log();
    for (int i = 0; i < m; i++) {
        int a = getf(e[i].x), b = getf(e[i].y);
        if (a == b) {
            if (e[i].v > totv[a]) inv[a]++;
            continue;
        }
        f[a] = b;
        totv[b] += totv[a];
        if (totv[b] >= e[i].v) {
            inv[b] = 0;
        } else {
            inv[b] += inv[a] + 1;
        }
        // log();
    }
    cout << inv[getf(1)] << endl;
    return 0;
}

Measured memory_bytes: 6656
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
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
#from decimal import *
 
S = input()
w = INT()
ans = ""
for i in range(0, len(S), w):
	ans += S[i]

print(ans)



Measured memory_bytes: 5200
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
from heapq import heappush, heappop

x, y, z = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(x+y+z)]
c.sort(key=lambda x: x[1]-x[0])

ans_l = [-1 for _ in range(x+y+z)]
ans_r = [-1 for _ in range(x+y+z)]

tmp = 0
l = []
for i in range(x):
	tmp += c[i][0]
	heappush(l, (c[i][0] - c[i][2], i))
ans_l[x] = tmp

for i in range(x, x+z):
	tmp += c[i][0]
	heappush(l, (c[i][0] - c[i][2], i))
	p = heappop(l)
	tmp -= c[p[1]][0]
	tmp += c[p[1]][2]
	ans_l[i+1] = tmp

tmp = 0
r = []
for i in range(x+z, x+y+z):
	tmp += c[i][1]
	heappush(r, (c[i][1] - c[i][2], i))
ans_r[x+z] = tmp

for i in range(x+z-1, x-1, -1):
	tmp += c[i][1]
	heappush(r, (c[i][1] - c[i][2], i))
	p = heappop(r)
	tmp -= c[p[1]][1]
	tmp += c[p[1]][2]
	ans_r[i] = tmp

ans = 0
for i in range(x, x+z+1):
	ans = max(ans, ans_l[i] + ans_r[i])

print(ans)

Measured memory_bytes: 79836
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int main() {

	std::cin.tie(nullptr); std::ios::sync_with_stdio(false);

	int X, A, B; cin >> X >> A >> B;

	if (B <= A) {
		cout << "delicious";
	}
	else if (B - A <= X) {
		cout << "safe";
	}
	else {
		cout << "dangerous";
	}

	return 0;

}

Measured memory_bytes: 256
def dfs(dg, gs, ms, used, v):
    if used[v]:
        return dg[gs[v]]
    used[v] = 1
    me = ms[v]
    for i in xrange(len(me)):
        if me[i] in dg:
            ret = dfs(dg, gs, ms, used, gs.index(me[i]))
            for e in ret:
                if e not in dg[gs[v]]:
                    dg[gs[v]].append(e)
        else:
            if me[i] not in dg[gs[v]]:
                dg[gs[v]].append(me[i])
    return dg[gs[v]]

while 1:
    n = input()
    if not n:
        break
    gs = []; ms = []
    dg = {}
    for i in xrange(n):
        g, m = raw_input().split(":")
        gs.append(g); ms.append(m[:-1].split(","))
        dg[g] = []

    dfs(dg, gs, ms, [0]*n, 0)
    print len(dg[gs[0]])

Measured memory_bytes: 4384
N = int(input())
A = list(map(int, input().split()))

mini = A[0]
ans = 0

for i in range(len(A) - 1):
    if A[i] > A[i+1]:
        ans += A[i] - A[i+1]
        A[i+1] = A[i]
print(ans)

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

const int N = 1e6+1;
vector<int> spf(N+5, -1);

unordered_map<int,int> get_factors(int x){
	unordered_map<int,int> mp;
	while(x>1){
		mp[spf[x]]++;
		x /= spf[x];
	}
	return mp;
}

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

	for(int i=2;i<N;i++){
		if(spf[i] != -1) continue;
		for(int j=i;j<N;j+=i){
			if(spf[j]==-1) spf[j] = i;
		}
	}

	long long ans = 0;
	while(--n){
		unordered_map<int,int> f = get_factors(n);
		long long temp = 1;
		for(auto x : f){
			temp *= (1+x.second);
		}
		ans += temp;
	}	

	cout << ans << endl;

	return 0;
}

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

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;

int main()
{
	scanf("%d", &N);
	for (int i = 1; ; ++i) {
		int m = i * (i + 1) / 2;
		if (m >= N) {
			for (int j = i; j >= 1; --j) {
				if (j <= N) {
					printf("%d\n", j);
					N -= j;
				}
			}
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

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

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int C = sc.nextInt();

        int[] B = new int[M];
        for(int m=0; m<M; m++) B[m]=sc.nextInt();

        int ans = 0;
        for(int n=0; n<N; n++){
            int[] A = new int[M];
            for(int m=0; m<M; m++) A[m]=sc.nextInt();

            int codeQuality = C;
            for(int m=0; m<M; m++) codeQuality += A[m]*B[m];
            if(codeQuality>0) ans++;
        }
        System.out.println(ans);



    }
}

Measured memory_bytes: 22228
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace ABC177
{
    using static Ex;
    public class Solve
    {
        public static void Main(string[] args)
        {
            new ABC_A();
        }
    }
    public class ABC_A
    {
        public ABC_A()
        {
            var (d, t, s) = ReadLongArray().ToTpl3();
            var b = (s * t >= d);
            b.YesNo();
        }
    }
    public class ABC_B
    {
        public ABC_B()
        {
        }
    }
    public class ABC_C
    {
        public ABC_C()
        {
        }
    }

    public static class Ex
    {
        public static void Cw(this object s) { Console.WriteLine(s); }



        public static bool Mins<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) > 0) { a = b; return true; } return false; }
        public static bool Maxs<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
        public static void Swap<T>(ref T a, ref T b) { var t = b; b = a; a = t; }
        public static void Swap<T>(List<T> list, int i, int j) { T tmp = list[j]; list[j] = list[i]; list[i] = tmp; }

        public static long Lcm(int x, int y) { return x / Gcd(x, y) * y; }
        public static long Gcd(long m, long n) { if (n == 0) return m; return Gcd(n, m % n); }
        public static List<string> FastSort(this List<string> s) { s.Sort(StringComparer.Ordinal); return s.ToList(); }
        public static void yesno(this bool b) { (b ? "yes" : "no").Cw(); }
        public static void YesNo(this bool b) { (b ? "Yes" : "No").Cw(); }
        public static void YESNO(this bool b) { (b ? "YES" : "NO").Cw(); }

        public static string Read { get { return Console.ReadLine().Trim(); } }
        public static int ReadInt { get { return int.Parse(Read); } }
        public static long ReadLong { get { return long.Parse(Read); } }
        public static double ReadDouble { get { return double.Parse(Read); } }
        public static string[] ReadArray() { return Read.Split(' '); }
        public static int[] ReadIntArray() { return Read.Split(' ').Select(int.Parse).ToArray(); }
        public static long[] ReadLongArray() { return Read.Split(' ').Select(long.Parse).ToArray(); }
        public static string[] ReadArray(long N) { var v = new string[N]; for (long i = 0; i < N; ++i) v[i] = Read; return v; }
        public static int[] ReadIntArray(long N) { var v = new int[N]; for (long i = 0; i < N; ++i) v[i] = ReadInt; return v; }
        public static long[] ReadLongArray(long N) { var v = new long[N]; for (long i = 0; i < N; ++i) v[i] = ReadLong; return v; }

        public static (T, T) ToTpl2<T>(this T[] v) { return (v[0], v[1]); }
        public static (T, T, T) ToTpl3<T>(this T[] v) { return (v[0], v[1], v[2]); }
        public static (T, T, T, T) ToTpl4<T>(this T[] v) { return (v[0], v[1], v[2], v[3]); }
        public static (T, T, T, T, T) ToTpl5<T>(this T[] v) { return (v[0], v[1], v[2], v[3], v[4]); }
    }
}


Measured memory_bytes: 28192
x,k,d = map(int,input().split())
x = abs(x)
if x>=k*d:
    print(x-k*d)
else:
    temp = x//d
    if temp%2==k%2:
        min_ = temp
        max_ = temp+2
    else:
        min_ = temp-1
        max_ = temp+1
    if max_ > k:
        max_ = min_
    #print(min_,max_)
    ans = min(abs(x-d*min_),abs(x-d*max_))
    print(ans)

Measured memory_bytes: 9200
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(N)]
cd = [LIST() for _ in range(M)]

def dist(p1, p2):
	return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

for p1 in ab:
	tmp_dist = INF
	tmp_idx = None
	for i, p2 in enumerate(cd):
		d = dist(p1, p2)
		if d < tmp_dist:
			tmp_dist = d
			tmp_idx = i+1
	print(tmp_idx)


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

int main() {
  long long N;
  cin >> N;
  string ans;
  while(N>0){
    N--;
    ans += (N%26)+'a';
    N/=26;
  }
  reverse(ans.begin(),ans.end());
  cout << ans << endl;
}


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

int main(){
  long long int N ,ans = 0 , K;
  cin >> N >> K ;
  vector<int> h(N);
  for(long long int i = 0; i < N; i++) cin >> h[i];
  for(long long int i = 0; i < N; i++)
    if(h[i] >= K) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 3768
#include <stdio.h>

int main(void)
{
	int a, b, count;

	scanf("%d%d", &a, &b);
	count = b - a + 1;

	if ((a > 0 && b > 0) || (a < 0 && b < 0 && count % 2 == 0))
		printf("Positive\n");
	else if (a < 0 && b < 0 && count % 2 == 1)
		printf("Negative\n");
	else
		printf("Zero\n");

	return 0;
}

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

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

      int n,m;
      cin>>n>>m;
      int c[m+1]={0};
      for(int i=0;i<n;i++)
      {
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
          int x;
          cin>>x;
          c[x]++;
        }
      }
      int ans=0;
      for(int i=1;i<=m;i++) ans+=(c[i]==n);
        cout<<ans;
}
/* If today were the last day of my life,would I want to do what I'm about to do today? */

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    
    vector<int>B(1001000,1);
    int A[N];
    
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    
    sort(A,A+N);
    for(int i=0;i<N;i++){
        if(i !=0 && A[i]==A[i-1]){
            B[A[i]]=0;
            continue;
        }
        if(B[A[i]]==0) continue;
        for(int j=2;j*A[i]<1000010;j++){
            B[j*A[i]]=0;
        }
    }
    int cnt=0;
    for(int i=0;i<N;i++){
        if(B[A[i]]==1) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}



Measured memory_bytes: 7948
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

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

int const INF = 100000000;
vector<vector<vector<int>>> dijkstra(vector<vector<int>> &field, vector<int> c, int H, int W) {
    // d[y座標][x座標][方向]
    vector<vector<vector<int>>> d(H+2, vector<vector<int>>(W+2, vector<int>(4, INF)));

    int dx[] = {0, 1, 0, -1};
    int dy[] = {-1, 0, 1, 0};
    d[1][1][1] = 0;
    priority_queue<pair<int, pair<int, pair<int, int>>>, vector<pair<int, pair<int, pair<int, int>>>>, greater<pair<int, pair<int, pair<int, int>>>>> que;
    que.push({0, {1, {1, 1}}});

    while (!que.empty()) {
        pair<int, pair<int, pair<int, int>>> p = que.top();
        que.pop();
        int dir = p.second.second.second;
        int y = p.second.first;
        int x = p.second.second.first;
        int dist = p.first;
        if (dist > d[y][x][dir]) continue;
        for (int i = 0; i < 4; i++) {
            int cost = c[i];
            if (field[y][x] == i) cost = 0;
            int changedDir = (dir + i)%4;
            int ny = y + dy[changedDir];
            int nx = x + dx[changedDir];
            if (field[ny][nx] == -1) continue;
            if (d[ny][nx][changedDir] > dist + cost) {
                int nextCost = dist + cost;
                d[ny][nx][changedDir] = nextCost;
                que.push({nextCost, {ny, {nx, changedDir}}});
            }
        }
    }
    return d;
}

int solve(int H, int W) {
    vector<vector<int>> field(H+2, vector<int>(W+2, -1));
    for (int y = 1; y <= H; y++) {
        for (int x = 1; x <= W; x++) {
            cin >> field[y][x];
        }
    }
    vector<int> cost(4);
    for (int i = 0; i < 4; i++) {
        cin >> cost[i];
    }

    vector<vector<vector<int>>> d = dijkstra(field, cost, H, W);
    int ret = INF;
    for (int i = 0; i < 4; i++) {
        ret = min(d[H][W][i], ret);
    }
    return ret;
}

int main(void) {
    int W, H;
    vector<int> ans;
    while (1) {
        cin >> W >> H;
        if (!W && !H) break;
        ans.push_back(solve(H, W));
    }
    for (auto &i: ans) {
        cout << i << endl;
    }
}


Measured memory_bytes: 3264
#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 9132
object Main extends App {
  val n = io.StdIn.readLine().toInt
  val numbers = Array.fill(20000)(true)
  for ( i <- 2 until numbers.length/2 )
    numbers(2*i) = false
  for ( i <- 3 until numbers.length )
    for ( l <- 3 until numbers.length by 2; if i*l < numbers.length )
      numbers(i*l) = false
  val primes = (0 to numbers.length).zip(numbers).filter(_._2).map(_._1).drop(2).filter(_ % 5 == 1)
  for ( i <- primes.take(n) ) print(i.toString ++ " ")
  println("")
}

Measured memory_bytes: 112812
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N, i;
  int sum = 0;
  cin >> N;
  int cnt; 
  cnt = N;

  while(cnt > 0){
    sum += cnt % 10;
    cnt /= 10;
  }

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

Measured memory_bytes: 256
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = (int(i) - 1 for i in input().split())
C = [input() for _ in range(H)]

ans = [[-1] * W for _ in range(H)]
ans[x1][y1] = 0

Q = deque([(x1, y1)])
while Q:
    x, y = Q.popleft()
    if (x, y) == (x2, y2):
        print(ans[x][y])
        quit()

    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for a in range(1, K + 1):
            nx = x + a * di
            ny = y + a * dj

            if not (0 <= nx < H and 0 <= ny < W) or C[nx][ny] == "@" or 0 <= ans[nx][ny] <= ans[x][y]:
                break

            if ans[nx][ny] == -1:
                Q.append((nx, ny))

            ans[nx][ny] = 1 + ans[x][y]

print(-1)

Measured memory_bytes: 36780
N, K = map(int, input().split())
L = (N-1)*(N-2)//2

if K > L:
    print(-1)
else:
    Ms = []
    for i in range(2, N+1):
        Ms.append((1, i))
    c = L
    for i in range(2, N):
        if c <= K:
            break
        for j in range(i+1, N+1):
            Ms.append((i, j))
            c -= 1
            if c <= K:
                break

    print(len(Ms))
    for u, v in Ms:
        print(u, v)

Measured memory_bytes: 3992
#include <iostream>

int main(int argc, char const *argv[])
{
    int a = 0;
    int b = 0;
    int c = 0;

    std::cin >> a >> b >> c;

    if (a < b && b < c) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

Measured memory_bytes: 3092
L, R = map(int, input().split())
mod = 2019
s = 2018
for i in range(L, min(R, L+2018)):
    for j in range(i+1, min(R+1, L+2019)):
        t = (i%mod)*(j%mod)%mod
        if s > t:
            s = t
print (s)

Measured memory_bytes: 3060