akhauriyash/Code-Regression huggingface dataset:
import itertools
n,k=map(int,input().split())

if k>(n-1)*(n-2)//2:
    print(-1)
else:
    c=(n-1)*(n-2)//2-k
    print(n-1+c)
    for i in range(1,n):
        print(i,n)
    for a,b in itertools.combinations(range(1,n),2):
        if c==0:
            break
        print(a,b)
        c-=1

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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  
  for (int i=0; i<N; i++) {
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  
  int A = 0;
  int B = 0;
  
  for (int i=0; i<N; i++) {
    if (i%2 == 0) {
      A += vec.at(i);
    }
    else {
      B += vec.at(i);
    }
  }
  
  cout << A-B;
}



Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();
    String[] s = new String[n];

    for (int i = 0; i < n; i++) {
      s[i] = sc.next();
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j + 2 < s[i].length(); j++) {
        if(s[i].substring(j, j + 2).equals("AB")) ans++;
      }
    }

    int bxa = 0;
    int bxx = 0;
    int xxa = 0;
    for (int i = 0; i < n; i++) {
      char st = s[i].charAt(0);
      char en = s[i].charAt(s[i].length() - 1);
      if (st == 'B' && en == 'A') bxa++;
      else if (st == 'B') bxx++;
      else if (en == 'A') xxa++;
    }

    if (bxa > 0) {
      ans += bxa - 1;
      if (xxa > 0) {
        ans++; xxa--;
      }
      if (bxx > 0) {
        ans++; bxx--;
      }
    }
    ans += Math.min(xxa, bxx);
    os.println(ans);
  }
}


Measured memory_bytes: 32580
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    int cnt = 0;
    for (int j = i; j < s.size(); j++) {
      if (s[j] == 'A' || s[j] == 'C' || s[j] == 'G' || s[j] == 'T') {
        cnt++;
      } else {
        break;
      }
    }
    ans = max(ans, cnt);
    cnt = 0;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
//Candies.cpp (C)
#include <iostream>
using namespace std;

int main(){
  int N,S,Smax;
  S = 0;
  Smax = 0;
  int A[3][110];
  cin >> N;
  for(int i = 1; i <= 2; i++){
    for(int j = 1; j <= N; j++) cin >> A[i][j];
  }
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= i; j++) S += A[1][j];
    for(int k = i; k <= N; k++) S += A[2][k];
    Smax = max(Smax,S);
    S = 0;
  }
  printf("%d\n", Smax);
}


Measured memory_bytes: 256
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

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

int main() {
	string S;
	cin >> S;

	bool flag_same = false;
	REP(i, S.size()) {
		REP(j, S.size()) {
			if ((i != j) && (S[i] == S[j])) {
				flag_same = true;
			}
		}
	}

	if (flag_same) {
		cout << "no" << endl;
	} 
	else { 
		cout << "yes" << endl;
	}

	return 0;
}


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

#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define endl "\n"

#define max(a, b) ((a > b) ? a : b)
#define min(a, b) ((a > b) ? b : a)

#define forn(i, a, n) for (int i = a; i < n; i++)
#define forns(i, a, n, step) for (int i = a; i < n; i += step)
#define fornr(i, a, n) for (int i = n; i > a; --i)
#define fornrs(i, a, n, step) for (int i = n; i > a; i -= step)
#define forlimits(i, l, r) for (int i = l; i <= r; i++)

// Choose auto x when you want to work with copies.
#define foritc(i, v) for (auto i = v)
// Choose auto &x when you want to work with original items and may modify them.
#define foritm(i, v) for (auto &i = v)
// Choose auto const &x when you want to work with original items and will not modify them.
#define forit(i, v) for (auto const &i = v)

#define all(v) (v).begin(), (v).end()

#define fill(arr, n, k) \
    forn(i, 0, n) { arr[i] = k; }

#define print(arr, n)                        \
    forn(i, 0, n) { cout << arr[i] << " "; } \
    cout << endl;

#define intersection(a, b, out) set_intersection(all(a), all(b), out.begin())

#define sum_n(n) (n * (n + 1) / 2)
typedef long long ll;
void solve();

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
    return 0;
}

void solve() {
    ll n;
    cin >> n;
    if (n % 1000 == 0) {
        cout << 0 << endl;
    } else {
        ll num = (n / 1000 + 1) * 1000;
        cout << (num - n) << endl;
    }
}

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

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

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

// O(N*M)

set<ll> makec(){
    set<ll> c;
    c.insert(1);
    ll a = 6;
    while(a <= 100000){
        c.insert(a);
        a *= 6;
    }
    ll b = 9;
    while(b <= 100000){
        c.insert(b);
        b *= 9;
    }
    return c;
}

int main() {
    ll n; cin >> n;
    set<ll> c = makec();
    Vl dp(n+1, INF);
    dp[0] = 0;
    rep(i, 0, n){
        for(auto j : c){
            if(i + j > n) continue;
            chmin(dp[i+j], dp[i]+1);
        }
    }
    co(dp[n]);

    return 0;
}



Measured memory_bytes: 3976
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int f[100][10];
ll p[100][11];

