akhauriyash/Code-Regression huggingface dataset:
n,m=map(int, input().split( ))
d = []
for _ in range(n):
    a,b = map(int, input().split( ))
    d.append((a,b))

d.sort()

tmp = m
ans = 0
for i in range(n):
    buy = min(tmp,d[i][1])
    tmp -= buy
    ans += buy*d[i][0]
    if not tmp:
        break

print(ans)

Measured memory_bytes: 53592
#include <stdio.h>
#include <string.h>
int main(int argc, const char * argv[]) {
    char string[100];
    gets(string);
    if (strcmp(string, "SUN") == 0) {
        printf("%d\n", 7);
    }
    if (strcmp(string, "SAT") == 0) {
        printf("%d\n", 1);
    }
    if (strcmp(string, "MON") == 0) {
        printf("%d\n", 6);
    }
    if (strcmp(string, "TUE") == 0) {
        printf("%d\n", 5);
    }
    if (strcmp(string, "WED") == 0) {
        printf("%d\n", 4);
    }
    if (strcmp(string, "THU") == 0) {
        printf("%d\n", 3);
    }if (strcmp(string, "FRI") == 0) {
        printf("%d\n", 2);
    }   
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int hiki,asi;
    cin>> hiki >>asi;
    int sa =asi-hiki*2;

    if (hiki*2<=asi && hiki*4>=asi && sa%2==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

}

Measured memory_bytes: 3636
#include<stdio.h>
int main(){
	int S,h,m,s;
	scanf("%d",&S);
	h = S / 3600;
	m = (S % 3600) / 60;
	s = (S % 3600) % 60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
#include<stdio.h>

int main(void) {
	int a, b;
	char op='a';

	while (op != '?') {
		scanf("%d %c %d", &a,&op,&b);
		//op = getchar();
		//scanf("%d", &b);

		if (op == '+')
			printf("%d\n", a + b);
		else if (op == '-')
			printf("%d\n", a - b);
		else if (op == '*')
			printf("%d\n", a*b);
		else if (op == '/')
			printf("%d\n", a / b);
		else
			break;
	}
	return 0;

}

Measured memory_bytes: 600
import sys
from collections import deque
n = int(input())
q = deque()
for i in range(n):
    c = sys.stdin.readline()[:-1]
    if c[0] == 'i':
        q.appendleft(c[7:])
    elif c[6] == ' ':
        try:
            q.remove(c[7:])
        except:
            pass
    elif c[6] == 'F':
        q.popleft()
    else:
        q.pop()
print(*q)

Measured memory_bytes: 71828
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const ll inf = 4523372036854775807;
const ld pi = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989;
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct S {//辺の情報を入れる変数
	int from, to, cost;
};
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld radian(ld a, ld b, ld c, ld d) {
	return sqrt(pow(a - c, 2) + pow(b - d, 2));
}
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int x, t;
	cin >> x >> t;
	cout << max(0LL, x - t) << endl;
	getchar(); getchar();
}

Measured memory_bytes: 256
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    int a,b,c;
    cin>>a>>b>>c;
    if(c/a-(b-1)/a>0) cout<<"OK";
    else cout<<"NG";
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>

using namespace std;

long long int pow(long long int x, long long int y) {
  long long int result = 1;
  for (long long int i = 0; i < y; ++i) {
    result *= x;
  }

  return result;
}

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

  int l = 0;
  for (long long int i = 1, v = 0, u = 26; i <= 13; ++i, v = u, u += pow(26, i)) {
    if (n <= u) {
      l = i;
      n -= v + 1;
      break;
    }
  }

  string ans = "";
  for (int i = 0; i < l; ++i) {
    char c = n%26 + 'a';
    n /= 26;
    ans = c + ans;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<i_i, int> p_i;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) {
        s << vv[i] << endl;
    }
    return s;
}

int main() {
    while (true) {
        int r, n;
        cin >> r >> n;
        if ( r == 0 ) { break; }
        map<int, int> maxh;
        rep (i, n) {
            int xl, xr, h;
            cin >> xl >> xr >> h;
            FOR (x, xl, xr) {
                maxh[x] = max(maxh[x], h);
            }
        }
        double mintime = 10000.0;
        FOR (x, -r+1, r) {
            double starth = sqrt(r*r - x*x) - r;
            int endh;
            if ( x < 0 ) {
                endh = maxh[x-1];
            } else if ( x == 0 ) {
                endh = min(maxh[-1], maxh[0]);
            } else {
                endh = maxh[x];
            }
            mintime = min(mintime, endh-starth);
        }
        printf("%f\n", mintime);
    }
    return 0;
}

Measured memory_bytes: 3164
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#define ll long long
#define s second
#define f first
const int MOD = 1e9+7;
using namespace std;

