akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let h = get!(usize);
    let w = get!(usize);
    let n = get!(usize);

    let mx = max!(h,w);
    if n % mx == 0 {
        println!("{}", n/mx);
    } else {
        println!("{}", n/mx+1);
    }
}


Measured memory_bytes: 8572
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

int main()
{
    int N, X, i;
    cin >> N >> X;
    vector<int> L(N), sum(N + 1);
    sum.at(0) = 0;
    for (i = 0; i < N; i++)
    {
        cin >> L.at(i);
        sum.at(i + 1) = sum.at(i) + L.at(i);
        if(sum.at(i + 1) > X) break;
    }
    cout << i + 1 <<endl;
    return 0;
}

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

struct weighted_union_find {
    long long N; // 頂点数
    long long M; // 連結成分の数
    std::vector<long long> parent; // i の直接の親
    std::vector<long long> size; // i を含む連結成分のサイズ
    std::vector<long long> weight; // i -> parent[i] の重み
    
    // ===============================================================
    
    weighted_union_find(long long n) : N(n), M(n) {
        parent.resize(n, -1);
        size.resize(n, 1);
        weight.resize(n, 0);
    }
    
    // ===============================================================
    
    long long weight_sum_to_root(long long i) {
        if (parent[i] == -1) return 0;
        else return weight[i] + weight_sum_to_root(parent[i]);
    }
    
    long long root(long long i) {
        if (parent[i] == -1) return i;
        long long x = root(parent[i]);
        weight[i] += weight[parent[i]];
        return parent[i] = x;
    }
    
    bool is_united(long long i, long long j) {
        return (root(i) == root(j));
    }
    
    long long dist(long long i, long long j) {
        if (!is_united(i, j)) return LLONG_MAX;
        else return weight_sum_to_root(j) - weight_sum_to_root(i);
    }
    
    // false : detected confliction
    bool unite(long long i, long long j, long long w) {
        w += weight_sum_to_root(i) - weight_sum_to_root(j);
        i = root(i); j = root(j);
        if (i == j) return (w == 0);
        if (size[i] < size[j]) {
            std::swap(i, j);
            w *= -1;
        }
        parent[j] = i;
        size[i] += size[j];
        weight[j] = w;
        return true;
    }
};

int main() {
    long long n, q;
    std::cin >> n >> q;
    weighted_union_find uf(n);
    
    bool flag = true;
    while (q--) {
        long long l, r, d;
        std::cin >> l >> r >> d;
        l--; r--;
        if (!uf.unite(l, r, d)) flag = false;
    }
    
    std::cout << (flag?"Yes":"No") << std::endl;
}

Measured memory_bytes: 5644
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define mod ((ull)(1e9)+7)
#define MAX ((ull)(1e9)+1)