int main(void){
  int n;
  cin >> n;
  REP(i, n) REP(j, 10) cin >> f[i][j];
  REP(i, n) REP(j, 11) cin >> p[i][j];
  ll ans = -(ll)(1e18);
  FOR(i, 1, 1<<10){
    ll sum = 0;
    REP(j, n){
      int count = 0;
      REP(k, 10) if((i>>k&1) && f[j][k]) count++;
      sum += p[j][count];
    }
    chmax(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n, k = [int(x) for x in input().split()]

vs = [int(x) for x in input().split()]

ns = [-v for v in vs if v < 0][::-1]
ps = [v for v in vs if v >= 0]

res = float('inf')
if len(ps) >= k:
    res = ps[k-1]
for i in range(min(k, len(ns))):
    if len(ps) + i + 1 < k: continue
    res = min(res, ns[i] * 2 + (ps[k - i - 2] if k > i + 1 else 0))
    res = min(res, ns[i] + (ps[k - i - 2] if k > i + 1 else 0) * 2)

print(res)


Measured memory_bytes: 14564
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Maxn=205;
int ch[Maxn];
int n,m;
int a[Maxn][Maxn],A[Maxn][Maxn],r[Maxn*Maxn];
bool ban[Maxn][Maxn];
int B[Maxn][Maxn];
namespace Net{
	struct edge{
		int to,cap,rev;
		edge(int _to=0,int _cap=0,int _rev=0){
			to=_to,cap=_cap,rev=_rev;
		}
	};
	vector<edge> G[Maxn];
	void add_edge(int u,int v,int c){
		G[u].pb(edge(v,c,G[v].size()));
		G[v].pb(edge(u,0,G[u].size()-1));
	}
	int dist[Maxn],seen[Maxn],q[Maxn],sq,eq;
	int src=203,snk=204;
	void Clear(){
		for (int i=0;i<Maxn;i++) G[i].clear();
	}
	void bfs(int s){
		for (int i=0;i<Maxn;i++) dist[i]=-1;
		dist[s]=0;sq=eq=0;
		q[eq++]=s;
		while (sq<eq){
			int x=q[sq++];
			for (int i=0;i<G[x].size();i++){
				int v=G[x][i].to;
				if (G[x][i].cap){
					if (dist[v]==-1){
						dist[v]=dist[x]+1;
						q[eq++]=v;
					}
				}
			}
		}
	}
	int dfs(int now,int dest,int f){
		if (now==dest) return f;
		for (int &i=seen[now];i<G[now].size();i++){
			edge &e=G[now][i];
			if (e.cap && dist[e.to]==dist[now]+1){
				int v=e.to;
				int fl=dfs(v,dest,min(f,e.cap));
				if (fl){
					e.cap-=fl;
					G[e.to][e.rev].cap+=fl;
					return fl;
				}
			}
		}
		return 0;
	}
	int dinic(int s=src,int t=snk){
		int ret=0;
		while (1){
			memset(seen,0,sizeof(seen));
			bfs(s);
			if (dist[t]==-1) return ret;
			while (1){
				int ff=dfs(s,t,2147483647);
				if (!ff) break;
				ret+=ff;
 			}
		}
	}
	void Solve(){
		for (int i=1;i<=n;i++){
			for (int j=0;j<G[i].size();j++){
				if (!G[i][j].cap){
					int v=G[i][j].to;
					if (v<=n+n){
						//cout<<"CON"<<i<<""
						ch[i]=v-n;
					}
				}
			}
		}
	}
}
vector<int> S[Maxn];
int main(){
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n*m;i++){
		r[i]=(i-1)/m+1;
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			A[i][j]=r[a[i][j]];
		}
	}
	for (int i=1;i<=m;i++){
		//cout<<i<<endl;
		Net::Clear();
		for (int j=1;j<=n;j++){
			Net::add_edge(Net::src,j,1);
			Net::add_edge(j+n,Net::snk,1);
		}
		for (int j=1;j<=n;j++){
			for (int k=1;k<=m;k++){
				if (ban[j][k]) continue;
				Net::add_edge(A[j][k],j+n,1);
			}
		}
		int v=Net::dinic();
		//cout<<v<<endl;
		//assert(v==n);
		Net::Solve();
		for (int j=1;j<=n;j++){
			int pos=ch[j];
			for (int k=1;k<=m;k++){
				if (!ban[pos][k] && A[pos][k]==j){
					ban[pos][k]=1;
					B[pos][i]=a[pos][k];
					break;
				}
			}
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			printf("%d ",B[i][j]);
		}
		printf("\n");
	}
	for (int i=1;i<=m;i++){
		for (int j=1;j<=n;j++){
			S[i].pb(B[j][i]);
		}
		sort(S[i].begin(),S[i].end());
		for (int j=1;j<=n;j++){
			B[j][i]=S[i][j-1];
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			printf("%d ",B[i][j]);
		}
		printf("\n");
	}
	return 0;
}

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

int main(){
	ll a, b, c, d, e;
	cin >> a >> b >> c >> d;
	ll a1, b1;
	ll lcm = c * d / __gcd(c, d);
	b1 = b - b/c - b/d + b/lcm;
	a--;
	a1 = a - a/c - a/d + a/lcm;
	cout << b1-a1 << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n,t,i;
	for(i=0;i<4;i++){
		scanf("%d %d",&t,&n);
		if(t==1){
			printf("%d\n",n*6000);
		}
		else if(t==2){
			printf("%d\n",n*4000);
		}
		else if(t==3){
			printf("%d\n",n*3000);
		}
		else if(t==4){
			printf("%d\n",n*2000);
		}
	}
	return 0;
}



Measured memory_bytes: 2076
X,Y,A,B,C=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
tmp=sorted(p)
P=tmp[::-1]
tmp=sorted(q)
Q=tmp[::-1]
tmp=sorted(r)
R=tmp[::-1]
tmp=P[:X]+Q[:Y]+R
tmp=sorted(tmp)
tmp=tmp[::-1]
ans=sum(tmp[:X+Y])
print(ans)


Measured memory_bytes: 24368
import java.util.Scanner;

public class Main {
	static int intN =0;
	static int sosuCnt =0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.nextLine();
		//String[] h = sc.nextLine().split(" ");

		int intN = Integer.parseInt(n);

		long sum=0;
		for (int i = 0;i < intN;i++) {
			sum=sum+i;
		}

		System.out.println(sum);
	}
}

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

