akhauriyash/Code-Regression huggingface dataset:
import collections

def main():
    N = input()
    A = map(int, input().split())
    c = collections.Counter(A)
    edge1 = None
    for edge, freq in sorted(c.items(), key=lambda x: -x[0]):
        if edge1 is None and freq >= 4:
            print(edge ** 2)
            exit()
        elif edge1 is None and freq >= 2:
            edge1 = edge
        elif edge1 is not None and freq >= 2:
            print(edge1 * edge)
            exit()
    print(0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 102124
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>	tree_set;
typedef long long ll;
typedef long double ld;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

ll mod=1e9 + 7;

int main()
{
    fast();
    ll n,m;
    cin>>n>>m;

    ll arr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];

    sort(arr,arr+n);

    vector< pair<ll,ll> >op(m);
    for(ll i=0;i<m;i++)
        cin>>op[i].second>>op[i].first;

    sort(op.begin(),op.end());
    reverse(op.begin(),op.end());

    bool flg=true;
    ll i=0;
    for(ll j=0;j<m;j++)
    {
        ll k = i+ op[j].second;
        for(;i<k;++i)
        {
            if(i>n || op[j].first<=arr[i])
            {
                flg=false;
                break;
            }
            arr[i]=op[j].first;
        }

        if(!flg)
            break;
    }

    ll ans=0;
    for(ll i=0;i<n;i++){
        ans+=arr[i];
        //cout<<arr[i]<<" ";
    }

    cout<<ans;
}



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

int main() {
  int N = 0;
  cin >> N;
  
  vector<int64_t> L(N + 1);
  L.at(0) = 2;
  L.at(1) = 1;
  
  for (int i = 2; i < N + 1; i++) {
    L.at(i) = L.at(i - 1) + L.at(i - 2);
  }
  
  cout << L.at(N) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<(int)(r); i++)
#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)
#define all(vec) vec.begin(),vec.end()
#define allr(vec) vec.rbegin(),vec.rend()
using namespace std;

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

using ll=int64_t;

using vb=vector<bool>;
using vc=vector<char>;
using vs=vector<string>;
using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

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

  int N,K; cin >>N >>K;
  vi A(N);
  rep(i,0,N) {cin >>A[i];}

  int ans=0;
  int right=0;
  while (true) {
    if (ans==0) {
      right+=K;
    } else {
      right+=K-1;
    }
    ans++;
    if (N<=right) {
      break;
    }
  }

  cout <<ans <<'\n';
  return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define mod 1000000007
#define ss second
#define ff first
#define vpii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define vs vector<string>
#define all(x) x.begin(),x.end()
#define mii map<int,int>
const int inf=0x3f3f3f3f3f3f3f3f;
void print(vi &v){
    for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
    cout<<endl;
}
int power(int a,int b){
    int res = 1;
    while(b!=0){
        if(b&1){
            res *= a; 
        }
        a = (a * a);
        b = (b / 2);
    }
    return res;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t = 1;
    while(t--){
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++){
        	if(s[i]=='7'){
        		cout<<"Yes"<<endl;
        		return 0;
        	}
        }
        cout<<"No"<<endl;
        return 0;
    }
    return 0;
}

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

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In,' '));
        }

        public void Solve(ConsoleInput cin)
        {
            string b = cin.ReadLine;
            switch (b)
            {
                case "A" :
                    WriteLine('T');
                    break;
                case "T" :
                    WriteLine('A');
                    break;
                case "C" :
                    WriteLine('G');
                    break;
                case "G" :
                    WriteLine('C');
                    break;
            }

        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream,char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0;i < tmp.Length;i++)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }

        
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }

}


Measured memory_bytes: 11220
sa = gets.chomp
sb = gets.chomp
sc = gets.chomp
s = [sa,sb,sc]
t = {"a"=>0, "b"=>1, "c"=>2}
turn = 0
loop do
    x = s[turn]
    if x == "" then
        puts t.key(turn).upcase
        break
    end
    next_t = t[x[0]]
    s[turn] = x[1..-1]
    turn = next_t
end

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int bs_upper_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

int bs_lower_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 

int n;
vector<ll> a;

/*ll solve(int l,int r,int play){
    if(l==r){
        if(play==1)
            return -1*a[l];
        else
            return a[l];
    }
    else{
        if(play==0)
            return max(a[l]+solve(l+1,r,!play),a[r]+solve(l,r-1,!play));
        else
            return min(-1*a[l]+solve(l+1,r,!play),-1*a[r]+solve(l,r-1,!play));
    }
}*/