int main(){
	string s;
	cin >> s;
	int max=0;
	for(int i=0; i<s.length(); i++){
		int l=0;
		for(int j=i; j<s.length(); j++){
			if(s[j]!='A' && s[j]!='C' && s[j]!='G' && s[j]!='T') break;
			l++;
		}
		if(max<l) max=l;
	}
	cout << max << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int INF=-2000000000;
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int minn=p[0];
  int cnt=0;
  rep(i,n){
    minn=min(p[i],minn);
    if(minn>=p[i]) cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <numeric>
typedef long long int ll;
using namespace std;
int main(){
	int a,b;
	string x,s;
	vector<string> S;
	cin >> a>>b;
	for(int i=0;i<a;i++){
		cin>>x;
		S.push_back(x);
	}
	sort(S.begin(),S.end());
	for(int i=0;i<a;i++){
		s=s+S[i];
	}
	cout<<s<<endl;
	return 0;
}
	


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

struct S{
	int x1,y1,x2,y2;
	string name;
};

int main()
{
	int n;
	while(cin>>n,n)
	{
		int h,w; cin>>h>>w;
		vector<string> name(n);
		map<string,vector<S> > button;
		
		cin.ignore();
		
		rep(i,n)
		{
			int k;
			string str;
			getline(cin,str);
			int p=str.rfind(" ");
			
			name[i]=str.substr(0,p);
			stringstream(str.substr(p))>>k;
			
			rep(j,k)
			{
				S s;
				string str; getline(cin,str);
				
				int p=0;
				rep(it,4)p=str.find(" ",p+1);
				s.name=str.substr(p+1);
				
				stringstream(str.substr(0,p))>>s.x1>>s.y1>>s.x2>>s.y2;
				button[name[i]].pb(s);
			}
		}
		
		int m; cin>>m;
		vector<string> buffer; int cur=0;
		buffer.pb(name[0]);
		
		rep(i,m)
		{
			string op; cin>>op;
			if(op=="show")
			{
				cout<<buffer[cur]<<endl;
			}
			else if(op=="click")
			{
				int x,y; cin>>x>>y;
				fr(it,button[buffer[cur]])if(it->x1<=x&&x<=it->x2&&it->y1<=y&&y<=it->y2)
				{
					buffer.erase(buffer.begin()+cur+1,buffer.end());
					buffer.pb(it->name);
					cur++;
					break;
				}
			}
			else if(op=="back")
			{
				if(cur>0)cur--;
			}
			else if(op=="forward")
			{
				if(cur<buffer.size()-1)cur++;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
import java.util.*;

//くそコード
class Main{
  public static void main(String[] args){
    try(Scanner sc = new Scanner(System.in)){
      int n = Integer.parseInt(sc.nextLine());
      //int a[] = new int[n];
      Integer a[] = new Integer[n];
      for(int i = 0; i < n; i++){
        a[i] = Integer.parseInt(sc.next());
      }
      int Alice = 0;
      int Bob = 0;
      Arrays.sort(a, Collections.reverseOrder());
      
      for(int i = 0; i < n; i++){
        if((i % 2) == 0){
          Alice = Alice + a[i];
        }else{
          Bob = Bob + a[i];
        }
      }
      System.out.println(Alice - Bob);
    }
  }
}
          
      

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

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        //Solve();
        return;
    }

    public static string Solve()
    {
        long[] input = ReadLongs();
        long A = input[0], B = input[1], C = input[2], D = input[3];
        long p = Lcm(C, D);
        long ans = B - A + 1 - (Qu(A, B, C) + Qu(A, B, D) - Qu(A, B, p));
        return ans.ToString();
    }

    public static long Qu(long a, long b, long c)
    {
        long min, max;
        min = (a % c == 0) ? a / c : a / c + 1;
        max = b / c;
        return Math.Max(max - min + 1, 0);
    }

    public static long Lcm(long a, long b)
    {
        return a * b / Gcd(a, b);
    }

    public static long Gcd(long a, long b)
    {
        if (a < b)
            // 引数を入替えて自分を呼び出す
            return Gcd(b, a);
        while (b != 0)
        {
            var remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


Measured memory_bytes: 13140
#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1<<30;
const int mod=1000000007;

int edge[100001];
bool used[100001];
ll cnt;
vector<int> v;
void dfs (int i){
  used[i]=true;
  v.push_back(i);
  cnt++;
  if(!used[edge[i]])dfs(edge[i]);
  }
    
  
int main(){
  int n;cin>>n;
  ll x[n];
  rep(i,n)cin>>x[i];
  rep(i,n-1)edge[i]=i;
  int m;
  ll k;
  cin>>m>>k;
  int a[m];
  rep(i,m){
    cin>>a[i];
    swap(edge[a[i]-2],edge[a[i]-1]);
    }
  rep(i,n-1)used[i]=false;
  int dist[n-1];
  rep(i,n-1){
    if(!used[i]){
      v.clear();
      cnt=0;
      dfs(i);
      ll r=k%cnt;
      rep(j,cnt){
        int fin=(j+r)%cnt;
        dist[v[j]]=x[v[fin]+1]-x[v[fin]];
        }
      }
    }
  ll ans=x[0];
  cout<<x[0]<<endl;
  rep(i,n-1){
    ans+=dist[i];
    cout<<ans<<endl;
    }
  return 0;
  }

Measured memory_bytes: 6904
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
LL mod=1000000007;
LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};




int main(){
    int n;cin >> n;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            ans += d[i]*d[j];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>

using namespace std ;

const int N=1e5+10 ;

int A[N] , B[N] , C[N] ;
int n ;

int main ()
{
	int i , res=0 ;
	scanf("%d",&n);
	for ( i=1 ; i<=n ; i++ ) scanf("%d",A+i);
	for ( i=1 ; i<=n ; i++ ) scanf("%d",B+i);
	for ( i=1 ; i<n ; i++ ) scanf("%d",C+i);
	for ( i=1 ; i<=n ; i++ )
	{
		res+=B[A[i]];
		if ( A[i]==A[i-1]+1 ) res+=C[A[i-1]];
	}
	printf("%d\n",res);
	return 0 ;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
	int n,i,f=0;
	long long a,t=1;

	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%lld",&a);
		if(a==0){
			printf("0");
			return 0;
		}
		else if(a>1000000000000000000/t){
			f=1;
			t=1;
		}
		t*=a;
	}
	if(f==1)
		printf("-1");
	else
		printf("%lld",t);
	return 0;
}

Measured memory_bytes: 1732
if __name__ == '__main__':
    A, B, K = map(int, input().split())

    satisfied_integers = set()
    for i in range(K):
        if A + i <= B:
            satisfied_integers |= {A + i}
            
        if A <= B - K + 1 + i:
            satisfied_integers |= {B - K + 1 + i}

    satisfied_integers = sorted(satisfied_integers)
    for v in satisfied_integers:
        print(v)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i]
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
const int maxN = 87;
int32_t main(){
    SPEED;
    int n;
    cin >> n;
    int dp[n];
    memset(dp, -1, sizeof(dp));
    dp[0] = 2;
    dp[1] = 1;
    for(int i = 2; i <= n; ++i){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n];
}

Measured memory_bytes: 3644
//srinivas
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
// using namespace __gnu_pbds;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define fr(x,in,n,r) for(x=in;x<n;x+=r)
#define ifr(x,n) for(x=0;x<n;x++)
#define dfr(x,n) for(x=n-1;x>=0;x--)
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define pof(a) pop_front(a)
#define pob(a) pop_back(a)
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
typedef long long ll;
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007

struct chash{ 
    ll operator()(ll x) const {return hash<ll>{}(x);}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt","r",stdin);
    ll a,b;
	cin>>a>>b;
	if(a>=13){
		cout<<b;
	}
	else{
		if(a>=6)
			cout<<b/2;
		else
			cout<<0;
	}
	return 0;
}

Measured memory_bytes: 256
# AGC020B - Ice Rink Game
def main():
    K, *A = map(int, open(0).read().split())
    if A.pop() != 2:
        print(-1)
        return
    mn, mx = 2, 3
    for i in A[::-1]:
        if i > mx:
            print(-1)
            return
        mx = mx // i * i + i - 1
        mn = ((mn + i - 1) // i) * i
    if mn > mx:
        print(-1)
    else:
        print(mn, mx)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14092
N,K = map(int,input().split())

def check(i,K):
    w = 0
    score = i
    while score < K:
        w += 1
        score = score * 2
    
    return w

output = []
x = 1 / 2    


for i in range(1, N + 1):
    dice = i
    output.append(x**(check(dice,K)))

    

print((1 / N) * sum(output))

Measured memory_bytes: 6296
#include<iostream>
#include<algorithm>

using namespace std;

int const N = 1e5 + 41;
long long const INF = 6e18;

int a[N], b[N], c[N], n, x;
long long ans, cur;

void read(){
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
	}
}

void solve(){
	if(n == 1){
		printf("%d\n",max(0, a[0] - x));
		return;
	}
	ans = INF;
	for(int i=0;i<n;++i){
		b[i] = a[i];
	}

	cur = 0;
	for(int i=1;i<n;++i){
		int sum = b[i] + b[i-1];
		int rem = sum - x;
		if(rem <= 0){
			continue;	
		}
		int mini = min(rem, b[i]);
		cur += mini;
		b[i] -= mini;
		rem -= mini;
		cur += rem;
	}
	ans = min(ans, cur);

	for(int i=0;i<n/2;++i){
		swap(a[i], a[n-1-i]);
	}
	for(int i=0;i<n;++i){
		b[i] = a[i];
	}

	cur = 0;
	for(int i=1;i<n;++i){
		int sum = b[i] + b[i-1];
		int rem = sum - x;
		if(rem <= 0){
			continue;	
		}
		int mini = min(rem, b[i]);
		cur += mini;
		b[i] -= mini;
		rem -= mini;
		cur += rem;
	}
	ans = min(ans, cur);
	
	printf("%lld\n",ans);
}

int main(){
	read();
	solve();







	return 0;
}

Measured memory_bytes: 1024
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int l, r, d;
	cin >> l >> r >> d;
	int ans = 0;
	for (int i = l; i <= r; ++i) {
		ans += i % d == 0;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3596
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int B = 300000+10;
const int N = 10000+10;
const int P = 26    +1;
int main()
{
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)==3)
    {
        int s=abs(n-a);
        int t=abs(n-b);

        if(s<t)printf("A\n");else printf("B\n");

    }
return 0;
}


Measured memory_bytes: 128
/*
 
 Author : Bisma
 
 */
#include<algorithm>
#include <assert.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define ll long long
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define ss(n) scanf("%s", n)
#define pii pair <int, int>
#define pll pair <long long, long long >
#define plp pair <int, pll >
#define pb push_back
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define ll long long 
#define sum(a,b) a=a+b
#define repn(a,b,c) for(int a = b ; a>=c ; a--)
#define mem(a, b) memset(a, (b), sizeof(a))



ll max(ll a , ll b){
  if(a>b) return a;
  return b;
}

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
}



struct wow
{
  ll last;
  ll now;
  ll cur;
};


bool co(wow a, wow b){
  if(a.last > b.last){
    return true;
  }

  return false;
}

int main(){
    
    fast();
  
    ll n = 5;

    wow a[6];

    rep(i,1,n){
      cin>>a[i].now;
      a[i].cur = a[i].now;
       ll lol = a[i].now % 10;
      if(lol == 0) lol = 10;
      a[i].last = lol;


      ll p = a[i].cur / 10;

      if(a[i].cur % 10 != 0) p+=1;

      a[i].now = 10*p;

      //cout<<i<<" :: "<<a[i].now<<" "<<p<<endl;

     
    }


    ll sum = 0;

    sort(a+1,a+n+1, co);

   // cout<<endl;

    rep(i,1,n){
     // cout<<a[i].now<<" "<<a[i].last<<endl;
      if(i==n){
        sum+=a[i].cur;
      }else{
        sum+=a[i].now;
      }
    }

    cout<<sum<<endl;

    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
//const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int n = (int)S.size();

    auto next = calcNext(S);

    vector<int> dp(n+1, 1<<29);
    vector<pair<char,int>> recon(n+1, {'?',n});
    dp[n] = 1;
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++){
            if(next[i][j] == n){
                if(dp[i] > 1) dp[i] = 1, recon[i] = {'a'+j, n};
            }
            else if(chmin(dp[i],dp[next[i][j] + 1] + 1)) recon[i] = {'a' + j, next[i][j] + 1};
        }
    }
    string ans = "";
    int idx = 0;
    while(idx < n){
        auto p = recon[idx];
        ans += p.first;
        idx = p.second;
    }
    cout << ans << endl;
}


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

bitset<50001> bs[50001];
vector<pair<int,int> > e;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,t;
	cin>>n>>m>>t;
	for(int i=0,u,v;i<m;i++){
		cin>>u>>v;
		e.emplace_back(u,v);
	}
	string ans;
	ans.assign(m,0);
	if(t==1){
		for(int i=1;i<=n;i++)	bs[i].reset(),bs[i].set(i);
		for(int j=m-1;j>=0;j--){
			int x=e[j].first,y=e[j].second;
			bs[x]|=bs[y];
			bs[y]|=bs[x];
		}
		bs[0].set();
		for(int i=1;i<=n;i++)	bs[0]&=bs[i];
		int r=0;
		for(int i=1;i<=n;i++)
			if(bs[0][i])
				r=i;
		if(r==0)
			cout<<-1<<endl;
		else{
			bs[0].reset();
			bs[0].set(r);
			for(int j=m-1;j>=0;j--){
				int x=e[j].first,y=e[j].second;
				if(bs[0][x])
					ans[j]='^';
				else
					ans[j]='v';
				bs[0][x]=bs[0][x]|bs[0][y];
				bs[0][y]=bs[0][y]|bs[0][x];
			}
			cout<<ans<<endl;
		}
	}
	else{
		if(n<=2)
			cout<<-1<<endl;
		else{
			int state[4]={0,1,2,3};
			for(int i=m-1;i>=0;i--){
				int x=e[i].first,y=e[i].second;
				if(x<=3&&y<=3){
					if(state[x]==state[y])
						ans[i]='^';
					else if(state[x]==state[6-x-y]){
						ans[i]='v';
						state[x]=state[y];
					}
					else{
						ans[i]='^';
						state[y]=state[x];
					}
				}
				else{
					if(x<=3)
						ans[i]='^';
					else
						ans[i]='v';
				}
			}
			cout<<ans<<endl;
		}
	}
}