int main() {
  int N, K, R, S, P;
  string T;
  cin >> N >> K >> R >> S >> P >> T;

  map<char, int> point;
  point['s'] = R;
  point['p'] = S;
  point['r'] = P;

  int totalSum = 0;
  for (int i = 0; i < K; i++) {
	totalSum += point[T[i]];
    int sameCount = 0;
    for (int j = i+K; j < N; j+=K) {
      if(T[j-K]==T[j] && sameCount==0) {
		sameCount++;
        continue;
      }
      totalSum += point[T[j]];
	  sameCount = 0;
    }
  }
  
  cout << totalSum << endl;

  return 0;
}

Measured memory_bytes: 512
object Main {
  def main(args: Array[String]): Unit = {
    io.Source.stdin.getLines foreach (n => println(pi(n.toInt)))
  }
  val primes: IndexedSeq[Int] = prime_sieve(50000)
  val pi_cache: collection.mutable.Map[Int, Int] = collection.mutable.Map.empty
  val phi_cache: collection.mutable.Map[(Int, Int), Int] = collection.mutable.Map.empty

  def prime_sieve(x: Int): IndexedSeq[Int] = {
    val n = x - x % 6 + 6
    val correction = if (x % 6 > 1) 1 else 2
    val sieve = Array.fill(n/3)(true)
    for (i <- 1 to (Math.sqrt(n) / 3).toInt if sieve(i)) {
      val k = (3 * i + 1) | 1
      for (j <- (k * k) / 3 until sieve.length by 2*k) sieve(j) = false
      for (j <- (k*(k-2*(i&1)+4))/3 until sieve.length by 2*k) sieve(j) = false
    }
    2 +: 3 +: (for (i <- 1 until n / 3 - correction if sieve(i)) yield (3*i+1)|1)
  }
  def bisect(n: Int): Int = {
    def loop(left: Int, right: Int): Int = {
      val mid = (left + right) / 2
      if (primes(mid) <= n && n < primes(mid+1)) mid+1
      else if (n < primes(mid)) loop(left, mid)
      else loop(mid+1, right)
    }
    if (n < primes.head) 0
    else if (n >= primes.last) primes.length
    else loop(0, primes.length)
  }
  def pi(x: Int): Int =
    pi_cache.getOrElseUpdate(x,
      if (x <= primes.last) bisect(x)
      else {
        val a = pi(Math.sqrt(Math.sqrt(x)).toInt)
        val b = pi(Math.sqrt(x).toInt)
        val c = pi(Math.cbrt(x).toInt)
        var result = phi(x, a) + ((b + a - 2) * (b - a + 1)) / 2
        for (i <- a + 1 to b) {
          val w = x / primes(i - 1)
          val b_i = pi(Math.sqrt(w).toInt)
          result -= pi(w)
          if (i <= c)
            for (j <- i to b_i)
              result = result - pi(w / primes(j - 1)) + j - 1
        }
        result
      }
    )
  def phi(x: Int, a:Int): Int =
    phi_cache.getOrElseUpdate(
      (x,a),
      {
        if (a == 1) (x + 1) / 2
        else phi(x, a - 1) - phi(x / primes(a - 1), a - 1)
      }
    )
}

Measured memory_bytes: 45184
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

h = list(map(lambda x: abs(a-(t-x*0.006)), h))

min_temp = 10000000
ans = -1
for i in range(n):
    if min_temp > h[i]:
        min_temp = h[i]
        ans = i+1

print(ans)


Measured memory_bytes: 3060
#include <stdio.h>

int main(void)
{
    int a, b, c, d, e, f;
    int det;
    double x, y;

    while (scanf("%d %d %d %d %d %d",
           &a, &b, &c, &d, &e, &f) != EOF) {
        det = a * e - b * d;
        x = (double)(e * c + -b * f) / det;
        y = (double)(-d * c + a * f) / det;
        printf("%.3f %.3f\n", x + 0, y + 0);
    }

    return 0;
}

Measured memory_bytes: 0
K = int(input())
X, Y = [int(_) for _ in input().split()]
x, signx = abs(X), -1 if X < 0 else 1
y, signy = abs(Y), -1 if Y < 0 else 1
ans = [(x, y)]
if x + y != K:
    while (x + y) > 2 * K:
        dx = min(K, x)
        dy = K - dx
        x -= dx
        y -= dy
        ans += [(x, y)]

    def calczw(x, y):
        #z+w=abs(z-x)+abs(w-y)=K
        if x > y:
            #z+w=x-z+w-y=K and z<=x and w>=y
            z = (x - y) // 2
            w = K - z
        else:
            #z+w=z-x+y-w=K and z>=x and w<=y
            w = (y - x) // 2
            z = K - w
        return (z, w)

    z, w = calczw(x, y)
    if abs(z - x) + abs(w - y) != K:
        dx = min(K, x)
        dy = K - dx
        x -= dx
        if y > dy:
            y -= dy
        else:
            y += dy
        ans += [(x, y)]
        z, w = calczw(x, y)
    if abs(z - x) + abs(w - y) != K:
        print(-1)
        exit()
    ans += [(z, w)]
print(len(ans))
for x, y in ans[::-1]:
    print(x * signx, y * signy)


Measured memory_bytes: 34432
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [float('Inf') for i in range(n)]
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i-j<0:
            break
        
        dp[i]= min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])

Measured memory_bytes: 56800
#include <cstdio>
using namespace std;
int main(){
	register int a, b, c, i;
	register long long k, ans;
	scanf("%d %d %d %lld", &a, &b, &c, &k);
	if (k & 1) printf("%d", b - a);
	else printf("%d", a - b);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    sort(all(vec));
    int ans = 0;
    rep(i,K){
        ans += vec[i];
    }
    cout << ans << endl;
}

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

#define rep(i,n) for(int i = 0;i < n;++i)
#define rep2(i,n,m) for(int i = n;i < m;++i)
#define all(v) v.begin(),v.end()