int main()
{
    IOS;
    cin>>n;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        a.push_back(x);
    }
    ll dp[n][n][2];
    for(int i=n-1;i>=0;i--){
        dp[i][i][1]=-1*a[i];
        dp[i][i][0]=a[i];
        for(int j=i+1;j<n;j++){
            dp[i][j][0]=max(a[i]+dp[i+1][j][1],a[j]+dp[i][j-1][1]);
            dp[i][j][1]=min(-1*a[i]+dp[i+1][j][0],-1*a[j]+dp[i][j-1][0]);
        }
    }
    cout<<dp[0][n-1][0];
}


Measured memory_bytes: 85392
MOD = 1000000007

def prime_fact(n)
  #素因数分解
  i = 2
  while i ** 2 <= n do
    cnt = 0
    while n % i == 0
      cnt += 1
      n /= i
    end

    @map[i] = cnt if cnt > 0 && (@map[i] == nil || @map[i] < cnt)
    i += 1
  end

  @map[n] = 1 if n != 1 && @map[n] == nil
end

def power(n, a, m)
  res = 1

  if a > 0
    res = power(n, a / 2, m)
    if a % 2 == 0
      res = (res * res) % m
    else
      res = ((res * res) % m * n) % m
    end
  end
  
  return res
end

def main
  n = gets.chomp.to_i
  a = gets.chomp.split.map(&:to_i)

  @map = {}

  a.each do |v|
    prime_fact(v)
  end

  gcd = 1
  @map.map { |v, k|
    gcd *= power(v, k, MOD)
  }

  ans = 0
  a.each do |v|
    ans += (gcd / v) 
  end

  puts ans % MOD
end

main

Measured memory_bytes: 190996
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)

int main(){
	int n,m;
	cin>>n>>m;
	int hu[60][2]={0},po[60][2]={0};
	rep(i,n)rep(j,2)cin>>hu[i][j];
	rep(i,m)rep(j,2)cin>>po[i][j];
	rep(i,n){
		int mi=1000000000;
		rep(j,m){
			int t=abs(hu[i][0]-po[j][0])+abs(hu[i][1]-po[j][1]);
			mi=min(mi,t);
		}
		rep(j,m){
			int t=abs(hu[i][0]-po[j][0])+abs(hu[i][1]-po[j][1]);
			if(mi==t){
				cout<<j+1<<endl;
				break;
			}
		}
	}
}