ll llmax(ll x, ll y){
	if (x > y) return x;
	return y;
}

ll llmin(ll x, ll y){
	if (x > y) return y;
	return x;
}

bool is_prime(int x){
	for (int i = 2; i*i <= x; i++){
		if (!(x%i)) return false;
	}
	return true;
}

ll gcd(ll x, ll y){
	if (y > x){
		ll temp = x;
		x = y;
		y = temp;
	}
	if (x%y) return gcd(y, x%y);
	return y; 
}


int main(){
	ll n, ans = 0;
	cin >> n;
	if (n%2){
		cout << 0 << endl;
		return 0;
	}
	for (ll i = 5; i <= n; i*=5){
		ans += n/(i*2);
	}
	cout << ans << endl;
	return 0;
}




Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
	
		try{
	BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));

	while(true){
    String input = buf.readLine();
	String[] strAry = input.split(" ");
    int H = Integer.parseInt(strAry[0]);
    int W = Integer.parseInt(strAry[1]);
	
	if(H == 0  && W == 0){
		break;
	}
	
	for (int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++){
			if((i == 0 || i == H-1) || (j ==0 || j == W-1)){
			System.out.printf("#");
				}else{
			System.out.printf(".");
			}
		}
		System.out.printf("\n");
	}
	System.out.printf("\n");
	}
} catch (Exception e) {

	System.out.println("????????????");
	
}
		 }
    }

Measured memory_bytes: 56852
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

from math import ceil
def main():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))

    def kaisu(long):
        return(sum([ceil(ae/long) - 1 for ae in a]))

    def bs_meguru(key):
        def isOK(index, key):
            if kaisu(index) <= key:
                return True
            else:
                return False
        ng = 0
        ok = max(a)
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok
    print(bs_meguru(k))

if __name__ == '__main__':
    main()



Measured memory_bytes: 31108
count = 0

def merge(array, left, mid, right):
  global count

  n1 = int(mid - left)
  n2 = int(right - mid)

  l = array[left:mid]
  r = array[mid:right]
  
  l.append(9999999999)
  r.append(9999999999)

  i, j = 0, 0

  for k in range(left, right):
    count += 1
    if l[i] <= r[j]:
      array[k] = l[i]
      i += 1
    else:
      array[k] = r[j]
      j += 1

def mergeSort(array, left, right):
  if left + 1 < right:
    mid = int((left + right) / 2)
    mergeSort(array, left, mid)
    mergeSort(array, mid, right)
    merge(array, left, mid, right)

n = int(input())
array = [int(i) for i in input().split()]
mergeSort(array, 0, n)
print(*array)
print(count)



Measured memory_bytes: 63700
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool bmp(string x ,string y){
	return x < y;
}
int main(){
	int n, l, i;
	cin >> n >> l;
	string a[n];
	for ( i = 0 ; i < n ; i++ ){
		cin >> a[i];
	}
	sort(a,a+n,bmp);
	for ( i = 0 ; i < n ; i++ ){
		cout << a[i];
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <unordered_map>
#define inputarr(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define prllarr(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" ";
#define pb push_back
#define ll long long
#define mod 1000000007
#define foi ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define in(n) scanf("%lld",&n);
#define in2(x,y) scanf("%lld %lld",&(x),&(y));
#define in3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define out(n) printf("%lld\n",n);
#define out2(x,y) printf("%lld %lld\n",x,y);
#define test(t)  ll t; in(t);while(t--)
#define set(arr,n,s) for(ll i=0;i<n;i++){arr[i]=s;}


ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1){res=(res*x)%p;} y=y>>1;x=(x*x)%p;}return res;}
ll modInverse(ll a,ll p){return power(a,p-2,p);}//used with feemat little

ll gcd(ll x,ll y){if(x==0 || y==0){return max(y,x);}return gcd(y%x,x);}
ll gcdExtended(ll a,ll b,ll &x,ll &y){if(a==0){x=0;y=1;return b;}ll x1,y1;ll gcd = gcdExtended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return gcd;}//o(log(b))
;
void prac(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   #endif 
}
ll n;
ll arr[21];
ll dp[1<<21];
ll solve(ll mask)
{
	if(mask==(1<<n)-1){
		return 1;
	}
	if(mask>=(1<<n))return 0;
	if(dp[mask]!=-1)return dp[mask];
	
	ll index=__builtin_popcount (mask);
	// cout<<index;
	ll ans=0;
	for(ll i=0;i<n;i++){
		// cout<<mask<<(1<<i)<<endl;
		// cout<<i<<(arr[index]&(1<<i)) <<((mask&(1<<i))==0LL)<<endl;
		if(arr[index]&(1<<i) && ((mask&(1<<i))==0LL)){
			
			ans+=solve(mask|(1<<i));
			ans%=mod;
		}
	}
	dp[mask]=ans;
	return ans;
}