using namespace std;
using ll = long long;


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


    int n,m;
    cin >> n;
    map<int,int> memo;
    rep(i,n){
        cin >> m;
        if(memo.count(m)){
            cout << "NO" << endl;
          return 0;
        }else{
            memo[m]=1;
        }
    }
  cout << "YES" << endl;

}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define forn(i,a,b) for(ll i=a;i<=b;i++)
#define ft first
#define sd second
#define sz size()
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
//cout << fixed << setprecision(12) <<x<<endl;
const int MAX = 1e7;
ll a[MAX],b[MAX];
int main(){
fastIO;
#ifdef LOCAL
     freopen("in.txt", "r", stdin);
#endif
ll n,m,k,sumA=0,sumB=0;
cin>>n>>m>>k;
forn(i,1,n){
    int x;
    cin>>x;
    sumA+=x;
    a[i]=sumA;
}
forn(i,1,m){
    int x;
    cin>>x;
    sumB+=x;
    b[i]=sumB;
}
ll c=0;
forn(i,0,n){
    ll res = k-a[i];
   // cout<<res<<endl;
    if(res<0){
        continue;
    }
    ll aux = lower_bound(b,b+m,res)-begin(b);
    if(aux>m || b[aux]>res){
        aux--;
    }
    //cout<<aux<<endl;
    c=max(c,i+aux);
    //cout<<c<<end;¿l;
}
cout<<c<<endl;

}



Measured memory_bytes: 6712
/*
LANG:C++
PROB:

*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)


using namespace __gnu_pbds;
using namespace std;


typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
typedef unsigned long long ui64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
bool cmp(pi64 a,pi64 b)
{
  return a.se*a.fi<a.se*b.fi;
}

  int main()
  {
ios::sync_with_stdio(false);
    cin.tie(nullptr);
i64 n,m,c;
cin>>n>>m;
vector<pi64>a;
forn(i,n)
{i64 b,c;
  cin>>c>>b;
  a.pb({c,b});
}
sort(a.begin(),a.end(),cmp);
i64 count=0,price=0;
int j=0;
while(count<m)
{
if(count+a[j].se>m-1)
{
  price+=(m-count)*a[j].fi;
  count+=m-count;
  break;
}

  count+=a[j].se;
// cout<<price<<"\n";
  price+=a[j].fi*a[j].se;
  j++;
}
// cout<<count<<"\n";
cout<<price;
    return 0;
  }


Measured memory_bytes: 2420
N, MOD = int(input()), 10**9 + 7
memo = [{} for i in range(N+1)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if "".join(t).count("AGC") >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, "TTT"))

Measured memory_bytes: 3872
N, ma, mb = map(int, input().split())
a = [0]*N
b = [0]*N
c = [0]*N
NMAX = 40
ABMAX = 10
INF = 1000000
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[[INF]*(NMAX*ABMAX+1)for _ in range(NMAX*ABMAX+1)]for _ in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for ca in range(NMAX*ABMAX+1):
        for cb in range(NMAX*ABMAX+1):
            if dp[i][ca][cb] == INF:
                continue
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            dp[i+1][ca+a[i]][cb+b[i]
                             ] = min(dp[i+1][ca+a[i]][cb+b[i]], dp[i][ca][cb]+c[i])
ans = INF
for ca in range(1, NMAX*ABMAX+1):
    for cb in range(1, NMAX*ABMAX+1):
        if ca * mb == cb * ma:
            ans = min(ans, dp[N][ca][cb])
print(ans if ans != INF else -1)


Measured memory_bytes: 65324
#include <cstdio>


int main(){
    int W, H, x, y, r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
if ((0 <= x - r && x + r <= W) && (0 <= y - r && y + r <= H)) printf("Yes\n");
else printf("No\n");
    return 0;
}


Measured memory_bytes: 2696
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans;
int ch(int x){
  int a[2]={},c=0,f=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='-')f++;
    if(i==x)c++;
    if(i==x&&s[i]=='0')return 0;
    a[c]=a[c]*10+(s[i]-'0');
  }
  if(f)a[0]*=(-1);
  int p=(a[0]+a[1])/2;
  int t=a[1]-p;
  if(p-t==a[0]&&p>=0&&t>=0)return 1;
  return 0;
}
main(){
  cin>>s;
  for(int i=0;i<s.size();i++)
    ans+=ch(i);
  cout<<ans<<endl;
}

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

int main(){
  int n;
  cin >> n;
  int a[n+1];
  a[0]=0;
  for(int i=0;i<n;i++){
    cin >> a[i+1];
  }
  sort(a,a+n+1);
  int ans=0;
  for(int i=0;i<(n+1)/2;i++){
    ans=ans+a[n-2*i]-a[n-2*i-1];
  }
  cout << ans << endl;
}
  

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<stack>
using namespace std;
#define ll long long
#define mod 1000000007

int a[100005];
int a2[100005];
int main()
{
    int i,t,j,len,temp,N,Q,K;
    while(scanf("%d%d%d",&N,&K,&Q)!=EOF)
    {
        memset(a2,0,sizeof(a2));
        for(i=0;i<Q;i++)
        {
            scanf("%d",&temp);
            a2[temp]++;
        }
        for(i=1;i<=N;i++)
        {
            a[i]=K-Q+a2[i]; //不成功的局都得-1分
            if(a[i]<=0)
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
    return 0;
}



Measured memory_bytes: 1408
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>

using namespace std;

int main(void){
  string s,t;
  cin >> s;
  cin >> t;

  vector<char> h_s(26,-1);
  vector<char> h_t(26,-1);
  //cout << s << endl;
  //cout << t << endl;

  for(int i=0;i<s.size();i++){
    int ss=s[i]-'a';
    int tt=t[i]-'a';
    if(h_s[ss] >= 0){
      if(h_s[ss] != t[i]){
        cout << "No" <<endl;
        return 0;
      }
    }
    else if(h_t[tt] >= 0){
      if(h_t[tt] != s[i]){
        cout << "No" <<endl;
        return 0;
      }
    }
    else{
      h_s[ss] = t[i];
      h_t[tt] = s[i];
    }
    //if(s[i] == t[i]) continue;
    //else{
      /*
      if( h[s[i]-'a'] ){
        cout << "No" << endl;
        return 0;
      }

      else{
        h[s[i]-'a']=1;
      }
      */
      //char c1=s[i];
      //char c2=t[i];
      //cout << c1 << " " << c2 << endl;
      /*
      for(int j=0;j<s.size();j++){

        if(s[j] == c1) s[j]=c2;
        else if(s[j] == c2) s[j]=c1;

      }
      */
      //replace(s.begin(),s.end(),c1,c2);
      //replace(s.begin(),s.end(),c2,c1);
    //}


  }
  //if(s==t) cout << "Yes" << endl;
  //else cout << "No" << endl;
  cout << "Yes" << endl;
  //cout << s << endl;
  //cout << "Yes" << endl;

  return 0;
}


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