/*

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mt make_tuple
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
}





*/





Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll s[2][100001];
int a[2], q;
ll mn(ll x, int p){
    int i=lower_bound(s[p], s[p]+a[p], x)-s[p];
    ll ans=1e18;
    if(i>0) ans=min(ans, abs(x-s[p][i-1]));
    if(i<a[p]) ans=min(ans, abs(x-s[p][i]));
    return ans;
}
int main()
{
    cin>>a[0]>>a[1]>>q;
    
    for(int i=0; i<a[0]; i++) cin>>s[0][i];
    for(int i=0; i<a[1]; i++) cin>>s[1][i];
    for(int i=0; i<q; i++){
        ll x; cin>>x;
        ll ans=1e18;
        for(int p=0; p<2; p++){
            int j=lower_bound(s[p], s[p]+a[p], x)-s[p];
            if(j>0) ans=min(ans, abs(x-s[p][j-1])+mn(s[p][j-1], p^1));
            if(j<a[p]) ans=min(ans, abs(x-s[p][j])+mn(s[p][j], p^1));
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 2816
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	switch n % 10 {
	case 2, 4, 5, 7, 9:
		fmt.Printf("hon")
	case 3:
		fmt.Printf("bon")
	default:
		fmt.Printf("pon")
	}
}


Measured memory_bytes: 1816
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, M[N][N];
int color[N], d[N], f[N], tt;

//再帰関数による深さ優先探索
void dfs_visit(int u){
    int v;
    color[u] = GRAY;
    d[u] = ++tt; //最初の訪問
    for(v=0; v<n; v++){
        if(M[u][v] == 0) continue;
        if(color[v] == WHITE) {
            dfs_visit(v);
        }
    }
    color[u] = BLACK;
    f[u] = ++tt; //訪問の終了
}

void dfs(){
    int u;
    //初期化
    for(u=0; u<n; u++) color[u] = WHITE;
    tt = 0;

    for(u=0; u<n; u++){
        //未訪問のuを始点として深さ優先探索
        if(color[u] == WHITE) dfs_visit(u);
    }
    for(u=0; u<n; u++){
        printf("%d %d %d\n", u+1, d[u], f[u]); //タイムスタンプの出力
    }
}

int main(){
    int u, v, k, i, j;

    scanf("%d", &n);
    for(i=0; i<n; i++){
        for(j=0; j<n; j++) M[i][j] = 0;
    }

    for(i=0; i<n; i++){
        scanf("%d %d", &u, &k);
        u--;
        for(j=0; j<k; j++){
            scanf("%d", &v);
            v--;
            M[u][v] = 1;
        }
    }

    dfs();

    return 0;
}


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

using namespace std;

#define reps(i, n, m) for (int i = (int) (n); i < (int) (m); i++)
#define rep(i, n) reps(i, 0, (n))

int main() {
    int n; cin >> n;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    auto b = v;
    auto a = v;
    bool aa = prev_permutation(a.begin(), a.end());
    auto c = b;
    bool cc = next_permutation(c.begin(), c.end());
    if (aa) rep(i, n) cout << a[i] << " \n"[i==n-1];
    rep(i, n) cout << b[i] << " \n"[i==n-1];
    if (cc) rep(i, n) cout << c[i] << " \n"[i==n-1];
}


Measured memory_bytes: 3144
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#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++)
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1<<30;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};



int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n;
    cin>>n;
    vector<int> s(n,0);
    rep(i,n) cin>>s.at(i);
    int q;
    cin>>q;
    vector<int> t(q,0);
    rep(i,q) cin>>t.at(i);
    int cnt=0;
    rep(i,q){
        if(lower_bound(all(s),t[i])!=upper_bound(all(s),t[i])) cnt ++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 3412
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		String s = sc.next();

		Pattern p = Pattern.compile("(A|C|G|T)*");
		Matcher m = p.matcher(s);

		int ans = 0;
		while (m.find()) {
			ans = Math.max(ans,
					m.end() - m.start());
		}
		out.println(ans);
		sc.close();

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

}


Measured memory_bytes: 21844
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7; //924844033 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<double, double> Dll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, p, q, last, first, cnt, sum, ans, dp[40000],a[200000],b[200000];
string str, ss;
bool f;
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
struct edge { LL from, to, cost; };
vector<LL>vec;
vector<edge>ed;
vector<Pll>v;
map<LL,LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

int main() {
	cin >> c;
	if (c == 'a') {
		cout << "square1001" << endl;
	}
	else
	cout << "e869120" << endl;
	return 0;
}



Measured memory_bytes: 3144
import itertools
def main():
  a = int(input())
  b = int(input())
  c = int(input())
  d = int(input())
  s1 = a
  s2 = c
  s1 = min(s1,b)
  s2 = min(s2,d)
  print(s1+s2)
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
 
#define VALUE 1300
 
int a, b;  

int main(){
    scanf("%d %d",&a, &b);

    for (int i = 0; i < VALUE; i++){
        int a1 = i*0.08, b1 = i*0.1;
        if(a1==a && b1==b){
            printf("%d\n", i);
            return 0;
        }
    }

    printf("-1\n");
    return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  double ans=1.0*(n/2+n%2)/n;
  printf("%.10f\n",ans);
  return 0;
}

Measured memory_bytes: 256
a = []
for i in range(3):
    a += list(map(int, input().split()))
c = [False] * 9
n = int(input())
for i in range(n):
    b = int(input())
    if b in a:
        c[a.index(b)] = True
d = [[c[0], c[1], c[2]], [c[3], c[4], c[5]], [c[6], c[7], c[8]], [c[0], c[3], c[6]], [c[1], c[4], c[7]], [c[2], c[5], c[8]], [c[0], c[4], c[8]], [c[2], c[4], c[6]]]
if [True, True, True] in d:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double ll;
    ll = (x2 - x1)*(x2 - x1) + (y2-y1)*(y2-y1);
    cout << fixed;
    std::cout << setprecision(8) <<std::sqrt(ll) << std::endl;
}


Measured memory_bytes: 3284
#include <iostream>

using namespace std;

int N;
long long int X;

long long int a[55], c[55];

long long int CALL(int N, long long int X) {

	if (X == a[N]) { return c[N - 1] * 2 + 1; }
	else if (X > (a[N] + 1) / 2) { return c[N - 1] + 1 + CALL(N - 1, X - (a[N] + 1) / 2); }
	else if (X == (a[N] + 1) / 2) { return c[N - 1] + 1; }
	else if (X >= 2) { return CALL(N - 1, X - 1); }
	else { return 0; }
}