Measured memory_bytes: 306804
#pragma target("avx")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define rep(i,b,e) for(ll i=b; i<e; i++)
#define be(vec) vec.begin(),vec.end()
#define print(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define scan(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

struct Combination{
        std::vector<ll> fac, finv, inv;

        Combination(int max=6e5): fac(max+1), finv(max+1), inv(max+1) {
                fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
                for(int i=2; i<=max; i++){
                        fac[i] = fac[i-1] * i % MOD;
                        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
                        finv[i] = finv[i-1] * inv[i] % MOD;
                }
        }

        ll C(int n, int r) const {
                if(n<0 or n<r) return 0;
                return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD;
        }
};

std::map<ll, ll> prime_factor(ll n){
        std::map<ll, ll> ret;
        for(ll i=2; i*i<=n; i++){
                while(n%i==0){
                        ret[i]++;
                        n /= i;
                }
        }
        if(n!=1) ret[n]++;
        return ret;
}

int main(){
	ll n, m;
	scanf("%ld %ld", &n, &m);

	ll ans = 1;
	Combination comb;
	for(P p: prime_factor(m)) {
		ll c = p.second;
		ans *= comb.C(c+n-1, n-1);
		ans %= MOD;
	}
	printf("%ld\n", ans);
	return 0;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

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


int main() {
    ll x; cin >> x;
    ll ans = 0;
    ans += x/500 * 1000;
    x %= 500;
    ans += x/5 * 5;
    co(ans);

    return 0;
}


Measured memory_bytes: 3572
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  ll N,K,M;
  cin >> N >> M >> K;
  for(int a=0;a<=M;a++)
    for(int b=0;b<=N;b++){
      if((a*N+b*M-2*a*b) == K){
        cout << "Yes" << endl;
        return 0;
      }
    }
  cout << "No" << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

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

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 256
while True:
  m = int(input())
  if m == 0:
    break

  nums = []
  for _ in range(m):
    a, b = map(int, input().split())
    lst = [a * i for i in range(b + 1)]
    nums.append(lst)
  
  """
  dp[x][y] ... x種類目まででyを作る場合の数
  dp[x][y] = sum(dp[x - 1][y - wk] for wk in nums[x])
  """
  
  def solve(n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
      dp[i][0] = 1
    for x in range(1, m + 1):
      for y in range(1, n + 1):
        dp[x][y] = sum([dp[x - 1][y - v] for v in nums[x - 1] if v <= y])
    print(dp[m][n])
    
  g = int(input())
  for _ in range(g):
    solve(int(input()))


Measured memory_bytes: 5648
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main(void) {
    int c[3][3] = {0};

    for (int y = 0; y < 3; y++) {
        cin >> c[y][0];
        cin >> c[y][1];
        cin >> c[y][2];
    }

    for (int i = 0; i < 3; i++) {
        int x, y, z;
        x = c[0][i] - c[0][(i + 1) % 3];
        y = c[1][i] - c[1][(i + 1) % 3];
        z = c[2][i] - c[2][(i + 1) % 3];
        if (!(x == y && y == z && z == x)) {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <functional>
#include <list>
#include <utility>
#include <map>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll, ll> Pll;
typedef pair<int, Pii > P1;

#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define mp1(a,b,c) P1(a,P(b,c))
#define get_arsize(a) (sizeof(a)/sizeof(a[0]))
const ll mod = 1000000007;
const double eps = 1e-10;
const int MAX = 200000;

int main() {
	int n;
	cin >> n;
  for(int i = 1; i < 10; ++i) {
    if (n % i == 0 && n / i < 10) {
      cout << "Yes" << endl;
      return 0;
    }
  }
	cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
// ABC087_C
#include <iostream>
#include <string>
#include <vector>
#include <iterator>  // std::prev(iter, n) n 個分デクリメントしたイテレータ
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define MIN(vec) min_element(vec.begin(), vec.end())  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(vec.begin(), vec.end())
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(vec.begin(), vec.end(), 0LL)  // 0 は初期値
#define pll pair<ll, ll>
#define F first
#define S second
const ll INF = 1LL<<60;  // 10^18

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N;
    cin >> N;
    vector< vector<ll> > vec(2, vector<ll>(N));
    REP(i, 2) {
        REP(j, N) cin >> vec[i][j];
    }
    
    // calculation
    ll res = -1, sum_up, sum_down;
    REP(i, N) {
        sum_up = accumulate(vec[0].begin(), next(vec[0].begin(), i+1), 0LL);
        sum_down = accumulate(next(vec[1].begin(), i), vec[1].end(), 0LL);
        res = max(res, sum_up+sum_down);
    }
    
    cout << res << "\n";
    
    return 0;
}

Measured memory_bytes: 256
totalPrograms, totalChannels = STDIN.gets.split(" ").map{|x| x.to_i }
program_times = []
totalPrograms.times {
    start, stop, channel = STDIN.gets.split( " " ).map{|x| x.to_f}
    start -= 0.5
    program_times << ['S', start, channel - 1]
    program_times << ['E', stop, channel - 1]
}

program_times.sort! {|t1, t2| t1[1] - t2[1]}

maxRecording = 0
recordingChannels = Array.new(30,0)
program_times.each { |t|
    if( t[0] == 'S' )
        recordingChannels[ t[2] ] += 1
    elsif( t[0] == 'E' )
        recordingChannels[ t[2] ] -= 1 if recordingChannels[ t[2] ] > 0
    end

    recording = recordingChannels.reduce( 0 ) { |cnt, v| v > 0 ? cnt + 1 : cnt }
    maxRecording = [ recording, maxRecording ].max
}
puts maxRecording



Measured memory_bytes: 45300
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	ll n, m;
	cin >> n >> m;
	auto fn = [](ll x) {
		return x * (x - 1) / 2;
	};
	cout << fn(n) + fn(m) << '\n';
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
// Useful constants
#define INF  (int)1e9
#define EPS   1e-9
#define MOD 1000000007ll
#define PI 3.14159
// for input-output
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
// iteration macros: have advantage of auto-casting and not recomputing arguments
#define REP(i, a, b) \
for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
#define TRvi(c, it) \
for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for (vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for (msi::iterator it = (c).begin(); it != (c).end(); it++)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
// input macro
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}
//output macro
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
// shortcut for data type
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define vvii vector<vii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define uset unordered_set
#define umap unordered_map
//--namespace
using namespace std;
//--useful function
ll gcd(ll a, ll b){ll temp;while (b > 0){temp = a%b;a = b;b = temp;} return a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
// --clock funtion
clock_t time_p=clock();
void TimeTaken()
{
    time_p=clock()-time_p;
    cerr<<"Completion time : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
// --solve function
void solve() {

}
//--main function
int main(){
	int n,sum=0;
	cin>>n;
  	vi v(n);
  REP(i,0,n-1)cin>>v[i];
  REP(i,0,n-1){
    REP(j,i+1,n-1){
      sum+=v[i]*v[j];
    }
  }
  cout<<sum;
  
	return 0;

//   TimeTaken();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, t;
    cin >> k >> t;
    int sum = 0, MAX = 0;
    vector<int> a(t);
    rep(i, 0, t){
        cin >> a[i];
        sum += a[i];
        chmax(MAX, a[i]);
    }
    cout << max(0LL, (MAX - (sum - MAX)) - 1) << endl;
}

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

const int INF = 1001001001;

int main() {
	vector<int> v(5);
	rep(i, 5) cin >> v[i];
	int last_order = 0;
	int r, tmp, last_order_num;
	rep(i, 5) {
		if (v[i]%10 != 0) r = v[i]%10;
		else continue;
		tmp = 10-r;
		if (tmp > last_order) {
			last_order = tmp;
			last_order_num = i;
		} else continue;
	}
	int ans = 0;
	rep(i, 5) {
		if (i == last_order_num) continue;
		if (v[i]%10 != 0) ans += ((v[i]+(10-1))/10)*10;
		else ans += v[i];
	}
	ans += v[last_order_num];
	cout << ans << endl;
	return 0;
}

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

string s;
int x, y;
const int OFFSET = 10000;
bitset<2*OFFSET+10> xx,yy;

void solve()
{
	const int n = s.length();
	int step = 0;
	bool f = true; // x axis
	bool fi = true;
	xx.set(OFFSET);
	yy.set(OFFSET);
	for(int i=0;i<=n;++i){
		if(i<n && s[i] == 'F') step++;
		else{
			auto& t = f ? xx : yy;
			if(fi) t<<=step;
			else t=(t<<step)|(t>>step);
			fi = false;
			step = 0;
			f = f?false:true;
		}
	}
	if(xx.test(x+OFFSET)&&yy.test(y+OFFSET)) cout<<"Yes\n";
	else cout<<"No\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> s;
	cin >> x >> y;
	solve();
	return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>

int main(void){
  int a,i=0;
  char S[100];
  a=scanf("%s",S);
  
  for(i=0; S[i]!='\0';i++){
  }
  
  for(int j=0; j<i;j++){
    S[j]=120;
  }
  
  printf("%s\n",S);

  return 0;
}
  

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/













using ld = long double;
ld a, b, c;
const ld EPS = 1e-14;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> a >> b >> c;

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







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

int main() {
  vector<bool> isprime_vec(100001);
  vector<int> primes;
  for (int i = 2; i <= 100000; i++) {
    bool isprime = true;
    for (int div : primes) {
      if (div * div > i) break;
      if (i % div == 0) {
        isprime = false;
        break;
      }
    }
    if (isprime) {
      primes.push_back(i);
      isprime_vec.at(i) = true;
    }
  }
  vector<int> s(100001);
  for (int i = 3; i <= 100000; i += 2) {
    if (isprime_vec.at(i) and isprime_vec.at((i + 1) / 2)) {
      s.at(i) = s.at(i - 2) + 1;
    } else {
      s.at(i) = s.at(i - 2);
    }
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    int sl = (l >= 2) ? s.at(l - 2) : 0;
    cout << s.at(r) - sl << endl;
  }
}


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

public class P
{
    public int x { get; set; }
    public int y { get; set; }
    public bool red { get; set; }
}

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var w  = setArray(n);
        var hs = new HashSet<P>();
        var count = 0;
        foreach (var x in w.OrderBy(y =>y.x))
            if (x.red) hs.Add(x);
            else
            {
                var t = hs.Where(z => z.x < x.x && z.y < x.y).OrderByDescending(z => z.y);
                if (t.Count() > 0) { hs.Remove(t.First()); count++; }
            }
        Console.WriteLine(count);
    }
    public static P[] setArray(int n)
    {
        var w = new P[2 * n];
        for (int i = 0; i < 2 * n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var a = int.Parse(line[0]);
            var b = int.Parse(line[1]);
            if (i < n) w[i] = new P { x = a, y = b, red = true };
            else w[i] = new P { x = a, y = b };
        }
        return w;
    }
}

Measured memory_bytes: 13652
#include<stdio.h>
#include<ctype.h>

int main() {
	//int i=0;
	char a[101],b[101],c[101];

	scanf("%s %s %s",a,b,c);
	char out[4];

	snprintf(out,4,"%c%c%c",a[0]-32,b[0]-32,c[0]-32);

	/*for (i = 0; i < 101;i++) {
		if(isupper(str[i]) !=0)*/
		printf("%s",out);
	//}

	return 0;

}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
long long dp[110][100010];


main(){
	int n,m,w[110],v[110];
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(w[i]<=j)
				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			}
		}
		cout<<dp[n][m]<<endl;
	}

Measured memory_bytes: 79360
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 998244353;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}




 



int main(void) {
  
 

 int n, k, c;
string s;
int m = 0;
int w = 0;

int p, q, u, v;

int f = -200100;
  
  cin >> n >> k >> c;
  cin >> s;

  vector<int> a(n+10,0), g(n+10), b(n+10,0), xx(n+10);
  vector<bool> r(n+10,false);

  

  for (int i = 1; i <= s.size(); i++) {
    if (m > 0) {
      a[i] = a[i - 1];
      m--;
    }
    else if (s[i - 1] == 'x') {
      a[i] = a[i - 1];
    }
    else if (s[i - 1] == 'o') {
      r[i] = true;
      a[i] = a[i - 1] + 1;
      m = c;
    }
  }
  
  for (int i = 1; i <= n; i++) {
    xx[i] = w;
    if (r[i]) {
      w = i;
      xx[i] = w;
    }
  }

  
  m = 0;
  for (int i = s.size(); i >= 1; i--) {
    if (m > 0) {
      b[i] = b[i + 1];
      m--;
    }
    else if (s[i - 1] == 'x') {
      b[i] = b[i + 1];
    }
    else if (s[i - 1] == 'o') {
      b[i] = b[i + 1] + 1;
      m = c;
    }
  }

  f = 0;
  for (int i = 1; i <= n; i++) {
    g[i] = f;
    if (s[i - 1] == 'o') f = i;
  }

  
  
  

  
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == 'x') continue;
    if (g[i] <= 0) p = 0;
    else p = a[g[i]];
    int e = xx[g[i]];
    if (e == 0) e = i + 1;
    else e = max(e + c + 1, i + 1);
    //cout << e << endl;
    if (e > n) q = 0;
    else q = b[e];
    //cout << "e = " << e << endl;
    //cout << i << " " << p << " " << q << " ";
    if (i - c - 1 <= 0) u = 0;
    else u = a[i - c - 1];
    if (i + c + 1 > n) v = 0;
    else v = b[i + c + 1];
    //cout << u + v << endl;
    if (p + q < k && u + v + 1 >= k) cout << i << endl;
  }
  return 0;
  
}


Measured memory_bytes: 4996
#include <iostream>

using namespace std;

const int MAXN = 110;
const int MAXK = 1e5 + 10;
const int MOD = 1e9 + 7;

long long a[MAXN];
long long dp[MAXK][MAXN];

int main()
{
    long long n, k;
    cin >> n >> k;

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

    for (int i = 0; i <= n; i++)
        dp[0][i] = 1;


    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++) {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
            if (i >= a[j - 1] + 1)
                dp[i][j] = (dp[i][j] - dp[i - a[j - 1] - 1][j - 1] + MOD) % MOD;
        }

    cout << dp[k][n];
    return 0;
}