int main(){
    int n;
    cin >> n;
    map<long long int, int> mp;
    for(int i=0;i<n;++i){
        long long int a;
        cin >> a;
        mp[a]++;
    }
    long long int maxi1=0, maxi2=0;
    for(auto elm : mp){
        while(elm.first >= maxi1 && elm.second > 1){
            maxi2 = maxi1;
            maxi1 = elm.first;
            elm.second -= 2;
        }
    }
    cout << maxi1 * maxi2 << endl;

    return 0;
}


Measured memory_bytes: 6528
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cctype>

#define mp make_pair
#define pb push_back
#define REP(i,a,n) for(int i = a;i < (n);i++)
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define range(x,min,max) ((min) <= (x) && (x) <= (max))

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<vector<int> > VII;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef pair<int,int> PII;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n, r;
	VI ps, cs, cards, temp;
	while(1){
		ps.clear();
		cs.clear();
		cards.clear();
		cin >> n >> r;
		if(n == 0 && r == 0) break;
		rep(i, n){
			cards.pb(i + 1);
		}
		reverse(all(cards));
		rep(i, r){
			int p, c;
			cin >> p >> c;
			ps.pb(p);
			cs.pb(c);
		}
		rep(i, r){
			temp.clear();
			REP(j, ps[i] - 1, ps[i] + cs[i] - 1){
				temp.pb(cards[j]);
			}
			rep(j, ps[i] - 1){
				temp.pb(cards[j]);
			}
			REP(j, ps[i] + cs[i] - 1, cards.size()){
				temp.pb(cards[j]);
			}
			cards.clear();
			cards = temp;
		}
		cout << cards[0] << endl;
	}
	return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef double db;

#define mp make_pair
#define pb push_back
#define pt(i) printf("%lld\n",(ll)i)
#define mp make_pair
#define ff first
#define ss second
#define pi acos(-1.0)
ll md=1000000007;

ll in() { ll a;scanf("%lld",&a); return a;}
db din(){ db a;scanf("%lf",&a); return a; }
ll bigmod(ll b, ll p,ll md){if(p==0) return 1;if(p%2==1){ return ((b%md)*bigmod(b,p-1,md))%md;} else {ll y=bigmod(b,p/2,md);return (y*y)%md;}}
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b);}

long long getRandom(long long a,long long b){
    long long ret = (long long)rand()*(long long)rand();
    ret %= (b - a + 1);
    ret += a;
    return ret;
}

int n;
db dp[3005][3005],ar[3005];

db solve(int pos,int don)
{
	if(2*don>n)
		return 1;
	if(pos==n)
		return 0;
	if(dp[pos][don]!=-1)
		return dp[pos][don];
	return dp[pos][don]=(ar[pos]*solve(pos+1,don+1)+(1-ar[pos])*solve(pos+1,don));
}

int main()
{
//	freopen("in.c","r",stdin);
//	freopen("out.c","w",stdout);
	n=in();
	for(int i=0;i<n;i++)
		ar[i]=din();
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			dp[i][j]=-1;
	printf("%.10lf\n",solve(0,0) );
}



