akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,m;
  cin>>n;
  if(n&1)m=n;
  else m=n+1;
  cout<<n*(n-1)/2-n/2<<endl;
  repi(i,1,n)
  {
    repi(j,i+1,n+1)
    {
      if(i+j==m)continue;
      cout<<i<<" "<<j<<"\n";
    }
  }
  cout<<flush;


  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(i*j==n){
			cout << "Yes" << endl;
			return 0;	
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

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

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

const long long INF = 1LL << 60;

int main() {
    int n;
    long long h[100100];
    long long dp[100100];

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

    for (int i = 0; i < 100100; i++) dp[i] = INF;

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

    cout << dp[n - 1] << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




int main(){

	ll X;
	scanf("%lld",&X);

	ll sum = 0;
	for(ll i = 1; ; i++){

		sum += i;
		if(sum >= X){

			printf("%lld\n",i);
			return 0;
		}
	}

	return 0;
}


Measured memory_bytes: 256
from collections import deque

N, M = list(map(int, input().split()))
relation_list = [[] for _ in range(N + 1)]
for i in range(M):
    a, b = list(map(int, input().split()))
    relation_list[a].append(b)
    relation_list[b].append(a)

room_q = deque()
room_q.append(1)
michihsirube_room = [-1 for _ in range(N + 1)]
while room_q:
    node = room_q.popleft()
    for near_room_id in relation_list[node]:
        if michihsirube_room[near_room_id] == -1:
            michihsirube_room[near_room_id] = node
            room_q.append(near_room_id)
print('Yes')
for i in range(2, N + 1):
    print(michihsirube_room[i])


Measured memory_bytes: 34080
process.stdin.resume();
process.stdin.setEncoding("utf8");

const reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];

reader.on("line", (line) => {
  lines.push(line);
});

reader.on("close", () => {
  for (let l = 0; l < lines.length; l++) {
    const [n, x] = parseLine(lines[l]);
    if (!n && !x) break;
    let count = 0;
    for (let i = Math.min(x - 1, n); i > 2; i--) {
      for (let j = i - 1; j > 1; j--) {
        let k = x - (i + j);
        if (k > 0 && k < j) count++;
      }
    }
    console.log(count);
  }
});

function parseLine(s) {
  return s.split(" ").map((s) => Number(s));
}



Measured memory_bytes: 16648
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])


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

using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], b[N], n, m, t, p;

bool isval(int idx)
{
    int v = max(t - (n - idx + 1), 0ll) * m;
    for (int i = 1; i <= n; i++) b[i] = m;
    for (int i = idx - 1; i >= 1; i--) {
        if (a[idx] + m > a[i]) b[i] -= a[idx] + m - a[i], v -= a[idx] + m - a[i];
    }
    for (int i = 1; i < p; i++) v -= b[i];
    return (v <= 0 && (a[p] <= a[idx] + m));
}

int32_t main()
{
    cin >> n >> m >> t >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    int dw = 1, up = n + 1;
    while (up - dw > 1){
        int md = (up+dw)>>1;
        if (isval(md)) dw = md;
        else up = md;
    }
    cout << dw << "\n";
}


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

#define N 3
#define LIM 32
#define HN 362897

struct dep{
  int depth,key;
};

int ans[N][N]={
  {1,2,3},
  {4,5,6},
  {7,8,0}
};

int min = LIM;
struct dep h[HN];

int hash1(int k)
{
  return k % HN;
}
int hash2(int k)
{
  return 1 + k%(HN-1);
}
int hash(int k, int i)
{
  return (hash1(k) + i*hash2(k))%HN;
}


void dfs(int p[N][N], int n)
{
  int i,j,i0,j0,a=0,b=1;
  int f=0;
  int tmp[N][N];
  for(i=0;i<N;i++)
  {
    for(j=0;j<N;j++)
    {
      if(ans[i][j]!=p[i][j])f++;
      if(p[i][j]==0)
      {
        i0=i;
        j0=j;
      }
      a+=p[i][j]*b;
      b*=10;
    }
  }

  if(f==0)
  {
    if(min>=n)
    {
      min=n;
    }
    return;
  }
  if(n>min) return;
  i=0;
  while(1)
  {
    b=hash(a, i);
    if(h[b].key == 0)
    {
      h[b].key=a;
      h[b].depth=n;
      break;
    }
    else if(h[b].key == a)
    {
      if(h[b].depth>n)
      {
        h[b].depth=n;
        break;
      }
      else return;
    }
    i++;
  }

  if(i0>0 && i0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0-1][j0];
    tmp[i0-1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>0 && j0<N)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0-1];
    tmp[i0][j0-1]=f;
    dfs(tmp, n+1);
  }

  if(i0>=0 && i0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0+1][j0];
    tmp[i0+1][j0]=f;
    dfs(tmp, n+1);
  }
  if(j0>=0 && j0<N-1)
  {
    memcpy(tmp,p,sizeof(int)*N*N);
    f=tmp[i0][j0];
    tmp[i0][j0]=tmp[i0][j0+1];
    tmp[i0][j0+1]=f;
    dfs(tmp, n+1);
  }

}