int main(void) {

	cin >> N >> X;

	a[0] = 1;
	for (int i = 1; i <= N; i++) {
		a[i] = a[i - 1] * 2 + 3;
	}

	c[0] = 1;
	for (int i = 1; i <= N; i++) {
		c[i] = c[i - 1] * 2 + 1;
	}

	cout << CALL(N, X) << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <list>
#include <math.h>
#include <iomanip>
#include <map>
#include <cstdlib>
#include <queue>
#include <stack>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

int static const N_MAX = 100 + 100;
int static const W_MAX = 1000 * 100 + 100;

int N,W;
int w[N_MAX];
long long v[N_MAX];
long long dp[N_MAX][W_MAX];

long long dfs(int i, long long j){

  if( dp[i][j] >= 0 ) return dp[i][j];

  long long ans = 0;
  if( i == N ) ans = 0;
  else if( j < w[i] ) ans = dfs(i+1,j);
  else ans = max(dfs(i+1, j-w[i])+v[i], dfs(i+1,j));
  
  return dp[i][j] = ans;

}

int main(){
  cin>>N>>W;
  rep(i,N) cin>>w[i]>>v[i];

  memset(dp, -1, sizeof(dp));
  cout<< dfs(0,W) <<endl;

}

Measured memory_bytes: 156672
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int MAX_N=550;
const int MAX_L=305;
ll ans=inf;
int n,len[MAX_N];
ll c[MAX_N],dp[MAX_N][MAX_L][2];
char s[MAX_N][MAX_L];
ll dfs(int id,int pos,int dir)
{
	if(pos>len[id]) return 0;
	if(~dp[id][pos][dir]) return dp[id][pos][dir];
	ll &v=dp[id][pos][dir];
	v=inf;
	bool flag=true;
	if(!dir){ for(int j=pos,k=len[id];j<k;j++,k--) if(s[id][j]!=s[id][k]) {flag=0; break;} } 
	else{ for(int j=pos,k=1;j>k;j--,k++) if(s[id][j]!=s[id][k]) {flag=0; break;} } 

	if(flag) return dp[id][pos][dir]=0;

    for(int i=1,j,k;i<=n;i++) {//???????????
        flag=1;
        if(!dir) {
            for(j=pos,k=len[i];j<=len[id]&&k>=1;j++,k--)
                if(s[id][j]!=s[i][k]) {flag=0; break;}
            if(flag) {
                if(k<1) v=min(v,c[i]+dfs(id,j,0));
                else v=min(v,c[i]+dfs(i,k,1));
            }
        }
        else {
            for(j=pos,k=1;j>=1&&k<=len[i];j--,k++)
                if(s[id][j]!=s[i][k]) {flag=0; break;}
            if(flag) {
                if(j<1) v=min(v,c[i]+dfs(i,k,0));
                else v=min(v,c[i]+dfs(id,j,1));
            }
        }
    }
	return v;
}
int main()
{
 	scanf("%d",&n); memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1),scanf("%lld",&c[i]),len[i]=strlen(s[i]+1);
    for(int i=1;i<=n;i++) 
		ans=min(ans,c[i]+dfs(i,1,0));
    printf("%lld\n",ans==inf?-1:ans);return 0;
	return 0;
}


Measured memory_bytes: 6416
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

B,A,D,C= inputIL()

a = (D+(A-1))//A
c = (B+(C-1))//C

if a<=c:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 72812
#include<bits/stdc++.h>
using namespace std;
bool zs(int n)
{
	for(int i=2;i*i<=n;++i)
		if(n%i==0)
			return false;
	return true;
}
bool hw(int n)
{
	int m=0,k=n;
	while(k!=0)
	{
		m=m*10+k%10;
		k/=10;
	}
	if(m==n)
		return true;
	return false;
}
int main()
{
	int n,hh=0,hhh=0;
	string s;
	cin>>n>>s;
	for(int i=0;i<=n;i++)
	{
		if(s[i]=='I')
			++hh;
		if(s[i]=='D')
			--hh;
		hhh=max(hhh,hh);
	}
	cout<<hhh;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
int main()
{
    int m,n,i,j,ii,jj,q,mm[105][105],nn[105][105],a,b[10005],bb,c[105];
    while(~scanf("%d%d",&m,&n))
    {
        memset(mm,0,sizeof(mm));
        memset(nn,0,sizeof(nn));
        scanf("%d",&q);
        bb=0;
        for(i=1; i<=q; i++)
        {
            scanf("%d",&a);
            for(j=bb; j<bb+a; j++)
            {
                b[j]=i;
            }
            bb+=a;
        }
        for(i=0; i<m; i++)
        {
            for(j=0; j<n; j++)
            {
                mm[i][j]=b[i*n+j];
            }
            for(j=0; j<n; j++)
            {
                if(i%2==0)
                {
                    nn[i][j]=mm[i][j];
                }
                if(i%2==1)
                {
                    nn[i][j]=mm[i][n-1-j];
                }
            }
        }
        for(i=0; i<m; i++)
        {
            for(j=0; j<n-1; j++)
            {
                printf("%d ",nn[i][j]);
            }
            printf("%d\n",nn[i][n-1]);
        }
    }
    return 0;
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

struct UfTree{
    vi parent;
    vi num;

    UfTree(int n){
        rep(i,n){
            parent.push_back(i);
            num.push_back(1);
        }
    }

    int find(int a){
        if(parent[a]==a){
            return a;
        }else{
            parent[a]=find(parent[a]);
            return parent[a];
        }
    }

    int getn(int a){
        if(parent[a]==a){
            return num[a];
        }else{
            parent[a]=find(parent[a]);
            return num[parent[a]];
        }
    }

    void unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b)return;

        parent[b]=a;
        num[a]+=num[b];
    }

    bool same(int a, int b){
        return find(a)==find(b);
    }

};