Measured memory_bytes: 70912
#include <queue>
#include <vector>
#include <iostream>
#pragma warning(disable : 4996)
using namespace std;
void reader(int *x) {
	int k = getchar_unlocked(); *x = k - '0';
	while (1) {
		k = getchar_unlocked();
		if (k < '0' || k > '9') break;
		*x = ((*x) << 1) + ((*x) << 3) + k - '0';
	}
}
int N, M, Q, a[200009], b[200009], r[200009], f[200009], dist[200009], ret[200009]; vector<int> g[200009], gt[200009]; bool vis[100009];
int main() {
	reader(&N), reader(&M), reader(&Q);
	for (int i = 0; i < M; i++) {
		reader(&a[i]), reader(&b[i]), a[i]--, b[i]--;
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	fill(f, f + M, -1);
	for (int i = 0; i < Q; i++) reader(&r[i]), r[i]--, f[r[i]] = i;
	queue<int> que1; que1.push(0);
	fill(dist, dist + N, -1); dist[0] = 0;
	while (!que1.empty()) {
		int u = que1.front(); que1.pop();
		for (int i : g[u]) {
			if (dist[i] == -1) {
				dist[i] = dist[u] + 1;
				que1.push(i);
			}
		}
	}
	for (int i = 0; i < M; i++) {
		if (dist[a[i]] == dist[b[i]]) continue;
		if (dist[a[i]] > dist[b[i]]) swap(a[i], b[i]);
		if (f[i] == -1) gt[a[i]].push_back(b[i]);
	}
	int cnt = N - 1;
	vector<bool> vis(N); vis[0] = true;
	queue<int> que2; que2.push(0);
	while (!que2.empty()) {
		int u = que2.front(); que2.pop();
		for (int i : gt[u]) {
			if (!vis[i]) {
				vis[i] = true; cnt--;
				que2.push(i);
			}
		}
	}
	for (int i = Q - 1; i >= 0; i--) {
		ret[i] = cnt;
		if (dist[a[r[i]]] == dist[b[r[i]]]) continue;
		gt[a[r[i]]].push_back(b[r[i]]);
		if (vis[a[r[i]]] && !vis[b[r[i]]]) {
			vis[b[r[i]]] = true; cnt--;
			queue<int> que; que.push(b[r[i]]);
			while (!que.empty()) {
				int u = que.front(); que.pop();
				for (int j : gt[u]) {
					if (!vis[j]) {
						vis[j] = true, cnt--;
						que.push(j);
					}
				}
			}
		}
	}
	for (int i = 0; i < Q; i++) printf("%d\n", ret[i]);
	return 0;
}

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

int ctoi(char c){
  return c - '0';
}

int main() {
  vector<char> a(10);
  for(int i = 0; i < 10; i++){
    cin >> a.at(i); 
  }
  if(ctoi(a.at(5))*10 + ctoi(a.at(6)) >= 5) cout << "TBD" << endl;
  else cout << "Heisei" << endl;
}


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

long long F[300000] = {}, RF[300000] = {}, MOD = 1000000007;

long long Calc(long long A, long long B, long long C) {
	if (B == 0) return 1;
	if (B % 2 == 0) {
		long long D = Calc(A, B / 2, C) % C;
		return (D * D) % C;
	}
	return (A * Calc(A, B - 1, C)) % C;
}

long long Comb(long long A, long long B) {
	long long RT = 1;
	RT *= F[A]; RT = RT % MOD;
	RT *= RF[B]; RT = RT % MOD;
	RT *= RF[A - B]; RT = RT % MOD;
	return RT;
}

void init(long long N) {
	F[0] = 1, F[1] = 1, RF[0] = 1, RF[1] = 1;
	for (int i = 2; i <= N; i++) F[i] = (F[i - 1] * i) % MOD;
	for (int i = 2; i <= N; i++) RF[i] = Calc(F[i], MOD - 2, MOD);
}

int main() {
	long long N, A, B, C, ANS = 0, PLUS = 0;
	cin >> N >> A >> B >> C;
	init(N * 2);
	for (int i = 0; i < N; i++) {
		long long X = 1;
		X = Comb(N + i - 1, i);
		X *= Calc(A, N, MOD); X = X % MOD;
		X *= Calc(B, i, MOD); X = X % MOD;
		X *= Calc(Calc(A + B, MOD - 2, MOD), N + i, MOD); X = X % MOD;
		X *= (N + i); X = X % MOD;
		X *= 100; X = X % MOD;
		X *= Calc(100 - C, MOD - 2, MOD); X = X % MOD;
		ANS += X; ANS = ANS % MOD;
	}
	for (int i = 0; i < N; i++) {
		long long X = 1;
		X = Comb(N + i - 1, i);
		X *= Calc(B, N, MOD); X = X % MOD;
		X *= Calc(A, i, MOD); X = X % MOD;
		X *= Calc(Calc(A + B, MOD - 2, MOD), N + i, MOD); X = X % MOD;
		X *= (N + i); X = X % MOD;
		X *= 100; X = X % MOD;
		X *= Calc(100 - C, MOD - 2, MOD); X = X % MOD;
		ANS += X; ANS = ANS % MOD;
	}
	cout << ANS << endl;
}

Measured memory_bytes: 3840
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	public static class PriorityQueue{
		int[] heap;
		int size;
		
		public PriorityQueue(){
			heap = new int[2000000];
			size = 0;
		}
		
		private void maxHeapify(int i){
			int l = i * 2 + 1;
			int r = i * 2 + 2;
		
			int largest = -1;
		
			if(l < size && heap[l] > heap[i]){
				largest = l;
			}else{
				largest = i;
			}
		
			if(r < size && heap[r] > heap[largest]){
				largest = r;
			}
		
			if(largest != i){
				int tmp = heap[i];
				heap[i] = heap[largest];
				heap[largest] = tmp;
			
				maxHeapify(largest);
			}
		}
		
		public void insert(int value){
			heap[size++] = value;
			
			int current = size - 1;
			while(current != 0 && heap[(current - 1) / 2] < heap[current]){
				int tmp = heap[(current - 1) / 2];
				heap[(current - 1) / 2] = heap[current];
				heap[current] = tmp;
				
				current = (current - 1) / 2;
			}
		}
		
		public int extractMax(){
			final int ret = heap[0];
			heap[0] = heap[--size]; 
			this.maxHeapify(0);
			
			return ret;
		}
		
		public String toString(){
			StringBuilder sb = new StringBuilder();
			sb.append("[");
			for(int i = 0; i < size; i++){
				if(i != 0){
					sb.append(", ");
				}
				sb.append(heap[i]);
			}
			sb.append("]");
		
			return sb.toString();
		}
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		PriorityQueue queue = new PriorityQueue();
		while(true){
			final String ops = sc.next();
			
			//System.out.println(queue);
			
			if("insert".equals(ops)){
				final int value = sc.nextInt();
				queue.insert(value);
			}else if("extract".equals(ops)){
				System.out.println(queue.extractMax());
			}else if("end".equals(ops)){
				break;
			}
			
		}
		
	}

	public static class Scanner {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public void close() throws IOException {
			br.close();
		}
	}

}

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

class Program
{
    static void Main(string[] args)
    {
        int[] NAB = ReadLineParseIntArray();
        int N = NAB[0];
        int A = NAB[1];
        int B = NAB[2];
        WriteLine(Min(B, N * A));
    }
    static int ReadLineParseInt() => int.Parse(ReadLine());
    static int[] ReadLineParseIntArray() => ReadLine().Split(' ').Select(int.Parse).ToArray();
}