int main()
{
  int i,j;
  int p[N][N];

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

  printf("%d\n",min);

  return 0;
}



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

#define int long long
#define DEBUG(x) cerr <<#x<<":"<<x<<endl;
#define DEBUG2(x, y) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<endl;
#define DEBUG3(x, y, z) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl;
#define DEBUGVC(x) cerr <<#x<<": "; for(auto a:x) cerr << a <<" "; cerr << endl;
#define DEBUGMP(x) cerr <<#x<<":"<<endl; for(auto a:x) cerr << a.first <<" "<< a.second << endl;
#define MAX_N (1000006)
#define INF (1LL << 60)
const int MOD = (int)1e9+7;


signed main() {
    while(1) {
        int n, r;
        cin >> n >> r;
        if(n==0 && r==0) break;

        stack<int> st;
        for(int i=1; i<=n; i++) st.push(i);

        for(int i=0; i<r; i++){
            int p, c;
            cin >> p >> c;
            vector<int> v1;
            vector<int> v2;
            for(int j=0; j<p-1; j++){
                v1.push_back(st.top());
                st.pop();
            }
            for(int j=0; j<c; j++){
                v2.push_back(st.top());
                st.pop();
            }
            for(int j=0; j<p-1; j++){
                st.push(*(v1.end()-1));
                v1.pop_back();
            }
            for(int j=0; j<c; j++){
                st.push(*(v2.end()-1));
                v2.pop_back();
            }
        }

        cout << st.top() << endl;

    }
}



Measured memory_bytes: 3020
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:input()

"""========main code==============="""

t=ii()
ans=0
k=t//500
ans+=(k*1000)
t-=(k*500)
#print(t)
p=t//5
ans+=p*5
print(ans)

Measured memory_bytes: 38256
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

typedef vector<int> vi;

int m,n;
string obj[130];
map<vi, int> mp;


int dfs(vi &c){
    if(c.size()<=1) return 0; //分かった

    int& x = mp[c];
    if(x) return x; //探索済み。その他、デフォは0

    x = m;
    for(int i=0;i<m;++i){
        vi l,r;
        for(int j : c){
            if(obj[j][i]=='1') l.push_back(j);
            else r.push_back(j);
        }
        if(l.empty() || r.empty()) continue;
        x = min(x, 1+max(dfs(l),dfs(r)));
    }
    return x;
}

int main(){
    while(cin>>m>>n){
        if(m==0 && n==0) return 0;

        mp.clear();
        for(int j=1;j<=n;++j) cin>>obj[j];

        vi c; //cand
        for(int j=1;j<=n;++j) c.push_back(j);

        cout << dfs(c) << endl;
    }
}



Measured memory_bytes: 5308
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


n = int(input())
ps = get_sieve_of_eratosthenes(55555)
ansl = []
for p in ps:
    if p%5 == 1:
       ansl.append(p) 

print(*ansl[:n])


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