int main(){

    int n,m,k;
    cin>>n>>m>>k;

    UfTree con(n);

    vi fri(n);

    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        fri[a]++;
        fri[b]++;
        con.unite(a,b);
    }

    vi ans(n);
    rep(i,n){
        ans[i]=con.getn(i)-1-fri[i];
    }

    rep(i,k){
        int c,d;
        cin>>c>>d;
        c--;
        d--;
        if(con.same(c,d)){
            ans[c]--;
            ans[d]--;
        }
    }

    rep(i,n){
        cout<<ans[i]<<"\n";
    }

    return 0;
}

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll unsigned long long int
#define mp make_pair
#define pb push_back
bool sortbysec(pair <int, int> &a, pair <int, int> &b)
{
	return (a.second<b.second);
}
int main()
{
	SPEED
	int n, a, b;
	cin >> n;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; ++i)
	{
		cin >> a >> b;
		v.pb(mp(a,b));
	}
	sort(v.begin(), v.end(), sortbysec);
	int time = 0;
	for (int i = 0; i < n; ++i)
	{
		time += v[i].first;
		if (time>v[i].second)
		{
			cout << "No" << '\n';
			return 0;
		}
	}
	cout << "Yes" << '\n';
	return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){return modpow(x,mod-2);}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double d;
    cin>>d;
    double pi=3.14159265358979323846264338;
    printf("%.12lf\n",d*2*pi);
    return 0;
}


Measured memory_bytes: 3812
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int l,r,d,i,nr;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>l>>r>>d;
	for(i=l;i<=r;i++)if(i%d==0)nr++;
	cout<<nr<<endl;
	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  if(n<1000){cout<<"ABC"<<endl;return 0;}
  if(n<1999){cout<<"ABD"<<endl;return 0;}
  return 0;
}

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

int main()
{
    long int n,i,j,p,d;
    cin>>n;
    int matches[n+1][n];
    
    for(i=1;i<=n;++i){
        for(j=0;j<n-1;++j){
           scanf("%d",&matches[i][j]);   
        }
    }
    
    int cnt=0;
  
    int target = (n*(n-1))/2;
    vector<int>nms(n+1,0);
    
    for(d=1;d<=target;++d){
        
        bool flag = false;
        vector<bool>mark(n+1,false);
        
        for(p=1;p<n;++p){
            
             if(nms[p]>=n-1  || mark[p])
                 continue;
            
             int p1 = matches[p][nms[p]];
            
             if(mark[p1])
                 continue;

             if(matches[p1][nms[p1]] == p){
                 flag = true;
                 ++nms[p];
                 ++nms[p1];
                 mark[p1]=true;
                 mark[p]=true;
                 ++cnt;
             }
            
            if(cnt>=target){
                printf("%d",d);
                return 0;
            }
            
        }
        
        if(!flag)
            break;
     
    }
    
    for(i=1;i<=n;++i){
        if(nms[i]!=(n-1)){
            printf("-1");
            return 0;
        }
    }
    printf("%d",d);
}

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

using namespace std;

typedef long long ll;

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

	ll x;
	cin >> x;

	for(ll b = 1; b <= 1e4; b++){
		for(ll a = -b; a < b; a++){
			if(b * b * b * b * b - a * a * a * a * a == x){
				cout << b << " " << a << endl;
				return 0;
			}
		}
	}

}


Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
using namespace std;