Measured memory_bytes: 13268
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;


void main() {
    auto s = readln.split;
    writefln("A%cC", s[1].front.toUpper);
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define f(i,a,b,c) for(ll i=a;i<b;i+=c)
#define r(i,a,b,c) for(ll i=a;i>=b;i-=c)
#define mod 1000000007

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s; cin >> s;
    if(s[s.length()-1]=='s') cout << s << "es";
    else cout << s << 's';
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
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; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;


int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i = 0;i<N;i++) {
        ll a;
        cin >> a;
        A.at(i) = a;
    }
    map<ll,ll> mp_X;
    map<ll,ll> mp_Y;
    for (ll i = 0;i<N;i++) {
        mp_X[A.at(i) + i]++;
    }
    for (ll i = 0;i<N;i++) {
        mp_Y[i - A.at(i)]++;
    }
    ll ans = 0;
    for (pair<ll,ll> p : mp_X) {
        ans += p.second * mp_Y[p.first];
    } 
    cout << ans << endl;
}


Measured memory_bytes: 39112
s = input()
d = 0

if s == 'MON':
    d = 6
elif s == 'TUE':
    d = 5
elif s == 'WED':
    d = 4
elif s == 'THU':
    d = 3
elif s == 'FRI':
    d = 2
elif s == 'SAT':
    d = 1
elif s == 'SUN':
    d = 7

print(d)

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

int main() {
    int abcd;
    cin >> abcd;
    int num[4] = {abcd / 1000, (abcd / 100) % 10, (abcd / 10) % 10, abcd % 10};
    int sum;
    bool match = false;

    for (int bit = 0; bit < (1 << 3); bit++) {
        sum = num[0];
        for (int i = 0; i < 3; i++) {
            if (bit & (1 << i)) sum -= num[i + 1];
            else
                sum += num[i + 1];
        }
        if (sum == 7) {
            match = true;
            cout << num[0];
            for (int j = 0; j < 3; j++) {
                if (bit & (1 << j)) cout << "-" << num[j + 1];
                else
                    cout << "+" << num[j + 1];
            }
            cout << "=7" << endl;
            break;
        }
        if (match) break;
    }

    return 0;
}

Measured memory_bytes: 3564
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

const auto mod = 1000000007L;

typedef long long ll;
ll key(ll x, ll n) {
    ll maxN = 200;
    return x*maxN + n;
}


ll f(ll x, ll n, vector<ll> const &s, std::unordered_map<ll, ll> &dp) {
    auto k = key(x, n);
    auto sn = s[n];
    if (dp.find(k) == dp.end()) {
        dp.emplace(k, n == 0 ? (x%sn) : (((n*f(x, n-1, s, dp))%mod + f(x%sn, n-1, s, dp))%mod));
    }
    return dp[k]%mod;
}