Measured memory_bytes: 86144
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  s = InputLine.to_sa

  a = s[0].to_i
  bs = s[1].split('.')
  bs[1] = (bs[1] + '00')[0..1]
  b = bs.join('').to_i

  t = (a * b).to_s

  if t.size > 2 then
    t = t[0...t.size - 2]
  else
    t = 0
  end

  puts t
end

if self.to_s == 'main' then
  main(ARGV)
end

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

int main() {
  int W, A, B, C, D;
  cin >> W >> A >> C;
  if (A > C) swap(A, C);
  B = A + W;
  D = C + W;
  cout << ((C - B > 0) ? C - B : 0) << "\n";
}

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

using namespace std;

const int MX = 500000;

char s[MX + 1];

int f[MX + 1][27];
int g[MX + 1][20];

void prepare() {
	int n = strlen(s);
	for (int i = 0; i < n; i++) s[i] -= 'a';
	
	for (int i = 0; i < 27; i++) f[n][i] = n;
	
	for (int i = n - 1; i >= 0; i--) {
		f[i][s[i]] = i;
		
		for (int j = s[i] + 1; j < 27; j++) {
			f[i][j] = f[min(f[i][j - 1] + 1, n)][j - 1];
		}
		
		for (int j = 0; j < s[i]; j++) {
			int r = f[i][26];
			f[i][j] = f[min(r + 1, n)][j];
		}
	}
	
	for (int i = n; i >= 0; i--) {
		g[i][0] = f[i][26];
		for (int j = 0; j < 19; j++) g[i][j + 1] = g[min(g[i][j] + 1, n)][j];
	}
}

bool solve(int l, int r) {
	for (int i = 19; i >= 0; i--)
		if (g[l][i] < r)
			l = g[l][i] + 1;
	
	return f[l][26] == r;
}

int main() {
	int q;
	scanf("%s %d", s, &q);
	
	prepare();
	
	while (q--) {
		int l, r;
		scanf("%d %d", &l, &r);
		
		printf(solve(l - 1, r - 1) ? "Yes\n" : "No\n");
	}
	
	return 0;
}


Measured memory_bytes: 92928