int main(){
    int n;
    int tarou = 0;
    int hanako = 0;
    string card1, card2;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> card1 >> card2;
        if(card1 > card2){
            tarou += 3;
        }
        else if(card1 < card2){
            hanako += 3;
        }
        else{
            tarou++;
            hanako++;
        }
    }
    cout << tarou << " " << hanako << endl;
    return 0;
    
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
vector<int> abc(3, 0);
int main() {
    for(int i = 0; i < 3; ++i) {
        cin >> abc.at(i);
    }

    sort(abc.begin(), abc.end());

    for(int i = 0; i < 3; ++i) {
        if(i == 0 || i == 1) {
            if(abc.at(i) != 5) {
                cout << "NO" << endl;
                return 0;
            }
        }else {
            if(abc.at(i) != 7) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    cout << "YES" << endl;
}

Measured memory_bytes: 256
N=int(input())
H=list(map(int,input().split()))
Cost=[0 for i in range(N)]
Cost[1]=abs(H[1]-H[0])
for i in range(2,N):
    Cost[i]=min(Cost[i-2] + abs(H[i]-H[i-2]), Cost[i-1] + abs(H[i]-H[i-1]))
print(Cost[N-1])

Measured memory_bytes: 14028
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI (acos(-1))
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using Complex = std::complex<double>;
using namespace std;


int N;
int p[1010];


int solve(){
	int ans = 1;
	repe(i, 2, N){
		int n = i;
		repif(j, 2, j*j <= i)
			while(n%j == 0) n/=j, p[j]++;
		if(n != 1) p[n]++;
	}
	rep(i, 0, 1010)
		if(p[i] != 0) ans = MUL(ans, p[i]+1);
	return ans;
}


signed main(){
	cin >> N;

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
       
while(true){
     int H = scan.nextInt();
        int W = scan.nextInt();
if(H == 0 && W == 0)break;

for(int i = 0; i < H; i++){
    for(int x = 0; x < W;  x++){
        System.out.print("#");
    }
  System.out.println();
}
System.out.println();
}
        
    }
}



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

typedef long long LL;

const int Mod=998244353,N=3e5+10;

int n,A,B,fact[N],inv[N];
LL k;

void Init() {
	scanf("%d%d%d%lld",&n,&A,&B,&k);
}

int Calc(int n,int m) {
	return 1ll*fact[n]*inv[m]%Mod*inv[n-m]%Mod;
}

void Solve() {
	fact[0]=1; for (int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%Mod;
	inv[1]=inv[0]=1; for (int i=2;i<=n;++i) inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	for (int i=2;i<=n;++i) inv[i]=1ll*inv[i-1]*inv[i]%Mod;
	int ans=0;
	for (int i=0;i<=n && k>=1ll*i*A;++i) if ((k-1ll*i*A)%B==0)  {
		LL x=i,y=(k-1ll*i*A)/B;
		if (x<=n && y<=n) ans=(ans+1ll*Calc(n,x)*Calc(n,y))%Mod;
	}
	printf("%d\n",ans);
}

int main()
{
	Init();
	Solve();
	return 0;
}


Measured memory_bytes: 2560
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N = int(input())
D = list(map(int,input().split()))

energy = 0
for i in range(N):
    tmp = D.pop(0)
    energy += tmp*sum(D)

print(energy)


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li n, x, y;

li ans[2020];

int main() {
    cin >> n >> x >> y;
    x--;
    y--;

    rep(i, n) {
        repp(j, i + 1, n) {
            li res = j - i;
            // use xy
            li res2 = abs(x - i) + abs(y - j) + 1;
            ans[min(res, res2)]++;
        }
    }
    rep(i, n - 1) {
        cout << ans[i + 1] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static boolean f(ArrayList<int[]> p, ArrayList<int[]> q) {
		if (p.size() != q.size()) return false;
		int n = p.size();
		int dx = p.get(0)[0], dy = p.get(0)[1];
		for (int i=0; i<n; i++) {
			p.get(i)[0] -= dx;
			p.get(i)[1] -= dy;
		}
		dx = q.get(0)[0]; dy = q.get(0)[1];

		for (int i=0; i<n; i++) {
			q.get(i)[0] -= dx;
			q.get(i)[1] -= dy;
		}

		for (int k=0; k<4; k++) {
			boolean res = true;
			for (int i=0; i<n; i++) {
				if (p.get(i)[0] != q.get(i)[0] || p.get(i)[1] != q.get(i)[1]) {
					res = false;
				}
			}

			if (res) return true;
			res = true;

			for (int i=0; i<n; i++) {
				int x = q.get(i)[0];
				int y = q.get(i)[1];
				q.get(i)[0] = -y;
				q.get(i)[1] = x;
			}
		}

		return false;
	}

	static boolean solve() {
		int n = in.nextInt();
		if (n == 0) return false;
		n = n + 1;

		ArrayList<ArrayList<int[]>> p = new ArrayList<>();
		for (int i=0; i<n; i++) {
			p.add(new ArrayList<int[]>());
		}

		for (int i=0; i<n; i++) {
			int m = in.nextInt();
			for (int j=0; j<m; j++) {
				p.get(i).add(new int[]{in.nextInt(), in.nextInt()});
			}
		}

		for (int i=1; i<n; i++) {
			ArrayList<int[]> q = new ArrayList<>();
			for (int j=p.get(i).size()-1; j>=0; j--) {
				q.add(p.get(i).get(j));
			}

			if (f(p.get(0), p.get(i))) {
				out.println(i);
			} else if (f(p.get(0), q)) {
				out.println(i);
			}
		}
		out.println("+++++");

		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		while(solve());
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 38968
#include <iostream>
using namespace std;
int main(void){
    int n, money=100000; 
    cin >> n;
    for(int i=1; i<=n; i++){
        money *= 1.05;
        if(money%1000 != 0){
            money = money/1000*1000 +1000;
        }
    }
    cout << money << endl;
    return 0;
}



Measured memory_bytes: 2988
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools


def main():
    N = int(input())
    P = tuple(map(int, input().split()))
    Q = tuple(map(int, input().split()))
    result = 0
    seq = [i + 1 for i in range(N)]
    seq_list = list(itertools.permutations(seq, N))
    print(abs(seq_list.index(P) - seq_list.index(Q)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 8052
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>
#define pL3 pair<pL, ll>

const int MX=1000000;
const ll inf=1e18;
const ll mod=1e9+7;


int main()
{
    FasterIO;

//    int tc, cs=1; cin>>tc;
//    while(tc--)
    {
        ll a, b, c, d;
        cin>>a>>b>>c>>d;
        ll mx=-1e18;

        mx=max(mx, b*d);
        mx=max(mx, a*c);
        mx=max(mx, b*c);
        mx=max(mx, d*a);
        if(a<=0 && b>=0 || c<=0 && d>=0) mx=max(mx, 0LL);

        cout<<mx<<endl;
    }
    return 0;
}


Measured memory_bytes: 3632
using System;

public class Nin{
    public static void Main(){
        int N=int.Parse(Console.ReadLine());
        int human=0;
        for(int i=0;i<N;i++){
            string[] s=Console.ReadLine().Split();
            int a=int.Parse(s[0]);
            int b=int.Parse(s[1]);
            human+=b-a+1;
        }
        Console.WriteLine(human);
    }
}


Measured memory_bytes: 11092
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
ll x[1000],y[1000],z[1000],a[1000],ans;
int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
    ans=0;
    for(int cas=0;cas<8;cas++){
        for(int i=0;i<n;i++){
            a[i]=0;
            a[i]+=cas&1?x[i]:-x[i];
            a[i]+=cas&2?y[i]:-y[i];
            a[i]+=cas&4?z[i]:-z[i];
        }
        sort(a,a+n);
        ll mx=0;
        for(int i=n-m;i<n;i++)mx+=a[i];
        ans=max(ans,mx);
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 128
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = n % 1000 == 0 ? 1000 : n % 1000;
		System.out.println(1000 - t);

	}
}




Measured memory_bytes: 35792
#include "cstdio"
int a,b,i,c;
int main(){
	scanf("%d%d%d",&a,&b,&c);int x=0;
	for(i=0;i<=b;i++,x+=a)
	if(x%b==c){
		printf("YES\n");return 0;
	}
	printf("NO\n");
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

#ifdef ELEGIA
const int L = 6;
#else
const int L = 18;
#endif

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k, s, t;
  cin >> n >> k >> s >> t;
  if ((s & t) != s) {
    cout << "0\n";
    return 0;
  }
  vector<int> a;
  while (n--) {
    int x;
    cin >> x;
    if ((x & s) == s && (x & t) == x)
      a.push_back(x);
  }
  n = a.size();
  if (n == 0) {
    cout << "0\n";
    return 0;
  }
  k = min(n, k);
  for (int& x : a)
    x -= s;
  t -= s;
  s = 0;

  vector<vector<ll>> C(n + 1, vector<ll>(n + 1));
  vector<ll> sb(n + 1);
  for (int i = 0; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    sb[i] = accumulate(C[i].begin() + 1, C[i].begin() + k + 1, 0LL);
  }

  vector<ll> f0(L), f1(L);
  ll ans = 0;
  for (int i = 0; i < L; ++i) {
    for (int j = 0; j < n; ++j)
      if ((a[j] >> i) & 1)
        f0[i] |= 1LL << j;
      else
        f1[i] |= 1LL << j;
  }
  function<void(int, int, ll)> dfs = [&](int k, int sgn, ll mask) {
    if (k == L) {
      ans += sgn * sb[__builtin_popcountll(mask)];
      return;
    }
    dfs(k + 1, sgn, mask);
    if ((t >> k) & 1) {
      dfs(k + 1, -sgn, mask & f0[k]);
      dfs(k + 1, -sgn, mask & f1[k]);
    }
  };
  dfs(0, 1, (1LL << n) - 1);
  cout << ans;

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define mp(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll IINF = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll b[n];
    for (int i = 0; i < n; i++) {
        b[i] = a[i] ^ a[(i + 1) % n];
    }
    vector<bool> vis(n + 1, 0);
    ll tot = 0;
    for (int i = 0; i < n; i++) {
        int ti = i + 1;
        int tj = ti + 1; if (tj > n) tj -= n;
        if (vis[ti] || vis[tj]) continue;
        vis[ti] = vis[tj] = true;
        tot ^= b[i];
    }
    for (int i = 0; i < n; i++) {
        ll v = tot ^ a[i];
        cout << v << ' ';
    }
    cout << '\n';
    return 0;
}

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

int main(){
  char s[201];
  int i, len, si, flag;

  scanf("%s", s);
  len = strlen(s);

  for(si=(len+1)/2-1;si>0;si--){
    i=0;
    flag=0;
    for(i=0;i<si;i++){
      if(s[i]!=s[si+i]){flag=1;break;}
    }
    if(flag==0){printf("%d\n", si*2);return 0;}
  }
  return 0;
}


Measured memory_bytes: 128
//BISMILLAHIR RAHMANIR RAHIM
//ALLAH HU AKABR
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
string s;
cin>>s;
int l=s.size();
if(l<=n)
{
    cout<<s<<endl;
}
else
{
 for(int i=0;i<n;i++)
 {
     cout<<s[i];
 }
 cout<<"...";

}
return 0;
}


Measured memory_bytes: 3644
s = input()
K = int(input())
ans_lis = []
s_length = len(s)
lis = [[] for i in range(26)]

for i in range(s_length):
    lis[ord(s[i]) - ord('a')].append(i)


for i in range(26):
    k = 1
    while k <= K:
        for j in lis[i]:
            ans_lis.append(s[j:j + k])
        k += 1
        ans_lis = sorted(list(set(ans_lis)))
    if len(ans_lis) >= K:
        print(ans_lis[K - 1])
        exit()


Measured memory_bytes: 9444
s = input()
c = 0
ans = 0
for i in range(len(s)):
    if s[i] == "A" or s[i] == "T" or s[i] == "C" or s[i] == "G":
        c += 1
    else:
        ans = max(ans, c)
        c = 0
ans = max(ans, c)
print(ans)

Measured memory_bytes: 3060
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

bool is_palin(string& s) {
    bool ok = true;
    forn(i, s.size() / 2) {
        ok &= s[i] == s[s.size() - 1 - i];
    }
    return ok;
}

int main() {
    fastio();

    string s;
    cin >> s;

    int n = s.size();

    string t = s.substr(0, (n - 1) / 2);
    string u;

    for (int i = (n + 3) / 2 - 1; i < n; i++) {
        u.push_back(s[i]);
    }

    if (is_palin(s) && is_palin(t) && is_palin(u)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 256
def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    T = int(buflist[1])
    c = []
    t = []
    for i in range(N):
        buf = input()
        buflist = buf.split()
        c.append(int(buflist[0]))
        t.append(int(buflist[1]))
    min = None
    index = None
    for i in range(N):
        if t[i] <= T:
            if min == None:
                min = c[i]
                index = i
            elif c[i] < min:
                min = c[i]
                index = i
    if min == None:
        print("TLE")
    else:
        print(min)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = list(map(int, input().split()))
li = []
for i in range(2**n):
  total = 0
  for j in range(n):
    if ((i>>j)&1):
      total += a[j]
  li.append(total)

for p in b:
  if p in li:
    print('yes')
  else:
    print('no')



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

int main() {
	int n;
	cin>>n;
	
	int number=0;
	if(n>=105) number++;
	if(n>=135) number++;
	if(n>=165) number++;
	if(n>=189) number++;
	if(n>=195) number++;
	
	cout<<number<<endl;
	return 0;
}

Measured memory_bytes: 256
from itertools import product
from bisect import bisect_left, bisect_right


def main():
    A, B, Q = map(int, input().split())
    ss = [int(input()) for _ in range(A)]
    ts = [int(input()) for _ in range(B)]
    xs = [int(input()) for _ in range(Q)]

    # gen = TLE(A, B, Q, ss, ts, xs)
    # gen = f(A, B, Q, ss, ts, xs)
    gen = editorial(A, B, Q, ss, ts, xs)
    print(*gen, sep="\n")


def TLE(A, B, Q, ss, ts, xs):
    for x in xs:
        ans = float("inf")
        for s in ss:
            for t in ts:
                if s <= x <= t or t <= x <= s:
                    ds, dt = abs(x-s), abs(x-t)
                    tmp = min(ds, dt) + abs(s-t)
                elif x <= s <= t or x <= t <= s:
                    tmp = max(s, t)-x
                elif x >= s >= t or x >= t >= s:
                    tmp = x-min(s, t)
                ans = min(ans, tmp)

        yield ans


def f_ans(s, t, x):
    if s <= x <= t or t <= x <= s:
        ds, dt = abs(x-s), abs(x-t)
        tmp = min(ds, dt) + abs(s-t)
    elif x <= s <= t or x <= t <= s:
        tmp = max(s, t)-x
    elif x >= s >= t or x >= t >= s:
        tmp = x-min(s, t)
    return tmp


def f(A, B, Q, ss, ts, xs):
    for x in xs:
        t_left = bisect_left(ts, x)
        t_right = bisect_right(ts, x)
        s_left = bisect_left(ss, x)
        s_right = bisect_right(ss, x)

        t_idx = [t_right + a for a in [-1, 0, 1]]
        t_idx += [t_left + a for a in [-1, 0, 1]]
        s_idx = [s_right + a for a in [-1, 0, 1]]
        s_idx += [s_left + a for a in [-1, 0, 1]]

        ans = float("inf")
        for si, ti in product(set(s_idx), set(t_idx)):
            if 0 <= si < A and 0 <= ti < B:
                tmp = f_ans(ss[si], ts[ti], x)
                ans = min(ans, tmp)
        yield ans


def editorial(A, B, Q, ss, ts, xs):
    INF = float("inf")
    # 番兵
    ss = [-INF] + ss + [INF]
    ts = [-INF] + ts + [INF]
    for x in xs:
        # -inf の右 [1]
        # +inf の左 [-1]
        b, d = bisect_right(ss, x), bisect_right(ts, x)
        ans = INF
        # 番兵のおかげでindex を気にしなくて良い
        for s in [ss[b - 1], ss[b]]:
            for t in [ts[d - 1], ts[d]]:
                # s--t--x, t--s--x
                # s--x--t, t--x--s
                # x--t--s, x--s--t
                d1 = abs(s - x) + abs(t - s)
                d2 = abs(t - x) + abs(s - t)
                ans = min(ans, d1, d2)

        yield ans


if __name__ == "__main__":
    main()


Measured memory_bytes: 22160
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

struct DATA{
  int size;
  int num;
  string str;
};

void Divide(const string, vector<string>*);
void Convert(const vector<string>, vector<DATA>*);
DATA MakeOneData(int, int, const string);
bool Compare(const DATA&, const DATA&);

int main(){
  string origin;
  vector<string> data1;
  vector<DATA> data2;

  cin >> origin;
  Divide(origin, &data1);
  Convert(data1, &data2);
  sort(data2.begin(), data2.end(), Compare);
  cout << data2[0].str << endl;

  return 0;
}

void Divide(const string str, vector<string>* data){
  int i=0;
  const string C("chicken");
  const string E("egg");

  while(i < str.size()){
    if(str[i] == C[0]){
      data->push_back(C);
      i += C.size();
    }else{
      data->push_back(E);
      i += E.size();
    }
  }
}

void Convert(const vector<string> data1, vector<DATA>* data2){
  int i, j, k;
  for(i=1, j=0, k=0; i<data1.size(); ++i){
    if(data1[i] == data1[i-1]){
      data2->push_back(MakeOneData(i-j, k, data1[i-1]));
      j=i;
      ++k;
    }
  }
  data2->push_back(MakeOneData(data1.size()-j, k, data1[data1.size()-1]));
}

DATA MakeOneData(int size, int num, const string str){
  DATA data;
  data.size = size;
  data.num = num;
  data.str = str;
  return data;
}

bool Compare(const DATA& x, const DATA& y){
  if(x.size == y.size) return (x.num < y.num);
  else return (x.size > y.size);
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
 
#define NOT_FOUND -1
/*for文のマクロ定義
rep(i,回数){
    処理
}
*/
 
void swap(int *a, int *b){
 *b=*a-*b;
 *a-=*b;
 *b+=*a;
}
 
int sosu_judge(int N){
 /*素数ならば1
   素数でなければ0を返す
 */
 int i,j;
 
 if(N==2)   return 1;
 if(N%2==0) return 0;
 
 for(i=3;i<N && N%i!=0;i+=2);
 
 if(i>=N) return 1;
 
 return 0;
}
 
int factorial(int N){  //Nの階乗を求める関数
 int ans=1;
 
 while(N--) ans*=(N+1);
 return ans;
}
 
//クイックソートをする関数
void q_sort(int a[], int first, int last){
    int i,j;
    int x,t;
 
    x = a[(first + last) / 2];
    i = first; j=last;
 
    while(1){
        while( a[i] < x) i++;
        while( x < a[j]) j--;
        
        if( i >= j) break;
        
        swap(&a[i],&a[j]);
        i++; j--;
    }
    if(first < i-1) q_sort(a, first,i-1 );
    if(last > j+1)  q_sort(a, j+1,  last);
}
 
int b_search(int target, int array[],int right, int left){
    /*二分探索を行う関数である。
      戻り値は探索したい値の格納されている位置である。
      もし値が存在しない場合、NOT_FOUND(-1)を返す
    */
    int mid;
    while(left<right){
        mid=(right+left)/2;
        if(array[mid]<target) left =mid+1;
        else                  right=mid;
    }
    if(array[mid]==target) return mid;
    return NOT_FOUND;
}
 
unsigned long combination(int n, int r){
    /*nCrの値を求める関数である。
      値が巨大になる可能性があるため、戻り地はunsigned longである
    */
    int i,j;
    unsigned long a[17];
 
    if(n-r<r) r=n-r;
    if(r==0 ) return 1;
    if(r==1 ) return n;
    if(r>17 ) return 0;
    for(i=1;i<r;i++) a[i]=i+2;
    for(i=3;i<=n-r+1;i++){
        a[0]=i;
        for(j=1;j<r;j++)a[j]+=a[j-1];
    }
    return a[r-1];
}

int main(){
    int n;
    cin>>n;
    int a[n];
    int b[n];
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    int suma,sumb1,sumb2=0;
    int sumb;
    int sum[n];
    rep(i,n) sumb1=sumb1+b[i];
    rep(i,n){
        suma=suma+a[i];
        sumb2=sumb2+b[i];
        sumb=sumb1-sumb2+b[i];
        sum[i]=suma+sumb;
    }
    int max=0;
    rep(i,n){
        if(max<=sum[i]) max=sum[i];
    }
    cout <<max<<endl;
}

Measured memory_bytes: 256
<?php
  fscanf(STDIN,'%d',$n);
  $l = explode(' ',fgets(STDIN));
  $sum = 0;
  $max = 0;
  for($i = 0; $i < $n; $i++) {
    if ($i == 0) {
      $max = (int)$l[$i];
    }
    if ($max < (int)$l[$i]) {
      $max = (int)$l[$i];
    }
    $sum += (int)$l[$i];
  }
  if ( ($sum - $max) > $max ) {
    echo 'Yes';
  }else{
    echo 'No';
  }
?>

Measured memory_bytes: 3828
#include <stdio.h>
#include <math.h>
int main()
{
    int a[100001],b[100001],c[100001],n,i,flag=1;
    scanf("%d",&n);
    a[0]=b[0]=c[0]=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
        if((a[i]-a[i-1])<(abs(b[i]-b[i-1])+abs(c[i]-c[i-1])))
           {
           flag=0;
           break;}
        if(((a[i]-a[i-1])-(abs(b[i]-b[i-1])+abs(c[i]-c[i-1])))%2==1)
           {
               
               flag=0;
               break;
           }
    }
    if(flag==1)
        printf("Yes");
        else
            printf("No");
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
//Author: Ezio Sam
/* Shorthands */
#define ll long long
#define pb push_back
#define em emplace_back
#define mp make_pair
#define sp " "
#define cs "Case "
#define fi first
#define sn second

/* STL */
#define mem(a,n) memset(a, n, sizeof(a));
#define all(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define sz(x)  (int)x.size()
#define mx(v)  *max_element(v.begin(),v.end())
#define mxi(v) distance(v.begin(),max_element(v.begin(),v.end()))
#define mxa(a) *max_element(a, a.size())
#define r(a)   reverse(a.begin(),a.end())
/* loops */
#define fr(i,n)   for(__typeof(n) i=0;i<(n);i++)
#define fn(i,n)   for(__typeof(n) i=1;i<=(n);i++)
/*Special*/
#define Ezio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(something)  cerr<<#something<<" - "<<something<<"\n";

int main()
{

   Ezio
   ll t,m,n,x,a,b;
   string s;

   cin>>a>>b;

   m=(a-b*2);
   cout<<(m>0?m:0)<<endl;
   return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1LL<<30)

vector<int> adjlist[2005];
vector<int> d[2005];

signed main() {
  int N,X,Y;
  cin >> N >> X >> Y;
  X--; Y--;
  adjlist[0].push_back(1);
  adjlist[N-1].push_back(N-2);
  for(int i=1; i<N-1; i++) {
    adjlist[i].push_back(i-1);
    adjlist[i].push_back(i+1);
  }
  adjlist[X].push_back(Y);
  adjlist[Y].push_back(X);

  for(int s = 0; s<N; s++) {
    auto &ds = d[s];
    ds.resize(N);
    fill(ds.begin(), ds.end(), INF);
    queue<int> q;
    q.push(s);
    ds[s] = 0;
    while(q.size()) {
      int t = q.front(); q.pop();
      for(auto tt : adjlist[t]) {
        if(ds[tt] != INF) continue;
        ds[tt] = ds[t] + 1;
        q.push(tt);
      }
    }
  }

  map<int, int> ans;

//  cerr << "=========" << endl;
  for(int s=0; s<N; s++) {
    for(int t=0; t<N; t++) {
//      cerr << s << "\t" << t << "\t" << d[s][t] << endl;
      ans[d[s][t]]++;
    }
  }
//  cerr << "=========" << endl;

  for(int k=1; k<=N-1; k++) {
    cout << ans[k]/2 << endl;
  }  
}


Measured memory_bytes: 31872
#include<bits/stdc++.h>
using namespace std;
const int N = 505, M = 1e5 + 9;

int n, m, x[M], y[M], ans;
bitset<N>f[N];
bool can[N];

int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) scanf("%d%d", &x[i], &y[i]);
	for (int i = 1; i <= n; ++i) {
		f[i][i] = 1;
		for (int j = m; j; --j) {
			if (f[i][x[j]] && f[i][y[j]]) { can[i] = 1; break; }
			if (f[i][x[j]] || f[i][y[j]]) f[i][x[j]] = f[i][y[j]] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) if (!can[i]) for (int j = i + 1; j <= n; ++j) if (!can[j] && !(f[i] & f[j]).count()) ++ans;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
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; }
template<class T, class U>T rem(T a, U b) { return a - b*floor(a/b); }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vector<pair<ll, ll> > p(N);
        rep(i, 0, N) cin >> p[i].second >> p[i].first;
        sort(all(p));
        vll acc(N+1, 0);
        rep(i, 0, N) {
                acc[i+1] += acc[i] + p[i].second;
        }
        //print1d(acc);
        rep(i, 0, N) {
                if (acc[i+1] > p[i].first) {
                        cout << "No" << endl;
                        return 0;
                }
        }
        cout << "Yes" << endl;
}

Measured memory_bytes: 4992
from collections import Counter


def binomial_coefficient(n, r):
    res = 1
    for i in range(r):
        res *= (n - i)
        res //= (i + 1)
    return res


N, A, B = map(int, input().split())
V = list(map(int, input().split()))
V.sort(reverse=True)

C = Counter(V)

ave = sum(V[:A]) / A
num = V[A - 1]
Nnums = C[num]

if num == V[0]:
    B = min(B, Nnums)
    cnt = 0
    for i in range(A, B + 1):
        cnt += binomial_coefficient(Nnums, i)
else:
    for k, v in C.items():
        if k > num:
            A -= v
    cnt = binomial_coefficient(Nnums, A)

print(ave)
print(cnt)


Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<long long>A(N);
  for (int i = 0; i < N; i ++) cin >> A[i];
  vector<long long>sum(N + 1);
  map<long long, long long>f_s;
  sum[0] = 0;
  for (int i = 0; i < N; i ++) {
    sum[i + 1] = sum[i] + A[i];
    f_s[sum[i + 1]] ++;
  }
  long long ans = 0;
  for (int i = 0; i < N; i ++) {
    ans += f_s[sum[i]];
    f_s[sum[i + 1]] --;
  }
  cout << ans << endl;
}



Measured memory_bytes: 15872
#include<stdio.h>
#include<string.h>
#define M 103
#define Min 1000000000
void Matrix_Chain_Order(int p[],int n);
int main()
{
    int n;
    while(scanf("%d",&n) == 1){
        int p[M];
        memset(p,'0',M);
        int i;
        for(i = 0;i < n;i++)
            scanf("%d%d",&p[i],&p[i+1]);
        Matrix_Chain_Order(p,n);
    }

    return 0;
}

void Matrix_Chain_Order(int p[],int n)
{
    int m[n+1][n+1],s[n+1][n+1];
    //边界条件
    int i,j;
    for(i = 1;i <= n;i++)
        m[i][i] = 0;
    //计算每个子问题m[i,j]的解
    int l;
    for(l = 2;l <= n;l++){
        for(i = 1;i <= n-l+1;i++){
            j = i + l - 1;
            m[i][j] = Min;
            int k;
            for(k = i;k <= j-1;k++){
                int val;
                val = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if(m[i][j] > val){
                    m[i][j] = val;
                    s[i][j] = k;
                }
            }
        }
    }
    printf("%d\n",m[1][n]);
}


Measured memory_bytes: 2140
import math

N = int(input())
S = input()

arr = list(str(S))
cnt = 0

for i in range(1000):
  a = math.floor(i/100)
  b = math.floor((i-a*100)/10)
  c = i-a*100-b*10
  
  if str(a) in arr:
    an = arr.index(str(a))
    del arr[:an+1]
    
    if str(b) in arr:
      bn = arr.index(str(b))
      del arr[:bn+1]
      
      if str(c) in arr:
        cnt = cnt + 1
        
  arr = list(str(S))
      
print(cnt)

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

int main(int argc, const char * argv[]) {
    int a,b;
    int num, i, sum = 0;
    
    cin >> a >> b;
    num = b - a;
    
    for(i = 0; i < num; i++) {
        sum += i;
    }
    cout << sum - a;
}


Measured memory_bytes: 256
package main

import(
    "fmt"
    "sort"
    "strings"
)



func main() {
    var h,w int
    fmt.Scan(&h,&w)
    s := scanString(h)
    for i:=0;i<h;i++{
        fmt.Println(s[i])
        fmt.Println(s[i])
    }
}





// Pairsort
type Pair struct {
    first,second int64
}

type By func(p1, p2 *Pair) bool

func (by By) Sort(pairs []Pair) {
    ps := &pairSorter{
            pairs : pairs,
            by: by,
    }
    sort.Sort(ps)
}

type pairSorter struct {
    pairs []Pair
    by func(p1, p2 *Pair) bool
}

func (s *pairSorter) Len() int {
    return len(s.pairs)
}

func (s *pairSorter) Swap(i, j int) {
    s.pairs[i], s.pairs[j] = s.pairs[j], s.pairs[i]
}

func (s *pairSorter) Less(i, j int) bool {
    return s.by(&s.pairs[i], &s.pairs[j])
}

func first (p1, p2 *Pair) bool {
        return p1.first < p2.first
}

func second (p1, p2 *Pair) bool {
        return p1.second < p2.second
}
// end



func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func makeTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}

func sortString(s string) string{
    t := strings.Split(s, "")
    sort.Strings(t)
    return strings.Join(t, "")
}

func reverseString(s string) string{
    t := []rune(s)
    for i,j := 0, len(s)-1 ; i < j ; i, j = i+1, j-1 {
        t[i], t[j] = t[j], t[i]
    }
    return string(t)
}

func inside(h,w,H,W int) bool{
    if h>=0 && h<H && w>=0 && w<W{
        return true
    }
    return false
}


Measured memory_bytes: 640