const int INF = 1 << 28;
int cur[1710][1710], nxt[1710][1710], T[60];
int main() {
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        cin >> T[i];
    }

    int sum = 0;
    set< tuple<int, int> > vec;
    vec.emplace(0, 0);
    fill(cur[0], cur[1700], INF);
    fill(nxt[0], nxt[1700], INF);
    cur[0][0] = 0;
    for(int i=0; i<N; i++) {
        set< tuple<int, int> > nvec;
        for(auto e : vec) {
            int v[3] = {}; tie(v[0], v[1]) = e; v[2] = cur[v[0]][v[1]];
            // fprintf(stderr, "dp[%d][%d][%d] = %d\n", i, v[0], v[1], v[2]);
            for(int k=0; k<3; k++) {
                v[k] += T[i];
                
                int nv[3] = {v[0], v[1], v[2]};
                sort(nv, nv + 3);
                // fprintf(stderr, "nv = %d\n", nv[2]);
                nxt[nv[0]][nv[1]] = min(nxt[nv[0]][nv[1]], nv[2]);
                nvec.emplace(nv[0], nv[1]);

                v[k] -= T[i];
            }
            cur[v[0]][v[1]] = INF;
        }
        swap(nxt, cur);
        swap(vec, nvec);
    }

    int ans = INF;
    for(int i=0; i<1700; i++) {
        for(int j=0; j<1700; j++) {
            ans = min(ans, cur[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}



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

int main () {
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> x(m);
  vector<int> y(m);
  vector<vector<int> > ruiseki(n+1, vector<int> (n+1));
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      ruiseki[i][j] = 0;  
    }  
  }
  for (int i = 0; i < m; i++) {
    cin >> x[i] >> y[i];  
    ruiseki[x[i]][y[i]]++;
  }

  // 累積和を作っておく.
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      if (j != 0) { 
        ruiseki[i][j] = ruiseki[i][j] + ruiseki[i][j-1];  
      } 
    }  
  } 
  vector<int> qx(q);
  vector<int> qy(q);
  for (int i = 0; i < q; i++) {
    cin >> qx[i] >> qy[i];  
  }

  for (int i = 0; i < q; i++) {
    int answer = 0;
    for (int j = qx[i]; j <= qy[i]; j++) {
      if (j == 0) {
        answer = answer + (ruiseki[j][qy[i]]);
      } 
      else {
        answer = answer + (ruiseki[j][qy[i]] - ruiseki[j][j-1]);  
      }
    }
    cout << answer << endl;
  }
    
}

Measured memory_bytes: 4224
N = int(input())
S = list(input())

cnt = 0
S1 = list(set(S[:-2]))
for s1 in S1:
    i1 = S.index(s1)
    SS = S[i1+1:-1:]
    S2 = list(set(SS))
    for s2 in S2:
        i2 = S[i1+1:].index(s2) + i1+1
        SSS = S[i2+1::]
        S3 = set(SSS)
        cnt += len(S3)

print(cnt)


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

using namespace std;


#define PI 3.14159265
#define int long long



