akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())
dicts = {key: [False,0] for key in range(1, n+1)}
for i in range(m):
    p, s = input().split()
    p = int(p)
    if s == "AC":
        dicts[p][0] = True
        continue
    else:
        if dicts[p][0]==True:
            continue
        else:
            dicts[p][1] += 1
ans_list = [v[1] for k, v in dicts.items() if v[0]==True]
ans_n = len(ans_list)
penal = sum(ans_list)
print(ans_n,penal)

Measured memory_bytes: 23204
#include <stdio.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

int rot[24][7] = {
	{ 0,1,2,3,4,5,6 },{ 0,1,3,5,2,4,6 },{ 0,1,4,2,5,3,6 },{ 0,1,5,4,3,2,6 },
	{ 0,2,6,3,4,1,5 },{ 0,2,3,1,6,4,5 },{ 0,2,1,4,3,6,5 },{ 0,2,4,6,1,3,5 },
	{ 0,3,1,2,5,6,4 },{ 0,3,2,6,1,5,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
	{ 0,4,1,5,2,6,3 },{ 0,4,2,1,6,5,3 },{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },
	{ 0,5,1,3,4,6,2 },{ 0,5,3,6,1,4,2 },{ 0,5,4,1,6,3,2 },{ 0,5,6,4,3,1,2 },
	{ 0,6,2,4,3,5,1 },{ 0,6,3,2,5,4,1 },{ 0,6,5,3,4,2,1 },{ 0,6,4,5,2,3,1 } };

int  a[102][7];
char f[102];

int identical(int *a, int *b)
{
	int i, j;
	memset(f, 0, sizeof(f));
	for (i = 1; i <= 6; i++) f[a[i]]++;
	for (i = 1; i <= 6; i++) f[b[i]]--;
	for (i = 1; i <= 6; i++) if (f[b[i]]) return 0;

	for (j = 0; j < 24; j++) {
		if (b[1] == a[rot[j][1]]) {
			for (i = 2; ; i++) {
				if (i > 6) return 1;
				if (b[i] != a[rot[j][i]]) break;
			}
		}
	}
	return 0;
}

int main()
{
	int n, i, j, f;

	n = in();
	for (i = 0; i < n; i++) {
		for (j = 1; j <= 6; j++) a[i][j] = in();
	}
	f = 1;
	for (i = 0; i < n; i++) for (j = i+1; j < n; j++) {
		if (identical(a[i], a[j])) { f = 0; goto done; }
	}
done:
	puts(f? "Yes": "No");
	return 0;
}



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

int main() {

    int K, S;
    cin >> K >> S;

    int cnt = 0;

    for (int x = 0; x <= K; ++x) {
        for (int y = 0; y <= K; ++y) {
            int z = S -x - y;
            if (z>=0 and z<=K) cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3652
p=[1 for i in range(1000001)]
p[0]=0
p[1]=0
for i in range(2,500000):
    for j in range(2,1000000//i+1):
        p[i*j]=0

while True:
    n=int(input())
    if n==0:
        break
    s=0
    for i in range(1,n//2+1):
        if p[i]==1 and p[n-i]==1:
            s+=1
    print(s)


Measured memory_bytes: 13512
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        int T = Integer.parseInt(sc.next());
        System.out.println(T / A * B);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
template<class T>

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

vvi adl_input(int N,int M){ //N頂点M辺
  vvi L(N);
  rep(i,M){
    int a,b;
    cin >> a >> b;
    //a--;b--;
    L[a].push_back(b);
    L[b].push_back(a);
  }
  return L;
}

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);
}

vector<int> bfs(vvi L,int S){ //List,Start
  vector<int> v(L.size(),-1);
  v[S]=0;
  queue<int> q;
  q.push(S);
  while(!q.empty()){
    int a=q.front();
    q.pop();
    for(int x:L[a]){
      if (v[x]==-1){
        v[x]=v[a]+1;
        q.push(x);
      }
    }
  }
  return v;//startからの距離
}

void initialize(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout << fixed << setprecision(15);
}

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

int main(){
  initialize();
  int D,G;
  cin >> D >> G;
  int p[D];
  int c[D];
  rep(i,D) cin >> p[i] >> c[i];
  int ans=2019;
  rep(i,(1<<D)){
    int h=100;
    int k=i;
    int s=0;
    int a=0;
    int n=1;
    rep(j,D){
      if(k%2==0) {
        h=(j+1)*100;
        n=j;
      }
      else{
        s+=(j+1)*100*p[j]+c[j];
        a+=p[j];
      }
      k/=2;
    }
    if(G>=s and (G-s+h-1)/h<p[n] ) ans=min(ans,(G-s+h-1)/h+a);
    if(G<s) ans=min(ans,a);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
// Problem : B - Distance
// Contest : AtCoder - AtCoder Beginner Contest 174
// URL : https://atcoder.jp/contests/abc174/tasks/abc174_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

/**
 * @author dwij
 */

#include <bits/stdc++.h>

#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>

using namespace std;

//******* Debugging Class Template *******/
#define sim template <class c
#define ris return *this
#define dor > deb& operator<<
#define eni(x) \
    sim > typename enable_if<sizeof dud<c>(0) x 1, deb&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct deb {
#ifdef LOCAL
    ~deb() { cerr << endl; }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c&) { ris; }
#endif
}
;
#define log(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// End of weird debugging stuff.

typedef long long ll;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>

#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(), c.end()
#define mem(a, val) memset(a, val, sizeof(a))
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define endl "\n"

void solution() {
    // deb() << log();
    ll n, d;
    cin >> n >> d;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        if (a * a + b * b <= d * d) {
            ans++;
        }
    }

    cout << ans << endl;
}

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

    int T = 1;
    // cin >> T;
    // cin.ignore(); //must be there when using getline(cin, s)
    for (int tt = 1; tt <= T; tt++) {
        // cout << "Case #" << tt << ": ";
        solution();
    }

    return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
int main(void)
{
	int n,x,y,k,z,r,m;
	
	scanf("%d",&n);
	scanf("%d",&k);
	scanf("%d",&x);
	scanf("%d",&y);
	
	z=k*x;
	r=(n-k)*y;
	m=z+r;
	
	if(n-k<0){
		m=n*x;
	}
	printf("%d\n",m);
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int N = Integer.parseInt(line);
		String[] S = new String[N];

		for(int i = 0 ; i < S.length;  i++) {
			S[i] = sc.nextLine();
//			System.out.println(S[i]);
		}

		int ac = 0;
		int wa = 0;
		int tle = 0;
		int re = 0;
		for(String s: S) {
			if(s.equals("AC")) {
				ac++;
			}else if(s.equals("WA")) {
				wa++;
			}else if(s.equals("TLE")) {
				tle++;
			}else {
				re++;
			}
		}

		System.out.println("AC x " + ac);
		System.out.println("WA x " + wa);
		System.out.println("TLE x " + tle);
		System.out.println("RE x " + re);
	}

}


Measured memory_bytes: 65024
#include<bits/stdc++.h>
#define REP(n)    for(int i = 0; i < (n); ++i)
#define RREP(n)   for(int i = (n); i >= 0; --i)
#define FOR(m, n) for(int i = (m); i < (n); ++i)
#define SZ(x)       ( (int)(x).size() )
#define BIT(n)      ( 1LL << (n) )
#define EXIST(x)    ( (x).find()		!= (x).end() )
#define DEBUG(n)    cerr << #n << " : " << n << '\n';
#define PB  push_back
#define UB  upper_bound			//k <
#define LB  lower_bound			//k	<= 
#define F   first
#define S   second
#define INF 1.0e9


using namespace std;

typedef long long			ll;
typedef pair<int, int>		pii;
typedef pair<long			long, long long>   pll;
typedef vector<int>			vi;
typedef vector<double>		vd;
typedef vector<long long>   vll
;

template<class T> void chmax(T &	a, const T & b){ if( a < b ) a = b; }
template<class T> void chmin(T &	a, const T & b){ if( a > b ) a = b; }

int r_up(const int a, const int b){ return (a + b - 1) / b; }

const int dx[] = { 0,  0, 1, -1 };
const int dy[] = { 1, -1, 0,  0 };

struct UFT{
  vi	p;
  UFT(){}
  UFT(int N)       { p.resize( N, -1 ); }
  int	par(int a)   { if( p[a] >= 0 ){ p[a]  = par( p[a] ); return p[a]; } return a;  }
  int size(int a)  { return -p[par(a)]; }
  bool	same(int a, int b) { return par(a)	 == par(b); }
  void unite(int	a, int b){
	a													  = par(a);  b = par(b);
	if( a == b ) return;
	if( size(a) < size(b) ) swap(a,b);
	p[a]												 -= size(b);
	p[b]												  = a;
  }
};

int main(){
  int n;cin>>n;
  switch(n){case 3:case 5:case 7:cout<<"YES\n";break;default: cout<<"NO\n";}
  return 0;
}


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

int main(){
    string S;
    cin >> S;
    if(S == "abc" || S == "acb"){
        cout << "Yes" <<endl;
    }
    else if(S == "bac" || S == "bca"){
        cout << "Yes" << endl;
    }
    else if(S == "cab" || S == "cba"){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" <<endl;
    }
}


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

using namespace std;

using ll = long long;

int main(){
    ll a, b, k, ans = 0;
    cin >> a >> b >> k;
    for(ll i = min(a, b); i >= 1; --i){
        if(a % i == 0 && b % i == 0){
            ans++;
            if(ans == k){
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
N = chomp(readline())
keta = length(N)
ans = 0
for i in 1:2:keta
  ans += (10^i - 10^(i-1)) 
end
if keta % 2 == 1
  N = parse(N)
  ans += N - 10^keta + 1
end
println(ans)
  

Measured memory_bytes: 166396
n,x=map(int,input().split())
z=list(map(int,input().split()))
z.sort()
def gcd(a,b):
    if b==0:
        return a 
    return gcd(b,a%b)
ans=abs(x-z[0])

for i in range(n-1):
    sa=z[i+1]-z[i]
    ans=gcd(sa,ans)
print(ans)



Measured memory_bytes: 14252
#include<stdio.h>

int souwa(int);

int main(){
	int n;
	while(scanf("%d",&n)!=-1){
		printf("%d\n",souwa(n));
	}
	return 0;
}

int souwa(int n){
	int i,j,k,l,cnt=0;
	for(i=0;i<10;i++)
		for(j=0;j<10;j++)
			for(k=0;k<10;k++)
				for(l=0;l<10;l++){
					if(n==i+j+k+l)cnt++;
					}
	return cnt;
}

Measured memory_bytes: 596
#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

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

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

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> A(N + 1);
    vector<ll> B(N);
    rep(i, N + 1) { cin >> A[i]; }
    rep(i, N) { cin >> B[i]; }

    ll ans = 0;
    rep(i, N) {
        if (A[i] <= B[i]) {  //余裕があるとき
            ans += A[i];
            ll diff = B[i] - A[i];
            if (A[i + 1] <= diff) {  //余力で次のも倒せるとき
                ans += A[i + 1];
                A[i + 1] = 0;
            } else {  //余力では次のは倒せない時
                ans += diff;
                A[i + 1] = A[i + 1] - diff;
            }
        } else {  //余裕がないとき
            ans += B[i];
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
  ll n;
  cin >> n;
  ll m;
  cin >> m;
  vector<ll> h(n);
  for (int i=0; i<n; i++){
    cin >> h[i];
  }
  vector<vector<int>> to(n);
  for (int i=0; i<m; i++){
    int a,b; cin >> a >> b; a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  int ans = 0;
  for (int i=0; i<n; i++) {
    bool flg = true;
    for (auto v:to[i]) {
      if (h[i] <= h[v]) flg = false;
    }
    if (flg) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 9020
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

int L[100];
int D[101];

int main()
{
    int n, x;

    cin >> n >> x;
    for (int i = 0; i < n; i++)
    {
        cin >> L[i];
    }

    D[0] = 0;
    for (int i = 0; i < n; i++)
    {
        D[i + 1] = D[i] + L[i];
    }

    int cnt = 0;
    for (int i = 0; i < n + 1; i++)
    {
        if (D[i] <= x)
        {
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iomanip>
#include <iostream>
#include <cmath>

using namespace std;

int main(int argc, char* argv[]) {
  double a, b, C; cin >> a >> b >> C;
  double S, L, h;
  h = b*sin(C*M_PI/180.0);
  S = a * h / 2;

  double a1, a2, c;
  a1 = sqrt(pow(b, 2)-pow(h, 2));
  if (C <= 90) {
    a2 = a - a1;
  } else {
    a2 = a + a1;
  }
  c = sqrt(pow(a2, 2)+pow(h, 2));
  L = a+b+c;
  
  cout << fixed << setprecision(6);
  cout << S << endl << L << endl << h << endl;
  return 0;
}

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

int main()
{
    int x, y, buf;
    while(1)
    {
        cin >> x >> y;
        if(x == 0 && y == 0) break;
        if(x > y)
        {
            buf = x;
            x = y;
            y = buf;
        }
        cout << x << " " << y << endl;
    }
    return 0;
}


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

int main()
{
    const int ROW = 100;
    const int COL = 100;
    int r, c;
    int t[ROW][COL];

    memset(t, 0, sizeof(t));

    cin >> r >> c;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            cin >> t[i][j];

    for(int i = 0; i < r; i++)
    {
        long s = 0;
        for(int j= 0; j < c; j++)
        {
            if(j > 0)
                cout << ' ';
            cout << t[i][j];
            s += t[i][j];
        }
        cout << ' ' << s << endl;
    }

    long long a = 0;
    for(int j = 0; j < c; j++)
    {
        long s = 0;
        for(int i = 0; i < r; i++)
        {
            s += t[i][j];
        }
        if(j > 0)
            cout << ' ';
        cout << s;
        a += s;
    }
    cout << ' ' << a << endl;

    return 0;
}

Measured memory_bytes: 3128
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] x = sc.next().toCharArray();
        int sCnt = 0;
        int setCnt = 0;
        for (int i = 0; i < x.length; i++) {
            if(x[i] == 'S') sCnt++;
            else if(sCnt>0){
                setCnt++;
                sCnt--;
            }
        }
        System.out.println(x.length - (setCnt * 2));
        sc.close();

    }

}


Measured memory_bytes: 25940
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

  static final int N = 100000;
  static final int Q = 50000;
  static int n, q;
  static int s[], t[];

  public static int binary_search(int x) {
    int l = 0;
    int r = n;
    int m;
    while (r-l > 0) {
      m = (l+r)/2;
      if (s[m] == x)
      return m;
      else if (s[m] < x) 
        l = m + 1;
      else
        r = m;
    }
    return -1;
  }

  public static void main(String[] args) {
    int i;
    Scanner sc = new Scanner(System.in); 
    n = Integer.parseInt(sc.next());
    s = new int[n];
    for (i=0; i<n; i++)
      s[i] = Integer.parseInt(sc.next());

    q = Integer.parseInt(sc.next());
    t = new int[q];
    for (i=0; i<q; i++)
      t[i] = Integer.parseInt(sc.next());

    int res = 0;
    for (i=0; i<q; i++)
      if (binary_search(t[i]) != -1)
        res++;

    System.out.println(res);
  }
}

Measured memory_bytes: 68124
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
n = ii()
l = [0]*10001
for x in range(1,100):
    for y in range(x,100):
        for z in range(y,100):
            num = x**2+y**2+z**2+x*y+y*z+z*x
            if num < 10001:
                if x==y and y==z:
                    l[num] += 1
                elif x==y or y==z:
                    l[num] += 3
                else:
                    l[num] += 6

for i in l[1:n+1]:
    print(i)

Measured memory_bytes: 9316
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <bitset>
using namespace std;

int main(){
    int n;
    int a[100100];
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int b[100100];
    for(int i = 0; i < n; i++) b[a[i]-1] = i + 1;
    for(int i = 0; i < n; i++) cout << b[i] << endl;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define eps 0.000000001
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+5;
int main(){
	double a,b,c;cin>>a>>b>>c;
	if(a/c<=b) puts("Yes");
	else puts("No");
}


Measured memory_bytes: 3696
N ,X = map(int, input().split())
m = [int(input()) for _ in range(N)]
minW = 1000
c = 0

for i in m:
    X -= i
    if minW > i:
        minW = i
c += N

while X - minW >= 0:
    X -= minW
    c += 1

print(c)

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int p_MAX = 110000;
vector<int> prime;
// エラトステネスの篩(vec)
int calc_prime()
{
  bool notPrime[p_MAX];
  int n = sqrt(p_MAX)+1;
  notPrime[0]=1;
  notPrime[1]=1;
  for(int i=0;i<=n;i++){
    if(notPrime[i])
      continue;
    int m = p_MAX/i;
    for(int j=2;j<=m;j++)
      notPrime[j*i]=1;
  }
  prime.clear();
  for(int i=0;i<p_MAX;i++)
    if(!notPrime[i])
      prime.push_back(i);
  return 0;
}
int main()
{
  int q,t,l,r,i,j,res;
  vector<int> x;
  vector<int>::iterator li,ri;
  cin >> q;
  calc_prime();
  for(i=0,li=prime.begin();i<prime.size();i++){
    t=(prime[i]+1)/2;
    ri=lower_bound(li,prime.end(),t);
    if(*ri==t){
      x.push_back(prime[i]);
      li=ri;
    }
  }
  for(i=0;i<q;i++){
    cin >> l >> r;
    li=lower_bound(x.begin(),x.end(),l);
    ri=upper_bound(x.begin(),x.end(),r);
    cout << distance(li,ri) << endl;
  }
  return 0;
}

Measured memory_bytes: 896
# 解説見た後に作ったやつ
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, K = map(int, input().split())
    S = list(input())

    rev = False
    ans = 0
    rev_count = 0
    for i in range(1,N):
        if S[i] == S[i-1]:
            ans += 1
            rev = False
        else:
            if not rev and rev_count < K:
                rev_count += 1
                rev = True

            if rev:
                S[i] = 'L' if S[i] == 'R' else 'R'
                ans += 1


    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3956
import java.util.Scanner;

public class Main {

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

        final long N = sc.nextLong();
        final long X = sc.nextLong();

        long res = 0;

        for (int i = 0; i < N; i++) {
            final long x = sc.nextLong();
            res = gcd(res, Math.abs(x-X));
        }

        System.out.println(res);
    }

    private static long gcd(final long a, final long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}


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

using namespace std;
int N;
int main()
{
    cin>>N;
    set<string> s;
    for(int i=0;i<N;i++){
        string t;
        cin>>t;
        s.insert(t);
    }
    
    cout<<s.size()<<endl;

    return 0;
}


Measured memory_bytes: 19064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int H, W; 
    cin >> H >> W; 
    char c[60][60]; 
    for (int i = 1; i <= H; ++i){
    for(int j = 1; j <= W; ++j){ cin >> c[i][j]; 
     }
    }
    int d[60][60]; 
    for (int i = 1; i <= H; ++i){
    for(int j = 1; j <= W; ++j){
      if(c[i][j] == '#') d[i][j] = 1;
      else d[i][j] = 0; 
     }
    }
    string ans = "Yes";  
    for(int i = 1; i <= H; ++i){
    for(int j = 1; j <= W; ++j){
      if(d[i][j] == 1 && d[i-1][j] == 0 
         && d[i+1][j] == 0 && d[i][j-1] == 0 
         && d[i][j+1] == 0){
      ans = "No";
      break; 
      }
     }
      if(ans == "No") break; 
    } 
    cout << ans << endl; 
}

Measured memory_bytes: 256
/*
    *
    * Cyrus Jackson
    * VIT University - India
    *
*/
#define TCase(k) cout<<"Case #"<<(int)k+1<<": ";
#include <iostream>
#include <sstream>
#include <fstream>
#include <memory.h>
#include <cassert>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <functional>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <time.h>
#include <stack>
#include <set>
#include <climits>

#define cl1 double _time=clock();
#define cl2 cerr<<endl<<"time: "<<double(clock()-_time)<<endl;
#define clockTime cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#define BO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fi BO;freopen("in.txt","r",stdin);
#define fo freopen("out.txt", "w", stdout);
#define test()    int test_case;cin>>test_case;while(test_case--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define forR(i,n) for (int i = n; i --> 0; )
#define forO(i,n) for(int i = 1; i <= n; i++)
#define forN(i,n) for(int i = 0; i < n; i++)
#define forA(i,a,n) for(int i = a; i < n; i++)
#define s(t) scanf("%d",&t)
#define fill(t) memset(t,0,sizeof(t));
long long MOD = 1e9 + 7;
int GCD(int A, int B) {    if(B==0)        return A;    else        return GCD(B, A % B); }
typedef long long int ll;
const int INF = 1<<29;
#define MAX 10001
using namespace std;
vector<string> sub;
bool canForm(vector<int> v, int sum, int c, int n, int p, map<int,int> &m){
	if(sum < 0 || p >= n) return false;
	if(sum == c) {
		cout<<c<<endl;
		return true;
	}
	if(v[p] > sum){
		// do something
		return false;
	}
	return canForm(v,sum,c,n,p+1,m) || canForm(v,sum,c+v[p],n,p+1,m);
	
	
}
int main()
{
//	fi;
	int n; cin>>n;
	vector<int> v(2*n,0);
	forN(i,2*n) cin>>v[i];
	sort(v.begin(),v.end());
	int ans = 0;
	for(int i = 0; i < 2*n; i += 2){
		ans += min(v[i],v[i+1]);
	}
	cout<<ans<<endl;
	
	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

ll dp[100010];

int main()
{
	int n,m;
	cin >> n >> m;
	vi a(m);
	rep(i,m) cin >> a[i];
	dp[0] = 1;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(cnt < m && i == a[cnt]) { cnt++; continue; }
		if(i == 1) dp[i] = 1;
		else dp[i] = (dp[i-2]+dp[i-1])%MOD;
	}
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 1280
#include <cassert>
#include <cmath>
#include <cstdio>
#include <map>
#include <vector>

using Long = long long;

const int M = 2155;

bool visited[M];

Long int_sqrt(Long n)
{
    Long r = sqrt(n) + 1;
    while (r * r > n) {
        r --;
    }
    if (r * r == n) {
        return r;
    }
    return -1;
}

int main()
{
#ifdef LOCAL_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int p = 2; p * p < M; ++ p) {
        for (int pd = p * p; pd < M; pd += p * p) {
            visited[pd] = true;
        }
    }
    std::vector<Long> free;
    for (int i = 1; i < M; ++ i) {
        if (!visited[i]) {
            free.push_back(i);
        }
    }
    int n;
    while (scanf("%d", &n) == 1) {
        int result = 0;
        std::map<Long, int> count;
        for (int i = 0; i < n; ++ i) {
            Long a;
            scanf("%lld", &a);
            for (auto p : free) {
                if (p > 1) {
                    while (a % (p * p * p) == 0) {
                        a /= p * p * p;
                    }
                }
            }
            if (a != 1) {
                Long b = 0;
                for (auto p : free) {
                    if (a % p == 0) {
                        auto q = int_sqrt(a / p);
                        if (~q) {
                            b = p * p * q;
                            break;
                        }
                    }
                }
                if (!b) {
                    for (int j = (int)free.size() - 1; j >= 0; -- j) {
                        auto q = free[j];
                        if (a % (q * q) == 0) {
                            auto p = a / (q * q);
                            b = p * p * q;
                            break;
                        }
                    }
                }
                assert(b);
                result += std::max(count[a] + 1, count[b]) - std::max(count[a], count[b]);
            }
            count[a] ++;
        }
        printf("%d\n", result + !!count[1]);
    }
}



Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
using namespace std;
using v = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}

int main(int argc, char *argv[]){
    int N, m;
    // , P(m), X(m);
    cin >> N;
    vector<int> Time(N);
    rep(i, N) cin >> Time[i];
    cin >> m;
    int p, x, sum;
    rep(i, m){
        // cin >> P[i] >> X[i];
        sum = 0;
        // cout << i+1 << " -------------- " <<  endl;
        cin >> p >> x;
        rep(j, Time.size()){
            if(p-1 == j) sum += x;
            else sum += Time[j];
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
main(){
for(double r,i,j;std::cin>>r,r;printf("%.0f/%.0f\n",j,i)){
 for(i=0;++i<1000000;){
  j=(int)(i*M_PI);
  if(fabs(j/i-M_PI)<=r||fabs(++j/i-M_PI)<=r)break;
 }
}}

Measured memory_bytes: 0
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	// L(i): minimum cost at stone i
	//freopen("input.txt", "rt", stdin);
	int n;
	cin >> n;
	vector<int> dp(n, 9999999);
	vector<int> vecN(n);
	for (auto& i : vecN) {
		cin >> i;
	}

	dp[0] = 0;
	dp[1] = abs(vecN[1] - vecN[0]);
	
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 1] + abs(vecN[i] - vecN[i - 1]), dp[i - 2] + abs(vecN[i] - vecN[i - 2]));
	}

	cout << dp[n - 1] << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include<string>
#include<cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
#include<stack>
#include<set>
#include <limits>
#include <climits>
#include <numeric>
using namespace std;
typedef long long ll;
typedef vector<int>VI;
typedef pair<int,int>P;
typedef pair<double,double>P_D;
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define ALL(a)  (a).begin(),(a).end()
#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define fi first
#define se second
#define MAX 100100//5
#define MAX_N 200100
#define MAX_B 1001001//6
#define MAX_S 10010010//7
#define SENTINEL 2000000000//9
#define NIL -1
#define MOD 1000000007
#define INF 1<<30
#define INFTY 1000000000000000001LL
#define MAX_INT INT_MAX

int main(){
    double l;cin>>l;
    double k=l/3;
    printf("%.10lf\n",k*k*k);
}

Measured memory_bytes: 256
#include <string>
#include <algorithm>
#include <vector> 
#include <math.h>
#include <iostream>
using namespace std;
long long mod = 1000000000 + 7;

int main()
{
	int n,m;
	cin >> n >> m;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		long long ai;
		cin >> ai;
		a[i] = ai;
	}
	
	vector<pair<long long, int>> b;
	for (int i = 0; i < m; i++) {
		int bi;
		long long ci;
		pair<long long, int> ch;
		cin >> bi >> ci;
		ch.first = ci;
		ch.second = bi;
		b.push_back(ch);

	}
	
	sort(b.begin(), b.end());
	int count = 0;
	int i = m - 1;
	while (count <= n) {
		count = count + b[i].second;
		for (int j = 0; j < b[i].second; j++) {
			a.push_back(b[i].first);
		}
		i--;
		if (i == -1) {
			count = n + 1;
		}
	}

	sort(a.begin(), a.end());
	long long ans = 0;
	for (int j = 0; j < n; j++) {
		ans = ans + a[a.size() -1 -j];
	}
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 6624
#input
N, K = map(int, input().split())
A = list(map(int, input().split()))

#output
import math

A.sort()
mod = 10**9+7

n_ = 10**5 + 3
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
#これだとTLE!
"""
def cmb(n, r):
    if n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
"""

M = 0
m = 0
for i, a in enumerate(A):
    M += cmb(i, K-1) * a
    m += cmb(N-i-1, K-1) * a
    M %= mod
    m %= mod

print((M-m) % mod)

Measured memory_bytes: 15060
##########################
from collections import defaultdict as ddict
N, C = map(int, input().split())
imos = [0] * (10**5 + 2)
last_s_by_c = ddict(lambda: 1)
last_t_by_c = ddict(int)
stc = [list(map(int, input().split())) for i in range(N)]
for s, t, c in sorted(stc, key=lambda x: x[1]):
	if last_t_by_c[c] != s:
		imos[last_s_by_c[c] - 1] += 1
		imos[last_t_by_c[c]] -= 1
		last_s_by_c[c] = s
	last_t_by_c[c] = t
for c in last_s_by_c:
	imos[last_s_by_c[c] - 1] += 1
	imos[last_t_by_c[c]] -= 1
for i in range(10**5 + 1):
	imos[i + 1] += imos[i]
print(max(imos))


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

using namespace std;
using ll = long long;

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

    ll n, a, b;

    cin >> n >> a >> b;

    ll ans = n / (a + b) * a;

    if(n % (a + b) <= a) ans += n % (a + b);
    else ans += a;

    printf("%lld\n", ans);

    return 0;
}

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
#define ALL(v) (v).begin(), (v).end()
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif


map<int,int> dp;

int calc(int H){
    if(H==0) return 0;
    if(H==1) return 1;
    if(dp[H]>0) return dp[H];
    return dp[H] = 1+calc(H/2)*2;
}

void solve(){
    int H;
    cin >> H;
    cout << calc(H) << endl;
}

signed main(){
    cout << fixed << setprecision(18) << endl;
    cerr << fixed << setprecision(18) << endl;
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int even = 0;
    rep(i, n)
    {
        if (a[i] % 2 == 0)
            even++;
    }
    cout << pow(3, n) - pow(2, even) << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter

def board(dp, i):
  m = 1
  while i*m <= len(dp)-1:
    dp[i*m]=False
    m+=1

a=int(input())
b=[int(x) for x in input().split()]
b=sorted(b)
d=Counter(b)
dp=[True]*(b[-1]+1)
c=0
for i in b:
  if dp[i] and d[i] < 2:
    c+=1
  board(dp, i)
print(c)

Measured memory_bytes: 38220
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()

p_array = na()

p_array.sort()

print(sum(p_array[:K]))


Measured memory_bytes: 62272
//7
//218 233 389 645 704 728 786 
#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n-2;i++){
		for(int j=i+1;j<n;j++){
			if(a[i]+a[j]>a[n])ans+=n-j;
			else{
				for(int k=n-1;k>j;k--){
					if(a[i]+a[j]>a[k])ans++;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}
/*
7
218 786 704 233 645 728 389

1:218 786 704
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12: 
13:
14:
15:
16:
17:
18: 
19:
20:
21:
22:
23:




*/


Measured memory_bytes: 256
#include <iostream>

int main() {
	int n;
	std::cin >> n;

	int a[200010];
	for (int i = 0; i < n; ++i)
		std::cin >> a[i];

	int min = -1;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			min = a[i];
			++ans;
		}
		else {
			if (a[i] < min) {
				++ans;
				min = a[i];
			}
		}
	}

	std::cout << ans;
}

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

using namespace std;

int main(){
    long int H,W;
    long int n;
    cin >> H >> W;
    if(H==1 || W==1){
        n=1;
    }else{
        //1行目の行けるマス
        n=(W+1)/2;
        if(W%2==0){
            n=n*H;
        }else{
            if(H%2==0){
                n=(2*n-1)*(H/2);
            }else{
                n=(2*n-1)*(H/2)+(W+1)/2;
            }
        }
    }
    cout << n;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
	int X, N;
	cin >> X >> N;
	vector<int> p(N);
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}
	int min = 110;
	int ans = X;
	for (int i = 101; i > -3; i--) {
		int check = 0;
		for (int j = 0; j < N; j++) {
			if (i == p[j]) {
				check = -1;
			}
		}
		if (check == 0) {
			if (abs(X - i) <= min) {
				min = abs(X - i);
				ans = i;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    lint K;
    cin >> N >> K;
    VEC(lint) A(N), F(N);
    READVEC(A);
    READVEC(F);

    sort(ALL(A), greater<lint>());
    sort(ALL(F));

    auto check = [&](lint x) {
        lint ret = 0;
        FOR(i, 0, N) {
            // (Ai - t) * F[i] <= x
            // t >= Ai - x / F[i]
            lint need = max(A[i] - x / F[i], 0LL);
            ret += need;
        }

        return ret;
    };

    lint lo = 0, hi = 1LL << 60;
    while (hi - lo > 1) {
        lint md = lo + (hi - lo) / 2;
        if (check(md) <= K)
            hi = md;
        else
            lo = md + 1;
    }

    if (check(lo) > K)
        lo = hi;

    cout << lo << endl;
    return 0;
};


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll INF = 1LL << 30;

int main(void){
    string S; cin >> S;
    
    bool ans = true;
    for(int i = 0; i < S.size(); i++){
        if(i % 2 == 1){
            if(!(S[i] == 'L' || S[i] == 'U' || S[i] == 'D')) ans = false;
        }
        else if(i % 2 == 0){
            if(!(S[i] == 'R' || S[i] == 'U' || S[i] == 'D')) ans = false;
        }
    }
    if(ans) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}


Measured memory_bytes: 256
use std::io;
use std::cmp;


fn main() {
    let n = read_one::<usize>();
    let hn = read::<isize>();
    let mut dp = vec![::std::isize::MAX; n];
    dp[0] = 0;
    dp[1] = (hn[1] - hn[0]).abs();
    for i in 2..n {
        dp[i] = cmp::min(
            (hn[i - 1] - hn[i]).abs() + dp[i - 1],
            (hn[i - 2] - hn[i]).abs() + dp[i - 2]
        );
    }

    println!("{}", dp[n - 1]);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 6396
import itertools
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

route = list(itertools.permutations(list(range(N))))

ans = 0
for i in range(len(route)):
  for j in range(N-1):
    a = route[i][j]
    b = route[i][j + 1]
    X = (xy[a][0] - xy[b][0]) ** 2
    Y = (xy[a][1] - xy[b][1]) ** 2
    ans += (X + Y) ** 0.5
print(ans / len(route)) 

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

#define vec              vector<int>
#define vecll            vector<ll>
#define vecd             vector<double>
#define vecst            vector<string>
#define vecb             vector<bool>
#define v2(v,n,m,init)   vector<vector<int>>  v(n, vector<int>(m, init))
#define vb2(v,n,m,init)  vector<vector<bool>> v(n, vector<bool>(m, init))
#define vll2(v,n,m,init) vector<vector<ll>>   v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
//----------------------------------------------------------------

int main(void) {
  string s;
  cin >> s;
  if(s[0]=='9' || s[1]=='9'){
    prt("Yes");
  } else {
    prt("No");
  }

}


Measured memory_bytes: 3572
s = int(input())
a = []
for i in range(1,1000001):
  if i == 1:
    a.append(s)
  else:
    if a[len(a)-1]%2 == 0:
      a.append(a[len(a)-1]//2)
    else:
      a.append(3*a[len(a)-1] + 1)
    if a.index(a[len(a)-1]) != len(a)-1:
      print(len(a))
      break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define print(x,y) (cout << (x) << (y))
#define inf INT_MAX
#define sz(x) (ll)x.size()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair< int , pii> piii;
typedef pair<int,bool> pib;
typedef vector<pii> vii;
typedef vector<pib> vib;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<string,string> pss;
typedef vector<pss> vss;
const int MOD = 1e9 + 7; //998244353;


int main() {
    int n , m;
    cin >> n >> m;
    string grid[n];
    for(int i = 0;i<n;i++) cin >> grid[i];
    int dp[n][m];
    memset(dp , 0 , sizeof dp);
    dp[0][0] = (grid[0][0] == '.');
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(grid[i][j] == '#')continue;
            if(i) dp[i][j] +=dp[i-1][j];
            dp[i][j]%=MOD;
            if(j) dp[i][j] +=dp[i][j-1];
            dp[i][j]%=MOD;
        }
    }
    cout << dp[n-1][m-1];
}




Measured memory_bytes: 5248
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  9 20:50:35 2020

@author: akros
"""

# -*- coding: utf-8 -*-
"""
Created on Sun Aug  9 16:51:42 2020

@author: akros
"""

A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))

N = int(input())
a = []

for i in range(N):
    a.append(int(input()))
   
    if A1[0] == a[i]:
        A1[0] = True
    elif a[i] == A1[1]:
        A1[1] = True
    elif a[i] == A1[2]:
        A1[2] = True
    elif a[i] == A2[0]:
        A2[0] = True
    elif a[i] == A2[1]:
        A2[1] = True
    elif a[i] == A2[2]:
        A2[2] = True
    elif a[i] == A3[0]:
        A3[0] = True
    elif a[i] == A3[1]:
        A3[1] = True
    elif a[i] == A3[2]:
        A3[2] = True


if A1[0] == True and A1[1] == True and A1[2] == True:
    print("Yes")
elif A1[0] == True and A2[0] == True and A3[0] == True:
    print("Yes")
elif A1[0] == True and A2[1] == True and A3[2] == True:
    print("Yes")
elif A1[1] == True and A2[1] == True and A3[1] == True:
    print("Yes")
elif A1[2] == True and A2[2] == True and A3[2] == True:
    print("Yes")
elif A2[0] == True and A2[1] == True and A2[2] == True:
    print("Yes")
elif A3[0] == True and A3[1] == True and A3[2] == True:
    print("Yes")
elif A1[2] == True and A2[1] == True and A3[0] == True:
    print("Yes")
    
else:             
    print("No")

    
    
    


Measured memory_bytes: 9340
#include<cstdio>
const int N=3005,P=1e9+7;
const long long I=5e8+4;
int n,q,v[N],f[N][N],a;
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			if(v[i]>v[j])++f[i][j];
			else if(v[i]<v[j])++f[j][i];
	for(int i=1,x,y;i<=q;++i)
	{
		scanf("%d%d",&x,&y);
		for(int j=1;j<=n;++j)if(j!=x&&j!=y)
			f[x][j]=f[y][j]=I*(f[x][j]+f[y][j])%P,f[j][x]=f[j][y]=I*(f[j][x]+f[j][y])%P;
		f[x][y]=f[y][x]=I*(f[x][y]+f[y][x])%P;
	}
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j)
			(a+=f[i][j])%=P;
	for(int i=1;i<=q;++i)(a*=2)%=P;
	return printf("%d",a),0;
}

Measured memory_bytes: 36936
#include <stdio.h>
#include <set>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, m, a, now, ans = 0;
  scanf("%lld%lld", &n, &m);
  multiset<ll> s;
  multiset<ll>::iterator it;
  for(i = 0; i < n; ++i) scanf("%lld", &a), s.insert(a);
  for(i = 0; i < m; ++i) {
    it = s.end();
    now = *(--it) / 2;
    s.erase(it), s.insert(now);
  }
  for(it = s.begin(); it != s.end(); ++it) ans += *it;
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 4864