int main() 
{
  	// prac();
  
    in(n)
    for(ll i=0;i<(1<<n);i++)dp[i]=-1;
    for(ll i=0;i<n;i++){
    	for(ll j=0;j<n;j++){
    		ll x;
    		in(x)
    		if(x){
    			arr[i]|=(1<<j);
    		}
    	}
    }

    ll ans=solve(0);
    //prllarr(arr,7)
    out(ans)




}
/*error-----
convert every int to long long eg-1LL
create array with proper analysis of problem constrain
check mod also
*/






Measured memory_bytes: 16640
import java.util.Scanner;

public class Main {

		public static void main(String[] args){
			
			Scanner sc = new Scanner(System.in);
			// 文字列の入力
			String str = sc.next();
			String[] strArray = str.split("");

			if(strArray[0].equals(strArray[1])){
				if(strArray[1].equals(strArray[2])){
					if(strArray[2].equals(strArray[3])){
					System.out.println("No");
					return;
					}
				}
			}

			
			if(strArray[0].equals(strArray[1])){
				if(strArray[2].equals(strArray[3])){
				    System.out.println("Yes");
		    	    return;
				}
			}else{
				if(strArray[0].equals(strArray[2])){
					if(strArray[1].equals(strArray[3])){
					    System.out.println("Yes");
			    	    return;
					}
				}else{
					if(strArray[0].equals(strArray[3])){
						if(strArray[1].equals(strArray[2])){
						    System.out.println("Yes");
				    	    return;
						}
					}						
				}
			}

			System.out.println("No");
    	    return;
			

		}
}


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