main(){


	int n; cin >> n;

	string s, t;

	cin >> s >> t;


	for(int i = 0; i < n; i++){
		cout << s[i] << t[i];
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,a,n) for(int i=a; i<(n); i++)
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int main(){

	int m,t,p,r;
	while( cin >> m >> t >> p >> r, m|t|p|r ){
		int sumtime[t+1];
		int ac[t+1];
		int wrong[t+1][p+1];
		int num[t+1];

		rep(i,t+1){
			rep(j,p+1){
				wrong[i][j] = 0;
			}
			ac[i]=0;
			sumtime[i] = 0;
			num[i] = i;
		}
		rep(k,r){
			int tmpm,tmpt,tmpp,tmpj;
			cin >> tmpm >> tmpt >> tmpp >> tmpj;
			if(tmpj) wrong[tmpt][tmpp]++;
			else{
				sumtime[tmpt] += tmpm + wrong[tmpt][tmpp] * 20;
				ac[tmpt] ++;
			}
		}
//		rep(i,t) cout << "ac=" <<ac[i] << endl;
		for(int i = 1; i < t;i++){
//		reps(i,1,t-1){
			for(int j = i+1; j <= t;j++){
	//		reps(j,i+1;t){
				if(ac[i] < ac[j] || (ac[i]==ac[j] && sumtime[i]> sumtime[j]) ||
				 (ac[i]==ac[j] && sumtime[i] == sumtime[j] && num[i] < num[j])){
					swap(ac[i],ac[j]);
					swap(sumtime[i],sumtime[j]);
					swap(num[i],num[j]);
				}
			}
		}
		for(int i = 1; i < t;i++){
//		reps(i,1,t-1){
			if(ac[i] == ac[i+1] && sumtime[i] == sumtime[i+1]){
				cout << num[i] << "=";
			}
			else{
				cout << num[i] << ",";
			}
		}
		cout << num[t] << endl;

	}
	return 0;
}

Measured memory_bytes: 3036
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
typedef long long ll;

int main() {
    #ifndef LOCAL
        fastIO;
    #endif
    int s,w;
    cin >> s >> w;
    if(s>w) cout << "safe" << endl;
    else cout << "unsafe" << endl;
}


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

int main() {
	int N;
	cin.tie(NULL);
	cin >> N;
	vector<LL> A(N, 0), B(N, 0);
	LL sumall = 0;
	for(int i=0; i<N; i++) {
		cin >> A[i];
		sumall += A[i];
	}
	for(int i=0; i<N; i++) {
		cin >> B[i];
		sumall -= B[i];
	}
	LL sum = 0, ans = 0;
	priority_queue<LL> pq;
	for(int i=0; i<N; i++) {
		sum += A[i] - B[i];
		LL cur = sumall - sum;
		ans += abs(cur);
		if(cur<=0) {
			pq.push(0);
			continue;
		}
		
		if(cur > sumall) cur = sumall;
		pq.push(-cur);
		pq.push(-cur);
		ans += pq.top();
		pq.pop();
		
	}
	cout << ans << endl;
	return 0;
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

bool f[100005];
int c[100005];

void init(){
    rep(i,100005){
        f[i] = true;
        c[i] = 0;
    }
}

int main()
{
    init();
    f[0] = f[1] = false;
    // エラトステネスの篩にかけて素数のみをtrueとする
    for(int i=2; i<=100000; i++){
        if(f[i] == true){
            int j = i + i;
            while(j<=100000){
                f[j] = false;
                j = j + i;
            }
        }
    }
    // 2017に似た数をカウントする
    for(int i=3; i<=100000; i++){
        if(f[i] && f[(i+1)/2]) c[i] = c[i-1]+1;
        else c[i] = c[i-1];
        // cout << c[i] << endl;
    }

    // 入力値を読み込み
    
    int Q; cin >> Q;
    rep(_, Q){
        int l, r; cin >> l >> r;
        cout << c[r] - c[l-1] << endl;
    }
    
}

Measured memory_bytes: 1152
void main() {
	auto ip = readAs!(ulong[]), A = ip[0], B = ip[1], C = ip[2];
	if(A % 2 == 0 || B % 2 == 0 || C % 2 == 0) writeln(0);
	else writeln(min(A*B, B*C, C*A));
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
main :: IO ()
main = do
       [x,y] <- (map read . words) <$> getLine
       putStrLn $ solve x y
       
solve :: Int -> Int -> String
solve x y | fold [0..x] y False == True = "Yes"
          | otherwise        = "No"

fold :: [Int] -> Int -> Bool -> Bool
fold _ _ True = True
fold [] _ False = False 
fold (x'@(x:xs)) y False | 2*x + 4*((last x') - x) == y = fold xs y True
                         | otherwise                    = fold xs y False

Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 3e3+5;
const lli INF = 1e18+10;
const lli MOD = 200003;

vi m;
vi primes(1,2);
vector<vector<ld>>nk;
void sieve(){
	m = vi(N+1,0);
	for(int i = 4; i<N; i+=2)m[i]=1;
	for(int i = 3; i*i<=N; i+=2)if(!m[i])for(int j = i*i; j<N; j+=i)m[j]=1;
	for(int i = 3; i<N; i+=2)if(!m[i])primes.pb(i);
}

void pascal(){
	nk =vector<vector<ld>>(N,vector<ld>(N,0.0));
	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;
	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];
}

lli gcd(lli a, lli b){return (b?gcd(b,a%b):a);}

lli lcm(lli a, lli b){
	if(a<b)swap(a,b);
	lli c = gcd(a,b);
	a/=c;
	return a*b;
}

int popcount(lli x) { return __builtin_popcountll(x); }

lli poww(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = res * a;
		a = a*a;
		b/=2;
	}
	return res;
}

lli powm(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = (res * a)%MOD;
		a = (a*a)%MOD;
		b/=2;
	}
	return res;
}

bool isPrime(lli x){
	if(x==1)return 0;
	for(auto i:primes){
		if(i*i>x)return 1;
		if(x%i==0)return 0;
	}
	return 1;
}

// ---- コーディングはここから！ ('-')7
lli dp[N][N][4];
int main(){_
	lli r,c,k; cin>>r>>c>>k;
	vvl v(r, vl(c,0));
	fore(i,0,k){
		lli rr, cc, kk; cin>>rr>>cc>>kk; v[rr-1][cc-1]=kk;
	}
	fore(i,0,N)fore(j,0,N)fore(k,0,4)dp[i][j][k]=-1;
	auto f=[&](auto f, int rr, int cc, int id)->lli{
		if(cc==c)return 0;
		if(rr==r)return 0;
		if(dp[rr][cc][id]!=-1)return dp[rr][cc][id];
		lli mx = 0;
		if(v[rr][cc] and id<3)mx = max(v[rr][cc] + f(f,rr,cc+1,id+1),mx);
		if(v[rr][cc] and id<3)mx = max(v[rr][cc] + f(f,rr+1,cc,0),mx);
		mx = max(f(f,rr,cc+1,id),mx);
		mx = max(f(f,rr+1,cc,0),mx);
		return dp[rr][cc][id]=mx;
	};
	cout<<f(f,0,0,0)<<ENDL;



}