int main() {
    ll N;
    cin >> N;
    ll X;
    cin >> X;
    auto S = vector<ll>(N);
    for(size_t i = 0; i < N; i++){
        cin >> S[i];
    }
    sort(S.begin(), S.end());
    auto dp = std::unordered_map<ll, ll>();
    
    cout << (f(X, N-1, S, dp)%mod);
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n - 1; i++) cin >> c[i];

    long long sum = 0;
    int d = -99;
    for (int i = 0; i < n; i++) {
        sum += b[a[i] - 1];
        if (a[i] - 1 == d + 1) sum += c[d];
        d = a[i] - 1;
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
//cout << fixed << setprecision(20) << *** << endl;
#define rep(i,N) for(int i=0;i<(int)N;++i)
typedef long long ll;
using namespace std;

int main()
{
	ll N,ANS=0;
	bool F=false;
	vector<ll> V;
	vector<vector<ll>>VV;
	cin>>N;
	rep(i,N){
		ll t;
		cin>>t;
		V.push_back(t);
	}

	if(N==1){
		cout<<V[0]<<endl;
		return 0;
	}

	rep(i,101){
		vector<ll>m;
		rep(j,V.size()){
			if(i<V[j])m.push_back(1);
			else m.push_back(0);
		}
		VV.push_back(m);
	}
	rep(i,VV.size()-1){
		rep(j,VV[i].size()-1){
			if(VV[i][j]==1&&j==0)ANS++;
			if(VV[i][j]==0&&VV[i][j+1]==1)ANS++;
		}
	}
	cout<<ANS<<endl;
}

Measured memory_bytes: 3272
a = [input() for i in range(2)]
n = int(a[0])
h = list(map(int, a[1].split()))[::-1]

str = "Yes"
c = 10**9
for i in range(n):
    if h[i] <= c:
        c = h[i]
    else:
        if (h[i]-1) == c:
            h[i] -= 1
        else:
            str = "No"
            break

print(str)


Measured memory_bytes: 15192
#include<stdio.h>

int main()
{
 int a,b;

 scanf("%d%d",&a,&b);

 if(a==1)a=14;
 if(b==1)b=14;

 if(a>b)printf("Alice\n");
 else if(a<b)printf("Bob\n");
 else   printf("Draw\n");

 return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main(){
    double a,b;
    scanf("%lf %lf",&a,&b);
    
    int d,r;
    double f;
    
    d = a/b;
    r = (int)a%(int)b;
    f = a/b;
    
    printf("%d %d %lf\n",d,r,f);
    
    return 0;
}


Measured memory_bytes: 2760
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             x.begin(),x.end() 
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set ; 
const int M = 1e9+7;    
const int N = 5e5;  // limit for array size
int tests() {
  int n,m,k ; 
  int i,s,c ; 
  cin >>  n >> m     ;
  std::vector<int> book(n,10);
  forn(i,0,m){
    cin >> s >> c ; 
    if(book[s-1] == 10 )
      book[s-1] = c ; 
    else if(book[s-1] != c )
        return cout << -1 ,0 ; 
  }
  if(n ==1 && m == 0 )
    return cout << 0 , 0; 
  forn(i,1,n)
    if(book[i] == 10)
      book[i] = 0 ; 
  if(book[0] == 10 )
    book[0] = 1 ;
  if(book[0] == 0 && n > 1 )
    return cout << -1,0 ; 

  forn(i,0,n)
    cout << book[i] ;
  
  return 0; 
}
int main(){
    I__O ;  
    int cases = 1 ;
    // cin >> cases ; 
    while(cases--)
      tests(); 
  return 0 ; 
}

Measured memory_bytes: 256
import std.stdio,std.conv, std.algorithm, std.container,std.array,std.range,std.string,std.typecons,std.numeric,std.math,std.random,std.functional;

void main(){
	int w,h;
	while(read(w,h),w|h){		
		auto land = readMatrix(w,h);
		auto seeked = Matrix!(bool)(w,h);

		void SEEK (Pos p,ref Pos[] seeking,ref char type){
			if(!p.inRange(w,h))return;
			if(seeked[p])return;
			if(land[p] == 'W' || land[p] == 'B') {
				if(type == '.') type = land[p];
				else if(type != land[p]) type = 'X';
				return ;
			}
			seeking ~= p;
			seeked[p] = true;
			foreach(dpos;DPos) SEEK(p + dpos,seeking,type);
		}

		int B ,W;
		foreach(y;iota(h)){
			foreach(x;iota(w)){
				Pos[] seeking;
				char type = '.';
				SEEK(Pos(x,y),seeking,type);
				if(seeking.length == 0) continue;
				if(type == 'B') B += seeking.length;
				if(type == 'W') W += seeking.length;
			}
		}
		writeln(B," ",W);
	}
}


////////////////////////////////////LIB72//////////////////////////
const readMixin = q{ auto line = readln().split();foreach(i,ref arg; args){ if (i >= line.length) return;arg = line[i].to!(typeof(arg));}};
void read(T...)  (auto ref T args){mixin(readMixin);}
void readArray(T)(auto ref T args){mixin(readMixin);}
int  read(){int n;read(n);return n;}
const Dx = [1,0,-1,0], Dy = [0,1,0,-1];
const DPos = [Pos(1,0),Pos(0,1),Pos(-1,0),Pos(0,-1)];
void times(int n,void delegate() stmt){ foreach(i;iota(n))stmt();}

auto dot(R1,R2)(R1 a,R2 b) { 
	ElementType!(R1) res=0;
	for(;!a.empty&&!b.empty;a.popFront(),b.popFront())
		res+=a.front*b.front;
	return res;
}
struct infIota { 
	int i=0;
	enum empty=false;
	int front(){return i;}
	void popFront(){i++;}
}
struct Pos{ 
	int x,y,z;
	bool inRange(int w,int h,int Z=1){
		return x>=0 && y >= 0 && z >=0 && x < w && y < h && z < Z;
	}
	Pos opBinary(string op)(Pos rhs) {
		return Pos ( mixin( "x"~op~"rhs.x" ),
					 mixin( "y"~op~"rhs.y" ),
					 mixin( "z"~op~"rhs.z" ));
	}
	void opOpAssign(string op)(Pos lhs) {
		mixin("x"~op~"=lhs.x;");
		mixin("y"~op~"=lhs.y;");
		mixin("z"~op~"=lhs.z;");
	}
}
struct Matrix(T){
	private T[][] data;
	this(int w,int h){ data = new T[][](w,h);}
	this(ref T[][] data_){ data = data_;}
	T opIndexAssign(T v, size_t x, size_t y){return data[x][y] = v;}
	T opIndexAssign(T v, Pos p){return opIndexAssign(v,p.x,p.y);}
	T opIndex(size_t x, size_t y){return data[x][y];}
	T opIndex(Pos p){return opIndex(p.x,p.y);}
	ref T opCall(Pos p){return data[p.x][p.y];}
	auto W()const{return data.length;}	
	auto H()const{return data[0].length;}	
	void toString(scope void delegate(const(char)[]) sink) const{
		foreach(y;iota(H())) {
			foreach(x;iota(W()))sink(data[x][y].to!string);
			if(y != H()-1)sink("\n");
		}
    }
}
auto readMatrix(int w,int h){ 
	auto M=new char[][](w,h);
	foreach(y;iota(h)) foreach(int x,c;readln().chomp) M[x][y] = c;		
	return Matrix!(char)(M);
}

////////////////////////////////////LIB72//////////////////////////

void rep(int[] ms,void delegate(int,int) f){
	for(int i0;i0<ms[0];i0++) 
		for(int i1;i1<ms[1];i1++) 
			f(i0,i1);
}
//[3,4,5,6].REP!((i,j,k,l)=>{});

Measured memory_bytes: 3732
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUM 55555
char isprime[MAX_NUM];

int main(void){
    memset(isprime,1,MAX_NUM);
    isprime[0] = isprime[1] = 0;
    
    int N;
    scanf("%d",&N);
    int cnt = 0;
    for(int i = 0; i < MAX_NUM; i++){
        if(isprime[i]){
            for(int j = 2; j < MAX_NUM / i; j++){
                isprime[j*i] = 0;
            }
            if(i%10==1){
                cnt++;
                printf("%d ",i);
            }
            if(cnt == N){
                puts("");
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;
map<int, bool> mp;
int a[N], b[N];

signed main()
{
	IO_OP;

	int n;
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	for(int i=0;i<n;i++) b[i] = a[i];
	sort(b, b+n);
	for(int i=0;i<n;i++)
		mp[b[i]] = i & 1;
	int ans = 0;
	for(int i=0;i<n;i+=2) {
		ans += mp[a[i]];
	}
	cout << ans << endl;
	
}





Measured memory_bytes: 5760