int main(){
  int A, B;
  cin >> A >> B;
  int ans = 0;
  for(int ii=A; ii<=B; ii++){
    string s_pre = to_string(ii);
    string s_post = s_pre;
    reverse(s_post.begin(), s_post.end());
    if(s_pre == s_post) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <array>
#include <queue>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<long long> x(m);
    for (int i=0; i<m; ++i){
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    vector<long long> diff(m-1);
    for (int i=0; i<m-1; ++i){
        diff[i] = x[i+1] - x[i];
        //cout << diff[i] << endl;
    }
    sort(diff.begin(), diff.end());
    long long ans = 0;
    if(n >= m){
        cout << 0 << endl;
    }
    else {
        for (int i=0; i<m-n; ++i){
            ans += diff[i];
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.push_back(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
int main(){
  ll i,x,N,M,ans=0;
  cin>>N>>M;
  vec v(N);
  rep(i,N){
    cin>>v[i];
    if(v[i]>M){
      ans+=v[i]-M;
      v[i]=M;
    }
  }
  rep1(i,N){
    x=v[i]+v[i-1];
    if(x>M){
      ans+=x-M;
      v[i]-=x-M;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
typedef struct E{
	int to, len;
	struct E *next;
}edge;
int N, d[1<<17];
edge G[1<<17], *nil;
void push(int i, int j, int k){
	edge *X = (edge*)malloc(sizeof(edge));
	(*X).to = j;
	(*X).len = k;
	(*X).next = G[i].next;
	G[i].next = X;
	return;
}
void dfs(int i){
	edge *x = G[i].next;
	while(x != nil){
		if(d[(*x).to] == -1){
			d[(*x).to] = d[i] ^ (*x).len & 1;
			dfs((*x).to);
		}
		x = (*x).next;
	}
	return;
}
int main(){
	scanf("%d", &N);
	for(int i=0; i<=N; i++){
		d[i] = -1;
		G[i].next = nil;
	}
	for(int i=1; i<N; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		push(a, b, c);
		push(b, a, c);
	}
	d[1] = 0;
	dfs(1);
	for(int i=1; i<=N; i++)printf("%d\n", d[i]);
	return 0;
}

Measured memory_bytes: 10812
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

int main() {
    ll N;
    cin >> N;
    cout << N * N * N << endl;
}



Measured memory_bytes: 888
// C - Vacation
#include <bits/stdc++.h>
using namespace std;
// void abcprn(int a, int b, int c){printf("%4d,%4d,%4d\n",a,b,c);}

int main(){
	int N; cin>>N;
	// cout<<"dp:A    B    C\n";//
	int A=0, B=0, C=0;
	while(N--){
		int a,b,c; cin>>a>>b>>c;
		a += B>C? B:C;
		b += C>A? C:A;
		c += A>B? A:B;
		A=a; B=b; C=c;
		// abcprn(A,B,C);//
	}
	cout<< max({A,B,C}) <<endl;
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

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

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VLL a(n);
  rep(i,n) cin >> a[i];
  int cnt = 0;
  rep(i,n){
    if(a[i] != i+1) cnt++;
  }
  if(cnt <= 2) cout << "YES" << "\n";
  else cout << "NO" << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
#define FOR(i,n,F) for(int i = n;i < F;i++)




int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int xs = x2 - x1;
	int ys = y2 - y1;
	int x3 = x2 - ys;
	int y3 = y2 + xs;
	cout << (x3) << " " << (y3) << " " << (x3 - xs) << " " << (y3 - ys) << "\n";

	return 0;
}


Measured memory_bytes: 256
/*
        _            _                  _            _       _     _         _   _          _          _             _        
       / /\         / /\               / /\         / /\    / /\  /\ \      /\_\/\_\ _     /\ \       /\ \     _    /\ \      
      / /  \       / /  \             / /  \       / / /   / / /  \ \ \    / / / / //\_\   \ \ \     /  \ \   /\_\ /  \ \     
     / / /\ \__   / / /\ \           / / /\ \__   / /_/   / / /   /\ \_\  /\ \/ \ \/ / /   /\ \_\   / /\ \ \_/ / // /\ \_\    
    / / /\ \___\ / / /\ \ \         / / /\ \___\ / /\ \__/ / /   / /\/_/ /  \____\__/ /   / /\/_/  / / /\ \___/ // / /\/_/    
    \ \ \ \/___// / /  \ \ \        \ \ \ \/___// /\ \___\/ /   / / /   / /\/________/   / / /    / / /  \/____// / / ______  
     \ \ \     / / /___/ /\ \        \ \ \     / / /\/___/ /   / / /   / / /\/_// / /   / / /    / / /    / / // / / /\_____\ 
 _    \ \ \   / / /_____/ /\ \   _    \ \ \   / / /   / / /   / / /   / / /    / / /   / / /    / / /    / / // / /  \/____ / 
/_/\__/ / /  / /_________/\ \ \ /_/\__/ / /  / / /   / / /___/ / /__ / / /    / / /___/ / /__  / / /    / / // / /_____/ / /  
\ \/___/ /  / / /_       __\ \_\\ \/___/ /  / / /   / / //\__\/_/___\\/_/    / / //\__\/_/___\/ / /    / / // / /______\/ /   
 \_____\/   \_\___\     /____/_/ \_____\/   \/_/    \/_/ \/_________/        \/_/ \/_________/\/_/     \/_/ \/___________/    
                                                                                                                              
*/
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 2000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(13)

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

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

  string s; cin >> s;
  string S = "";
  REP(i, s.size()-1){
    if(s[i] == 'B' and s[i+1] == 'C'){
      S += '#';
      i++;
    } else S += s[i];
  }
  cerr << S << endl;
  int combo = 0, ans = 0;
  REP(i, S.size()){
    if(S[i] != 'A' and S[i] != '#') combo = 0;
    else if(S[i] == 'A') combo++;
    else ans += combo;
  }
  cout << ans << endl;
}

Measured memory_bytes: 916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
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;}
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353


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

    // solution comes here

    ll N;
    cin >> N;
    matrix dp(N, vl(3));
    rep(i, N){
        ll a, b, c;
        cin >> a >> b >> c;
        dp[i][0]=a;
        dp[i][1]=b;
        dp[i][2]=c;
    }

    rep(i, N-1){
        dp[i+1][0] += max(dp[i][1], dp[i][2]);
        dp[i+1][1] += max(dp[i][2], dp[i][0]);
        dp[i+1][2] += max(dp[i][0], dp[i][1]);
    }

    cout << max({dp[N-1][0], dp[N-1][1], dp[N-1][2]}) << nl;
}

Measured memory_bytes: 5760
n=int(input())
ac=0
tle=0
wa=0
re=0
for _ in range(n):
    s=input()
    if s=='AC':
        ac+=1
    elif s=='WA':
        wa+=1
    elif s=='TLE':
        tle+=1
    else:
        re+=1
print('AC x {}'.format(ac))
print('WA x {}'.format(wa))
print('TLE x {}'.format(tle))
print('RE x {}'.format(re))


Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
struct fastio { fastio () { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } _io;
template<class T, class U> bool chmax(T& a, const U &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> bool chmin(T& a, const U &b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	long long n;
	std::cin >> n;
	
	std::vector<long long> a(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			a[j]++;
		}
	}
	
	long long ans = 0;
	for (long long i = 1; i <= n; i++) {
		ans += (i * a[i]);
	}
	
	std::cout << ans << '\n';
	
	return 0;
}

Measured memory_bytes: 81340
#include <iostream>
using namespace std;
#define REP(i, n) for (int i = 0; i <= n; ++i)
#define triREP(a, A, b, B, c, C) REP(a, A) REP(b, B) REP(c, C)

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int ans = 0;
  triREP(a,A,b,B,c,C) {
    int total = 500*a + 100*b + 50*c;
    if (total == X) ++ans;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Mod 1000000007
#define rep(i, l, r) for(int i = l; i <= r; ++i)
int n, cnt;
unordered_map <int, int> dp;
int read(){
    char c; int x = 0, f = 1;
    c = getchar();
    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int Inc(int a, int b){
    return (a += b) >= Mod ? a - Mod : a;
}
int dfs(int n){
    if(dp[n]) return dp[n];
    ++cnt;
    return dp[n] = Inc(Inc(dfs(n / 2), dfs((n - 1) / 2)), dfs((n - 2) / 2));
}
signed main(){
    n = read(), dp[0] = 1, dp[1] = 2;
    printf("%lld\n", dfs(n));
    return 0;
}


Measured memory_bytes: 3708
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int64_t const MOD = 1e9+7;

template<int64_t Prime>
struct mod_int {
  int64_t v_;
  mod_int(int64_t x=0) : v_(x) { normalize(); }
  void normalize() { ((v_ %= Prime) += Prime) %= Prime; }
  mod_int operator+=(mod_int const& r){ (v_ += r.v_) %= Prime; return *this; }
  mod_int operator-=(mod_int const& r){ (v_ += Prime - r.v_) %= Prime; return *this; }
  mod_int operator*=(mod_int const& r){ (v_ *= r.v_) %= Prime; return *this; }
  mod_int operator+(mod_int const& r) { mod_int res(*this); return res += r; }
  mod_int operator-(mod_int const& r) { mod_int res(*this); return res -= r; }
  mod_int operator*(mod_int const& r) { mod_int res(*this); return res *= r; }
  mod_int pow(int x) const {
    int64_t res = 1, v = v_;
    while(x > 0) {
      if(x&1) (res *= v) %= Prime;
      x/=2; (v *= v) %= Prime;
    }
    return mod_int(res);
  }
  mod_int inv() const { return pow(Prime-2); }
};
typedef mod_int<MOD> mint;

// fact
template<typename INT, int64_t MAXN_>
struct factorial {
  INT fact[MAXN_+1], ifact[MAXN_+1];
  void init(int64_t N) {
    fact[0] = fact[1] = INT(1);
    for(int i = 2; i <= N; ++i) fact[i] = fact[i-1]*i;
    ifact[N] = fact[N].inv();
    for(int i = N-1; i >= 0; --i) ifact[i] = ifact[i+1]*(i+1);
  }
  INT perm(int64_t n, int64_t k) {
    if(k > n) return INT(0);
    return fact[n]*ifact[n-k];
  }
};

int const MAXN = 1e5;

factorial<mint, MAXN> F;

int main() {
  int N, K; std::cin >> N >> K;
  F.init(K);
  std::vector<std::vector<int>> G(N);
  for(int i = 0; i < N-1; ++i) {
    int a, b; std::cin >> a >> b; --a; --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  auto dfs = [&](auto&& f, int v, int p) -> mint {
    int adj = G[v].size();
    mint res = (p<0)? F.perm(K, adj+1): F.perm(K-2, adj-1);
    for(auto c: G[v]) if(c != p) res *= f(f, c, v);
    return res;
  };
  fin(dfs(dfs, 0, -1).v_);
  return 0;
}


Measured memory_bytes: 9600
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][0]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][1])
        G[xy[i][1]].append(p[1])
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][0], xy[i][1]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

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

/**
 * AIZU ONLINE JUDGE
 * 2852 Tiny Room
 *    2018/02/19
 */
public class Main {

    int N;
    int W;
    int H;
    int R;
    int[] x;
    int[] y;
    
    double func(double th) {
        double xmax = -Double.MAX_VALUE;
        double ymax = -Double.MAX_VALUE;
        double xmin = Double.MAX_VALUE;
        double ymin = Double.MAX_VALUE;
        double cos = Math.cos(th);
        double sin = Math.sin(th);
        for(int n = 0; n < N; n++) {
            double x0 = cos * x[n] - sin * y[n];
            double y0 = sin * x[n] + cos * y[n];
            if (x0 > xmax)
                xmax = x0;
            if (x0 < xmin)
                xmin = x0;
            if (y0 > ymax)
                ymax = y0;
            if (y0 < ymin)
                ymin = y0;
        }
        double max = Math.max(xmax - xmin - W, ymax - ymin - H);
        return max;
    }
    
    boolean smin(double x0, double x1) {
        for(int i = 0; i < 20; i++) {
        double m = (x0 + x1) / 2;
        double delta = 0.0000000001;
        double k = func(m);
        double kd = func(m + delta);
            log.printf("x0 x1, m (%f %f %f) k = %f\n", x0, x1, m, k);
        if (k <= 0)
                return true;
        if (k < kd) {
                x1 = m;
        }
        else {
                x0 = m;
            }
        }
        return false;
    }

    boolean main() throws IOException {

        Scanner sc = new Scanner(systemin);

        N = sc.nextInt();
        H = sc.nextInt();
        W = sc.nextInt();
        R = sc.nextInt();
        H -= R * 2;
        W -= R * 2;
        //log.printf("%d %d\n",  N, M);
        x = new int[N];
        y = new int[N];
        for(int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            //log.printf("%d %d\n", x[i], y[i]);
        }

        
        int ret = 0;
        int B = 1000;
        double k2 = 0;
        double d2 = 0;
        double d;
        for(int i = 0; i < B + 3; i++) {
            double s = i * Math.PI / B;
            double k = func(s);
            log.printf("%d\t%f\t%s\n", i, k, k <= 0 ? "OK" : "");
            if (k < 0) {
                ret = 1;
                break;
            }
            d = k - k2;
            if (i >= 2 && d2 <= 0 && d >= 0) {
                boolean sm = smin((i - 2) * Math.PI / B, s);
                if (sm) {
                    ret = 1;
                    break;
                }
            }
            
            k2 = k;
            d2 = d;
            
        }

        result.printf("%s\n", ret != 0? "Yes":"No");

        sc.close();
        return false;
    }

    PrintStream log;
    PrintStream result = System.out;
    BufferedReader systemin;

    static Main instance = new Main();

    Main() {
        systemin = new BufferedReader(new InputStreamReader(System.in));
        log = new PrintStream(new OutputStream() { public void write(int b) {} } );
    }

    public static void main(String[] args) throws IOException {

        instance.main();

        instance.systemin.close();
    }


}




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

using namespace std;
constexpr long long int mod = 1000000007;
int main() {
	long long a, b, c;
	cin >> a >> b >> c;
	if (b - 1 <= c)cout << (b - 1) * a / b;
	else cout << (a * c) / b;
}

Measured memory_bytes: 3620
#include <iostream>
#include <sstream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>
#include <list>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
//#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))
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 namespace std;

int main(void)
{
    lli N, K; cin >> N >> K;
    vector<lli> A(N); 
    rep(i, 0, N) {
        cin >> A[i];
        A[i]--;
    }
    vector<bool> used(N, false); //false:not used, true;used
    lli tmp = 0; //where he is
    vector<lli> order; //order.push_back(0);
    while (!used[tmp]) {
        order.push_back(tmp);
        used[tmp] = true;
        tmp = A[tmp];
    }
    //rep(i, 0, order.size())cout << order[i] << endl;
    //cout << tmp << endl;

    lli num_tmp = 0;
    rep(i, 0, order.size()) {
        if (tmp == order[i]) {
            num_tmp = i;
            break;
        }
    }

    if (K < num_tmp)cout << order[K] + 1 << endl;
    else {
        lli ans = K - num_tmp;
        ans = ans % (order.size() - num_tmp);
        cout << order[ans+num_tmp] + 1 << endl;
    }


    return 0;
}


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

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0 ; i < n ; i++){
        int x;
        cin >> x;
        p[x-1] = i;
    }
    for( auto i : p ) cout << i + 1 << " ";
    cout << endl;
}


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

typedef long long ll;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "]\n" : ", "); } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int n;

class SEGTREE
{
private:
    vector<ll> dat;
public:
    int n;
    int init(int n_);
    void update(int k, ll a);
    ll query(int a, int b, int k, int l, int r);
};

int SEGTREE::init(int n_) {
    n = 1;
    while (n <= n_) n *= 2;
    dat = vector<ll>(2*n,0);
    return n;
    //for (int i = 0;i < 2*n-1;++i) dat[i] = INT_MAX;
}

void SEGTREE::update(int k,ll a) {
    k += n-1;
    dat[k] = a;
    while (k > 0) {
        k = (k-1)/2;
        dat[k] = max(dat[k*2+1],dat[k*2+2]);
    }
}

ll SEGTREE::query(int a,int b,int k,int l,int r) {
    if (r <= a || b <= l) return -1;
    if (a <= l && r <= b) return dat[k];
    else {
        ll vl = query(a,b,k*2+1,l,(l+r)/2);
        ll vr = query(a,b,k*2+2,(l+r)/2,r);
        return max(vl,vr);
    }
}

int main() {
    SEGTREE mx;
    cin >> n;
    vector<int> h(n);
    vector<ll> a(n),dp(n+1,0);
    for (int i = 0;i < n;++i) cin >> h[i];
    for (int i = 0;i < n;++i) cin >> a[i];
    int m = mx.init(n);
    for (int i = 0;i < n;++i) {
        dp[h[i]] = mx.query(0,h[i],0,0,m)+a[i];
        ll t = mx.query(0,h[i],0,0,m);
        mx.update(h[i],dp[h[i]]);
    }
    cout << *max_element(dp.begin(),dp.end()) << endl;
    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main(){
    int n;
    ll y;
    cin >>n >>y;

    ll s = 0;
    vector<ll> a(n);
    rep(i,n){
        cin >>a[i];
        s += a[i];
    }

    ll ans = 0;
    for(int pre=1; pre<n; ++pre)rep(suf,n){
        if(pre+suf>=n) continue;

        ll tt = 0;
        rep(i,pre) tt += a[i];
        rep(i,suf) tt += a[n-1-i];
        if(tt+y < s/5) continue;

        vector<ll> v;
        for(int i=pre; i<n-suf; ++i) v.pb(a[i]);
        int V = v.size();
        if(V<4) continue;

        vector<ll> p(V+1);
        rep(i,V) p[i+1] = v[i]+p[i];

        vector<ll> dp(V+1);
        dp[0] = 1;
        rep(loop,4){
            vector<ll> nx(V+1);

            ll ss = 0;
            int j = 0;
            rep(i,V){
                while(j<i+1 && p[i+1]-p[j]+y>=s/5){
                    ss += dp[j];
                    ++j;
                }
                nx[i+1] = ss;
            }
            dp = nx;
        }

        ans += dp[V];
    }

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



Measured memory_bytes: 3184
n,x=map(int,input().split())
arr=list(map(int,input().split()))
cost=[10**18]*n
ans=10**18
for i in range(n):
  for j in range(n):
    cost[j]=min(cost[j],arr[j-i])
  ans=min(ans,x*i+sum(cost))
print(ans)

Measured memory_bytes: 3188
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
	double r;
	cin >> r;
	cout << fixed << setprecision(6) 
		<< r*r*M_PI << ' ' 
		<< 2 * r*M_PI << endl;
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) ((int)(x).size())
#define fill(v, h) memset((v), h, sizeof(v))
using namespace std;
const int MOD = 1000000007;

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

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

int main(void)
{
    uint64_t x;
    cin >> x;
    int year = 0;
    uint64_t money = 100;
    while (money<x)
    {
        money = trunc(money * 1.01);
        year++;
    }
    cout << year << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define MOD 1000000007
#define DEBUG 0
#define REP(i,n) for(int i=0;i<n;i++)

lli prime[100010];

vector<lli> makePrimeList(lli num){
	vector<lli> primeList;
	bool isPrime;
	for(lli i=2;i<=num;i++){
		lli size=primeList.size();
		isPrime=true;
		for(lli j=0;j<size;j++){
			if(i%primeList[j]==0){
				isPrime = false;
				break;
			}
		}
		if(isPrime){
			primeList.push_back(i);
			prime[i] = 1;
			if(DEBUG)cout<<"prime="<<i<<endl;
		}
	}
	return primeList;
}

bool isJudge(lli num){
	lli num1 = num;
	lli num2 = (num+1)/2;
	if(prime[num1] and prime[num2])return true;
	else return false;
}

int main(){

	lli Q;
	cin>>Q;
	REP(i,100010)prime[i]=0;
	vector<lli>primeList;
	primeList = makePrimeList(100010);

	lli dp[100010]={0};
	for(lli i=1;i<=100010;i+=2)if(isJudge(i)){
		if(DEBUG)cout<<"nitakazu="<<i<<endl;
		dp[i]=1;
	}
	REP(i,100009)dp[i+1] += dp[i];	

	REP(i,Q){
		lli l,r;
		cin>>l>>r;
		cout<<dp[r]-dp[l-1]<<endl;
	}
	return 0;

}
 

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

void solve() {

    int a, b, c, k;
    cin >> a >> b >> c >> k;

    int Sum = 0;
    while ((k > 0) && (a > 0)) {
        Sum += 1;
        k--;
        a--;
    }
    while ((k > 0) && (b > 0)) {
        k--;
        b--;
    }
    while ((k > 0) && (c > 0)) {
        Sum -= 1;
        k--;
        c--;
    }
    cout << Sum;
}

int main() {

    solve();

    return 0;
}


Measured memory_bytes: 3624
def check(n):
    if n == 1:
        return 0
    elif n == 2 or n == 3:
        return 1
    else:
        for i in range(2,int(n**(1/2))+1):
            if n % i == 0:
                return 0
        return 1
n = int(input())
s = [0 for i in range(n)]
count = 0
for i in range(n):
    s[i] = int(input())
    if check(s[i]) == 1:
        count += 1
print(count)


Measured memory_bytes: 6028
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.141592653589793
#define MOD 1000000007


int main(){
	int c[10][10];
	for(int i=1; i<=3; i++){
		scanf("%d%d%d", &c[i][1], &c[i][2], &c[i][3]);
	}
	//scanf("%d%d%d%d", &r, &g, &b, &n);
	int x[4], y[4];
	x[0] = c[1][2] - c[1][1], x[1] = c[1][3] - c[1][2];
	y[0] = c[2][1] - c[1][1], y[1] = c[3][1] - c[2][1];
	int f=1;
	for(int i=2; i<=3; i++){
		for(int j=2; j<=3; j++){
			if(c[i][j]-c[i][j-1] != x[j-2]){
				f=-1;
			}
			if(c[i][j]-c[i-1][j] != y[i-2]){
				f=-1;
			}
		}
	}
	if(f>0) printf("Yes\n");
	else printf("No\n");
	//printf("Yes\n");
	return 0;
}

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

using namespace std;

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

//全探索

int coin_pattern(int A, int B, int C, int X){
  vector<int> tmp(3);
  int cnt = 0;
  X /= 50;

  rep(i,A+1){
    tmp.at(0) = i*10;
    rep(j, B+1){
      tmp.at(1) = 2*j + tmp.at(0);
      rep(k, C+1){
        tmp.at(2) = k + tmp.at(1);
        if(tmp.at(2) == X) cnt++;
      }
    }
  }

  return cnt;
}

int main(){
  int A,B,C,X;
  cin >> A >> B >> C >> X;

  int counter = coin_pattern(A,B,C,X);

  cout << counter << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const double PI=acos(-1);
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{
    string s;
    cin>>s;
    ll ans=0;
    for(auto v:s)
    {
        int p=v-'0';
        ans+=p;
    }
    if(ans%9==0)
    {
        sayyes;
    }
    else
    {
        sayno;
    }
    
}


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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
typedef long long ll;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;
const int INF = 0x3f3f3f3f;
const int maxn = 1100000;

void run_case()
{
    string s;
    cin >> s;
    string t;
    cin >> t;
    int ans = 0;
    for (int i = 0; i < 3; i++)
    {
        if (s[i] == t[i])
            ans++;
    }
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    run_case();
    cout.flush();
    return 0;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 300005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
const int mod = 1e9 + 7;
int v[100005];
int b[200005];
int n;
vector<int>d;
void update(int x) {
    while (x <= 200000) {
        b[x]++;
        x += (x) & (-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += b[x];
        x -= x & (-x);
    }
    return ret;
}
ll cal(int x) {
    //cout << x << endl;
    ll ans = 0;
    ms(b);
    int cur = 100000;
    update(cur);
    f1(n) {
        if (v[i] >= d[x]) {
            cur++;
        }
        else {
            cur--;
        }
        ans += query(cur);
        update(cur);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    f1 (n) {
        cin >> v[i];
        d.pb(v[i]);
    }
    d.pb(-1);
    sort(all(d));
    ll tar = ((ll)(n) * (n + 1) / 2 + 1) / 2;
    int l = 1, r = n + 1;
    while (r - l > 1) {
        int mid = (r + l) >> 1;
        if (cal(mid) >= tar) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    cout << d[l] << '\n';
}


Measured memory_bytes: 1912
import java.util.*;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<n; i++){
            int d = sc.nextInt();
            set.add(d);
        }
        System.out.println(set.size());
    }
}

Measured memory_bytes: 22100
import scala.io.StdIn.readInt
import scala.collection.mutable.ArrayBuffer

object Main {
  def sieve(n:Int) = {
    val primes = Array.tabulate(n+1) { _ % 2 }
    primes(1) = 0
    primes(2) = 1

    for( i <- 3 to Math.sqrt(n).toInt by 2 )
    {
      if(primes(i) == 1)
        (i*i to n by i*2).foreach { primes(_) = 0 }
    }
    primes
  }

  def main(args:Array[String]) = {
    val p = sieve(10001)
    val b = new ArrayBuffer[String]
    var i = 0
    while({i=readInt;i}!=0) {
      val n =if(i.toInt % 2 == 0) i.toInt-1 else i.toInt
      b += (n to 5 by -2).find( j=> p(j)==1 && p(j-2)==1 ).map( j=>(j-2)+" "+j ).get
    }
    println( b.mkString("\n") )
  }
}

Measured memory_bytes: 54852
// finish date: 2018/2/14

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N, M;
    cin >> N >> M;
    vi cnt(M, 0);
    rep(i, N) {
        int K;
        cin >> K;
        int A;
        rep(i, K) {
            cin >> A;
            A--;
            cnt[A]++;
        }
    }
    int ans = 0;
    rep(i, M) {
        if (cnt[i] == N) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256