Measured memory_bytes: 356648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
struct node{
	int x,y;
}a[N],b[N]; 
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)
			cin>>a[i].x>>a[i].y;
		for(int i=1;i<=m;i++)
			cin>>b[i].x>>b[i].y;
		for(int i=1;i<=n;i++)
		{
			ll ans=1e9;
			ll pos=0;
			for(int j=1;j<=m;j++)
			{
				ll dis=abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y);
				if(dis<ans)
				{
					ans=dis;
					pos=j;
				}
				//cout<<dis<<endl;
			}
			cout<<pos<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
inputs = input().split(" ")
stack = []

for str in inputs:
  if str.isdigit():
    stack.append(int(str))
  else:
    b = stack.pop()
    a = stack.pop()
    if str == '+':
      stack.append(a + b)
    elif str == '-':
      stack.append(a - b)
    elif str == '*':
      stack.append(a * b)

print(stack.pop())


Measured memory_bytes: 5596
<?php
  $k = trim(fgets(STDIN));
  $num = explode(" ", trim(fgets(STDIN)));
  $x = floor($num[0]/$k);
  if($num[0] % $k == 0 || $k * ($x + 1) <= $num[1]){
    echo "OK";
  } else {
    echo "NG";
  }
?>

Measured memory_bytes: 16120
// Code by Nguyen Huu Lam
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long LL;

#define y0 Sword_Art_Online
#define y1 Your_lie_in_April
#define yn Darling_in_the_Franxx
#define tm Plastic_Memories
#define lr Charlotte
#define norm Weathering_with_you
#define left Violet_Evergarden
#define have Date_a_live
#define ends Your_name
#define prev Five_centimeters_per_second
#define hash Silent_voice
#define endl "\n"

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

LL Rand(LL l, LL h){
    return uniform_int_distribution<LL>(l, h)(rng);
}

template <typename T> void read(T &t){
    t = 0; char ch = getchar(); int f = 1;
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    do { (t *= 10) += ch - '0'; ch = getchar(); } while (isdigit(ch)); t *= f;
}

const LL MaxN = 1 + 2e5;

LL n, a[MaxN], k;

bool Check(LL val){
    LL cnt = 0;
    for(int i = 0 ; i < n ; ++i)
    cnt += (a[i] - 1) / val;
    return cnt <= k;
}

void InOut(){
    #define TASK "ABC"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
}

int main(){
    // InOut();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    LL l = 1, r = 1e9;
    while(l < r){
        LL tg = (l + r - 1) / 2;
        if(!Check(tg)) l = tg + 1;
        else r = tg;
    }
    cout << l << endl;

    return 0;
}

Measured memory_bytes: 5112
//Author: Fuadul Hasan(fuadul202@gmail.com)
	//BSMRSTU,Gopalganj
	#include<bits/stdc++.h>
	using namespace std;int tc = 1;
	#define happy ios::sync_with_stdio(false);
	#define coding  cin.tie(0);
	#define mp make_pair
	#define ll long long
	#define Pi atan(1)*4
	#define pb  push_back
	#define vpr vector<pr> 
	#define pr pair<int, int> 
	#define vi std::vector<int>
	#define vll std::vector<ll>
	#define YES printf("YES\n");
	#define NO printf("NO\n");
	#define Yes printf("Yes\n");
	#define No printf("No\n");
	#define all(n) n.begin(),n.end()
	#define point(x) setprecision(x)
	#define Test printf("Case %d: ",tc++);
	#define Unique(c) (c).resize(unique(all(c))-(c).begin())
	#define vout(v) for (auto z: v) cout << z << " "; cout << endl;

	const int M = 1e9 + 7;
	const ll  Inf = (ll)2e18 + 5;
	const int N   = 2e5 + 5;

	int solve() 
	{
		//happy coding

		ll n,m;
		cin>>n>>m;
		ll a[n+1];
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		ll cnt = 0;
		std::map<ll, bool> vis;
		for(int i=0;i<m;i++){
			ll x,y;
			cin>>x>>y;
			if(a[x]>a[y]&&!vis[y]){
				vis[y] = 1;
			}else if(a[x]<a[y]&&!vis[x]){
				 vis[x] = 1;
			}else if(a[x]==a[y]){
				if(vis[x]==0||vis[y]==0)
					//cnt++;
				vis[x] = 1;
				vis[y] = 1;
			}
		}
		for(int i=1;i<=n;i++){
			if(vis[i]==0){
				cnt++;
			}
		}
		cout<<cnt<<endl;
		
		return 0;
	}
	int main(){
		int test = 1;
		//scanf("%d", &test);
		while (test--)solve();return 0;
	}

Measured memory_bytes: 10676