akhauriyash/Code-Regression huggingface dataset:
/**
 *    author:  accesss_denied
**/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll mod=1e9+7;			
ll inf=1e18;

int main() {
			fast
			// #ifndef ONLINE_JUDGE
			// freopen("input.txt","r",stdin);
			// freopen("output.txt","w",stdout);
			// #endif

			
				string s;
				cin>>s;
				ll ans=0;

				for(ll i=0;i<s.size();i++)
				ans+=(s[i]-'0');

				if(ans%9==0 )
				cout<<"Yes";
				else
				cout<<"No";
				
                
			
			return 0;
		 }	




Measured memory_bytes: 3780
#include <iostream>

using namespace std;

const int mod =  1e9+7;

int main()
{
    long long n;
    long long s[100001];
    s[1] = 1;
    for(int i = 2; i <= 100000; i++)
        s[i] = (s[i-1]%mod * i%mod) % mod;
    while(cin>>n)
    {
        cout<< s[n] << endl;
    }
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main(){
	int n=0,x=0,count=0;
	while(true){
		scanf("%d %d",&n,&x);
		if(n==0&&x==0) break;
		count=0;
		for(int i=1; i<=n; i++){
			for(int f=i+1; f<=n; f++){
				for(int j=f+1; j<=n; j++){
					if(i+f+j==x) count+=1;
				}
			}
		}
		printf("%d\n",count);
	}
}



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

int main(){
    int N, cake, donut;
    bool can = false;
    cin >> N;
    for(cake = 0; cake < N; cake++){
        for(donut = 0; donut < N; donut++){
            if(cake*4 + donut*7 == N) can = true;
        }
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}

Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder.A
{ 
    public class Program
    {
        public static void Main(string[] args)
        {
            var s = r();
			if (Char.IsUpper(s[0]))
			{
                P("A");
                return;
			}
            P("a");
        }

        private static StreamReader sr;
        public static int[] Ecr()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static string Er()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine();
        }
        public static string r()
        {
            return Console.ReadLine();
        }
        public static  int[] cr()
        {
            return Console.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static int cri()
        {
            return int.Parse(Console.ReadLine());
        }
        public static void P(string str)
        {
            Console.WriteLine(str);
        }
        public static void P(int num)
        {
            P(num.ToString());
        }
    }
}


Measured memory_bytes: 25796
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
string s[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i]>>a[i];
    string k;
    cin>>k;
    bool flag=false;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(flag) ans+=a[i];
        if(s[i]==k) flag=true;
    }
    cout<<ans;
}


Measured memory_bytes: 1024
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    a = [LI() for _ in range(h)]
    b = [LI() for _ in range(h)]
    m = 1 << (80*80*2+3)
    r = [[0]*w for _ in range(h)]
    c = abs(a[0][0] - b[0][0])
    r[0][0] |= (1 << (80*80+1)) << c
    r[0][0] |= (1 << (80*80+1)) >> c
    for i in range(h):
        for j in range(w):
            if i == 0 and j == 0:
                continue
            c = abs(a[i][j] - b[i][j])
            t = 0
            if i > 0:
                t |= (r[i-1][j] << c) % m
                t |= r[i-1][j] >> c
            if j > 0:
                t |= (r[i][j-1] << c) % m
                t |= r[i][j-1] >> c
            r[i][j] = t

    c = r[-1][-1]
    t = 10000
    for i in range((80*80*2+3)):
        if (1<<i) & c > 0:
            k = abs(i-(80*80+1))
            if t > k:
                t = k

    return t


print(main())





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

   typedef long long ll;

   const double EPS = (1e-7);
   const int INF =(1e9);
   const double PI = (acos(-1));
   const int MOD = int(1e9) + 7;

   #define REP(i, n) for(int i = 0; i < (int)(n); i++)
   #define FOR(i, a, b) for (int i = (a); i < (b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((int)(x).size())


   #define dump(x) cerr<< #x << "= " << (x) << endl;

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

   int dx[4]={1,0,-1,0};
   int dy[4]={0,1,0,-1};



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

   //input
   string s; cin >> s;

   int n; n = s.size();
   vector<bool> a(n - 1);

   REP(i, n - 1){
       a[i] = (s[i] == s[i + 1]);
   }
   int ans = n;
   REP(i, n - 1){
       if (a[i] == 0){
           ans = min(ans, max(i + 1, n - 1 - i));
       }
   }
   cout << ans << endl;
   
}

Measured memory_bytes: 512
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto na = readln.split.to!(int[]);
    auto N = na[0];
    auto A = na[1];
    auto xs = readln.split.to!(int[]);

    auto DP = new long[][][](N+1, N+1, N*50+1);
    foreach (c; 1..N+1) {
        foreach (v; 0..N*50+1) {
            DP[N][c][v] = v%c == 0 && v/c == A ? 1 : 0;
        }
    }
    foreach_reverse (i; 0..N) {
        foreach (c; 0..N) {
            foreach (v; 0..N*50+1) {
                DP[i][c][v] = DP[i+1][c][v];
                if (c+1 <= N && v+xs[i] <= N*50) DP[i][c][v] += DP[i+1][c+1][v+xs[i]];
            }
        }
    }
    writeln(DP[0][0][0]);
}

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

using namespace std;

typedef long long ll;

ll MOD = 1000000007;

int main(int, char**) {
	string s, t;
	cin >> s >> t;
	int a, b;
	cin >> a >> b;
	string u;
	cin >> u;
	if (u==s) a--;
	else b--;
	cout << a << " " << b << endl;
	return 0;
}

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

#define N 100010
#define db double
db bit[N];

int main() {
	bit[0] = 1;
	for (int i = 1; i < N; ++i) {
		bit[i] = bit[i - 1] * 1.0 / 2;
	}
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		db res = 0;
		for (int i = 1; i <= n; ++i) {
			int cnt = 0, t = i;
			while (t < k) {
				++cnt;
				t <<= 1;
			}
			res += 1.0 / n * bit[cnt];
		}
		printf("%.16f\n", res);
	}
	return 0;
}


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

int asc(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int main() {
	int K, N, h[100000], i, min = 1000000000, dif;

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

	qsort(h, N, sizeof(int), asc);
	
	for (i = K - 1; i < N; i++) {
		dif = h[i] - h[i - (K - 1)];
		if (dif < min) {
			min = dif;
		}
	}

	printf("%d", min);

	return 0;
}

Measured memory_bytes: 1020
#include <iostream>

using namespace std;

int main(){
	
	long long a,b;
	cin>>a>>b;
	int res =1;
	for(int i=2;i<=1000000;i++){
		if(a%i==0&&b%i==0)res++;
		while(a%i==0)a/=i;
		while(b%i==0)b/=i;
	}
	if(a>1&&a==b)res++;
	cout<<res<<endl;
	
	return 0;
}

Measured memory_bytes: 384
*v,i,s,p,t,D,d[4],O,o[];C(x,o,y){o-43||(x+=y);o-45||(x-=y);o-42||(x*=y);return x;}main(w,x,y,z){for(;~scanf("%d%d%d%d",&w,&x,&y,&z)&&w+x+y+z;puts("0"))for(v=&w,D=256;D--;){for(s=i=0,p=1;i<4;d[i++]=v[t])s+=t=D>>i*2&3,p*=t+1;for(O=27;s==6&&p==24&&O--;printf(C(C(C(*d,*o,d[1]),o[1],d[2]),o[2],d[3])-10?C(C(*d,*o,d[1]),o[1],C(d[2],o[2],d[3]))-10?"":"(%d%c%d)%c(%d%c%d)\n":"((%d%c%d)%c%d)%c%d\n",d[0],o[0],d[1],o[1],d[2],o[2],d[3])&&main())for(t=O,i=3;i--;t/=3)o[i]="+-*"[t%3];}exit(0);}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

int main() {
    int n;
    ll ans=0;
    cin>>n;
    int l=0;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a==0) l=0;
        else if(a==1){
            if(l==1){
                ans++;
                l=0;
            }
            else{
                l=1;
            }
        }
        else{
            if(l==1){
                ans++;
                a--;
                ans+=a/2;
                l=a%2;
            }
            else{
                ans+=a/2;
                l=a%2;
            }
        }
    }
    cout<<ans<<endl;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL K, A, B;
  cin >> K >> A >> B;

  if(K <= A){
	cout << 1 << endl;
  }
  else{
	LL D = A - B;
	if(D <= 0)
	  cout << -1 << endl;
	else{
	  LL num = max(0ll, (K - A) / D - 10);
	  LL x = num * D;
	  num *= 2;
	  for(int i=1;x<K;++i){
		++num;
		if(i%2) x += A;
		else x -= B;
	  }
	  cout << num << endl;
	}
  }

  return 0;
}


Measured memory_bytes: 256
<?php
$o='';
while(1){
  list($a,$b)=explode(' ',trim(fgets(STDIN)));
  if($b<$a){$c=$a;$a=$b;$b=$c;}
  if($a||$b){$o.=sprintf("%d %d\n",$a,$b);}
  else{break;}
}
print $o;

Measured memory_bytes: 15476
import collections
a,b,c,d = input().split()
a=int(a)
b=int(b)
c=int(c)
d=int(d)
abi=int(min(a,b))
abm=int(max(a,b))
cdi=int(min(c,d))
cdm=int(max(c,d))
res1=[]
res2=[]
if abi<0 and abm<0:
  res1=[abi,abm]
elif abi<0 and abm==0:
  res1=[abi,-1,0]
elif abi<0 and abm>0:
  res1=[abi,-1,0,1,abm]
elif abi==0 and abm==0:
  res1=[0]
elif abi==0 and abm>0:
  res1=[0,1,abm]
elif abi>0 and abm>0:
  res1=[abi,abm]

if cdi<0 and cdm<0:
  res2=[cdi,cdm]
elif cdi<0 and cdm==0:
  res2=[cdi,-1,0]
elif cdi<0 and cdm>0:
  res2=[cdi,-1,0,1,cdm]
elif cdi==0 and cdm==0:
  res2=[0]
elif cdi==0 and cdm>0:
  res2=[0,1,cdm]
elif cdi>0 and cdm>0:
  res2=[cdi,cdm]

res=[]
for g in res1:
  for h in res2:
    res.append(g*h)
#print(res)
print(max(res))


Measured memory_bytes: 9480
A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
A3=list(map(int,input().split()))
N=int(input())
b=[0]*N
for i in range(N):
  b[i]=int(input())
C1=any([i == A1[0] for i in b])
C2=any([i == A1[1] for i in b])
C3=any([i == A1[2] for i in b])
C4=any([i == A2[0] for i in b])
C5=any([i == A2[1] for i in b])
C6=any([i == A2[2] for i in b])
C7=any([i == A3[0] for i in b])
C8=any([i == A3[1] for i in b])
C9=any([i == A3[2] for i in b])

if(any([all([C1,C2,C3]),all([C4,C5,C6]),all([C7,C8,C9]),all([C1,C4,C7]),all([C2,C5,C8]),all([C3,C6,C9]),all([C1,C5,C9]),all([C3,C5,C7])])):
   print("Yes")
else:
   print("No")

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

using namespace std;

bool check(int t, int e, int d){
  int tmp = t / d;
  if(abs(d * tmp - t) <= e) return true;
  if(abs(d * (tmp + 1) - t) <= e) return true;
  return false;
}

main(){
  int n, t, e;
  cin >> n >> t >> e;
  int ans = -1;
  for(int i=0;i<n;i++){
    int in;
    cin >> in;
    if(check(t, e, in)){
      ans = i+1;
    }
  }
  cout << ans << endl;
}

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

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

    int dp[100000];

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

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

}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;
using ll = long long;

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

int main() {
  int n;
  cin >> n;
  int x[n];
  rep(i, n) cin >> x[i];

  int ans = 1001001001;
  for (int p = 1; p <= 100; ++p) {
    int now = 0;
    rep(i, n) now += (p - x[i]) * (p - x[i]);
    ans = min(ans, now);
  }

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


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
#include<iomanip>
using namespace std;

#define ll long long
using vt = ll; //ここで数値の型を変えられる
#define rep(i, n) for (vt i = 0; i < (vt)(n); i++)
#define reps(i, s, n) for(vt i = (vt) (s); i < (vt) (n); i++) 
#define MOD 1000000007

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

int main() {
	vt n;
	cin >> n;
	vector<vector<vt>> abc(n , vector<vt>(3));
	rep(i, n) rep(j, 3) cin >> abc.at(i).at(j);
	vector<vector<vt>> dp(n + 1, vector<vt>(3, 0));
	rep(i, n) {
		rep(j, 3) {
			rep(k, 3) {
				if (j == k) continue;
				chmax(dp.at(i + 1).at(k), dp.at(i).at(j) + abc.at(i).at(k));
			}
		}
	}
	vt ans = -1;
	rep(i, 3) chmax(ans, dp.at(n).at(i));
	cout << ans;
	return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>

int main(){
   int i,j,n,sum;
   char s[100000],c;
 
   scanf("%d",&n);
   scanf("%s",s);
   sum=1;c=s[0];
   for (i=1;i<n;i++)
      if (s[i]!=c) {
        sum++;
        c=s[i];
      }
   printf("%d\n",sum);
   return 0;
}

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


vector<int> V(0), W(0);
int b;
vector<vector<int>> dp(0, vector<int>(0, 0));

int solve(int v, int L){
	if(v < b){
		return dp[v][L];
	}
	else if(W[v] <= L){
		return max(solve(v / 2, L), solve(v / 2, L - W[v]) + V[v]);
	}
	else{
		return solve(v / 2, L);
	}
}

signed main(){
	int N, i, j;
	scanf("%lld", &N);
	V.assign(N + 1, 0);
	W.assign(N + 1, 0);
//	vector<int> V(N + 1), W(N + 1);
	for(i = 1; i <= N; i++){
		scanf("%lld%lld", &V[i], &W[i]);
	}
	b = min(N + 1, 1ll << 10);
	int Lmax = 100000;
	dp.assign(b, vector<int>(Lmax + 1, 0));
	for(i = 1; i < b; i++){
		for(j = 0; j <= Lmax; j++){
			dp[i][j] = dp[i / 2][j];
			if(j >= W[i]){
				dp[i][j] = max(dp[i][j], dp[i / 2][j - W[i]] + V[i]);
			}
//			printf("dp[%lld][%lld] = %lld\n", i, j, dp[i][j]);
		}
	}

	int Q;
	scanf("%lld", &Q);
	while(Q--){
		int v, L;
		scanf("%lld%lld", &v, &L);
		printf("%lld\n", solve(v, L));
	}
	return 0;
}

Measured memory_bytes: 811120
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
      	int n = scanner.nextInt();
        String name[] = new String[n];
		for(int t = 0;t<n;t++) {
			name[t] = scanner.next();
            name[t] = String.valueOf(name[t].charAt(0));
        }
        int x = 0;
		Long amnt[] = {0L,0L,0L,0L,0L};
        String moji[] = {"M","A","R","C","H"};
        int s;
        for(x = 0;x < n;x++){
          	for(s = 0;s<5;s++){
         		if(moji[s].equals(name[x])){
                  amnt[s]++;
                }
            }
        }
		Long ans = amnt[0]*(amnt[1]*(amnt[2]+amnt[3]+amnt[4])+amnt[2]*(amnt[3]+amnt[4])+amnt[3]*amnt[4])+amnt[1]*(amnt[2]*amnt[3]+amnt[2]*amnt[4]+amnt[3]*amnt[4])+amnt[2]*amnt[3]*amnt[4];
       System.out.println(ans);
    }
}

Measured memory_bytes: 48056
//#define NDEBUG

#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pdd pair<double, double>
#define pll pair<ll, ll>
#define modadd(a, b) (((a % MOD) + (b % MOD)) % MOD)
#define modtimes(a, b) (((a % MOD) * (b % MOD)) % MOD)

//#define TEST

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1000000007;
const ll MAX = 1LL << 60;


int main(){
    StarBurstStream

    int n;
    cin >> n;
    vector<pii> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].F;
        a[i].S = i + 1;
    }
    lsort(a);
    for(int i = 0; i < n; i++){
        if(i != 0) cout << " ";
        cout << a[i].S;
    }
    cout << "\n";

    return 0;
}

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

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

    char x = S[K - 1];
    for (int i = 0; i < S.size(); i++) {
        if (S[i] != x) {
            S[i] = '*';
        }
    }
    cout << S << endl;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

int W,H;

bool check(int a, int b){
	if(a==0||a==W) return true;
	if(b==0||b==H) return true;
	return false;
}

int foo(int a, int b){
	if(b==0) return a;
	if(a==W) return W+b;
	if(b==H) return W+H+(W-a);
	return W+H+W+(H-b);
}


bool mainmain(){
	cin>>W>>H;
	int n;
	cin>>n;
	vector<pii> v;
	rep(i,n){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(check(a,b)&&check(c,d)){
			int aa = foo(a,b);
			int bb = foo(c,d);
			v.PB(minmax(aa,bb));
		}
	}
	sort(ALL(v));

	stack<pii> st;
	for(pii x: v){
		while(st.size() && st.top().se < x.fi) st.pop();
		if(st.size() && st.top().se < x.se) return false;
		st.push(x);
	}
	return true;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
	cout<<(mainmain()?"YES":"NO")<<endl;
}

Measured memory_bytes: 1524
#include <stdio.h>
#include <math.h>
#define PI 3.141592653589


int main()
{
    double a, b, c, S, L, H;
    
    scanf("%lf %lf %lf", &a, &b, &c);
    S = a * b * sin(c/180.0 * PI) / 2.0;
    L = a + b + sqrt(a*a + b*b - 2.0*a*b*cos(c/180.0 * PI));
    H = 2.0 * S / a;
    printf("%f\n%f\n%f\n", S, L, H);
    return 0;
}



Measured memory_bytes: 2808
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 100000000


int main(){
  int n;
  cin >> n;
  int ans = 0;
  rep(i,n){
    int a;
    cin >> a;
    if(a%2 == 1){
      ans++;
    }
  }
  if(ans%2 == 1) cout << "NO" << endl;
  else cout << "YES" << endl;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	int H[N];
	for (int i = 0; i < N; i++) {
		cin >> H[i];
	}
	bool flg = true;
	int ans = 0;
	while (flg) {
		int a = H[0];
		int cnt = 0;
		for (int i = 1; i < N; i++) {
			if (a == 0 && H[i] != 0) {
				cnt++;
			}
          a=H[i];
		}
        if (H[0] != 0) cnt++;
		for (int i = 0; i < N; i++) {
			if (H[i] != 0) H[i]--;
		}
		if (cnt == 0) flg = false;
		ans += cnt;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
P = list(map(int, input().split()))

pre_ans = 0
ans = 0
for i in range(K):
    ans += (P[i] + 1) / 2
    pre_ans += (P[i] + 1) / 2
#print("first_ans={}".format(ans))

for i in range(N - K):
    pre_ans = pre_ans + (P[K + i] + 1) / 2 - (P[i] + 1) / 2
    ans = max(ans, pre_ans)
    #print("{}-, cand={}, ans={}".format(i+1, pre_ans, ans))
print(ans)

Measured memory_bytes: 71792
var x,y,z,n,m:longint;
    i,t,w:longint;
    father,cost:array[0..1000000]of longint;
    flag:boolean;
function getfather(x:longint):longint;
var t:longint;
begin
  if father[x]=x then exit(x) else
  begin
    t:=getfather(father[x]);
    cost[x]:=cost[x]+cost[father[x]];
    father[x]:=t;
    getfather:=father[x];
  end;
end;
procedure join(x,y,z:longint);
var fx,fy:longint;
begin
  fx:=getfather(x);
  fy:=getfather(y);
  if fx<>fy then
  begin
    father[fx]:=fy;
    cost[fx]:=cost[y]-z-cost[x];
  end else
  if cost[y]-cost[x]<>z then flag:=false;
end;
begin
    flag:=true;
    read(n,m);
    for i:=0 to n do
    begin
      father[i]:=i;
      cost[i]:=0;
    end;
    for i:=1 to m do
    begin
      read(x,y,z);
      join(x,y,z);
    end;
    if flag then writeln('Yes') else writeln('No');
end.


Measured memory_bytes: 4608
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

string multiply(string num1, string num2) 
{ 
    int len1 = num1.size(); 
    int len2 = num2.size(); 
    if (len1 == 0 || len2 == 0) 
    return "0"; 
  
    // will keep the result number in vector 
    // in reverse order 
    vector<int> result(len1 + len2, 0); 
  
    // Below two indexes are used to find positions 
    // in result.  
    int i_n1 = 0;  
    int i_n2 = 0;  
      
    // Go from right to left in num1 
    for (int i=len1-1; i>=0; i--) 
    { 
        int carry = 0; 
        int n1 = num1[i] - '0'; 
  
        // To shift position to left after every 
        // multiplication of a digit in num2 
        i_n2 = 0;  
          
        // Go from right to left in num2              
        for (int j=len2-1; j>=0; j--) 
        { 
            // Take current digit of second number 
            int n2 = num2[j] - '0'; 
  
            // Multiply with current digit of first number 
            // and add result to previously stored result 
            // at current position.  
            int sum = n1*n2 + result[i_n1 + i_n2] + carry; 
  
            // Carry for next iteration 
            carry = sum/10; 
  
            // Store result 
            result[i_n1 + i_n2] = sum % 10; 
  
            i_n2++; 
        } 
  
        // store carry in next cell 
        if (carry > 0) 
            result[i_n1 + i_n2] += carry; 
  
        // To shift position to left after every 
        // multiplication of a digit in num1. 
        i_n1++; 
    } 
  
    // ignore '0's from the right 
    int i = result.size() - 1; 
    while (i>=0 && result[i] == 0) 
    i--; 
  
    // If all were '0's - means either both or 
    // one of num1 or num2 were '0' 
    if (i == -1) 
    return "0"; 
  
    // generate the result string 
    string s = ""; 
      
    while (i >= 0) 
        s += std::to_string(result[i--]); 
  
    return s; 
} 

signed main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n;
    cin>>n;
    int a[n];
    string ans="1";
    long double x=0;
    bool flag=true;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==0)
        {
            cout<<0;
            return 0;
        }
        if(flag)
            ans=multiply(ans,to_string(a[i]));
        if(ans.length()>19)
        {
            flag=false;
        }
    }

    if(ans.length()>19)
    {
        cout<<-1;
        return 0;
    }
    else if(ans.length()==19)
    {
        int nn=1e18;
        string str=to_string(nn);
        if(ans>str)
        {
            cout<<-1;
            return 0;
        }
    }
    int y=1;
    for(int i=0;i<n;i++)
    {
        y*=a[i];
    }
    cout<<y;

  
} 



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

int main(){
    //入力
    int W,H,N;
    cin >> W >> H >> N;

    //処理
    int x_min,x_max,y_min,y_max,x,y,a,ans;
    x_min = 0;
    x_max = W;
    y_min = 0;
    y_max = H;

    for(int i=0;i<N;i++){
        cin >> x >> y >> a;
        if(a==1){
            x_min=max(x,x_min);
        }else if(a==2){
            x_max=min(x,x_max);
        }else if(a==3){
            y_min=max(y,y_min);
        }else if(a==4){
            y_max=min(y,y_max);
        }
    }
    
    //出力
    if(y_min>y_max||x_min>x_max){
        ans=0;
    }else{
        ans=(y_max-y_min)*(x_max-x_min);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i=0; i<n; i++)
#define forsn(i, s, n) for(int i=s; i<n; i++)
int n;
vector<pair<pair<int, int>, int > > accx;
vector<pair< pair<int, int>, int > > accy;
vector< pair< int,  pair<int, int> > > edgeset;
//vector< vector<pair<int, int> > > graph;
vector<int> par;
vector<int> size;
long long int weight=0;
int find(int x){
	if(par[x]==-1) return x;
	return par[x]=find(par[x]);
}
void join(int a, int b, int w){
	int para, parb;
	para=find(a); parb=find(b);
	if(para==parb) return;
	if(size[para]<size[parb]) swap(para, parb);
	size[para]+=size[parb];
	par[parb]=para;
	weight+=w;
}
int main(){
	cin>>n;
	forn(i, n){
		int x, y;
		cin>>x>>y;
		accx.push_back(make_pair(make_pair(x, y), i));
		accy.push_back(make_pair(make_pair(y, x), i));
	}
	par.assign(n, -1);
	size.assign(n, 1);
	sort(accx.begin(), accx.end());
	forn(i, n-1){
		edgeset.push_back(make_pair( abs(accx[i].first.first-accx[i+1].first.first) , make_pair(accx[i].second, accx[i+1].second)));
		//graph[accx[i].second].push_back(make_pair(accx[i+1].second, ));
		//graph[accx[i+1].second].push_back(make_pair(accx[i].second, abs(accx[i].first.first-accx[i+1].first.first)));
	}
	sort(accy.begin(), accy.end());
	forn(i, n-1){
		//graph[accx[i].second].push_back(make_pair(accx[i+1].second, abs(accx[i].first.second-accx[i+1].first.second)));
		//graph[accx[i+1].second].push_back(make_pair(accx[i].second, abs(accx[i].first.second-accx[i+1].first.second)));
		edgeset.push_back(make_pair( abs(accy[i].first.first-accy[i+1].first.first) , make_pair(accy[i].second, accy[i+1].second)));
	}
	sort(edgeset.begin(), edgeset.end()) ;
	int len=edgeset.size();
	forn(i, len){
		join(edgeset[i].second.first, edgeset[i].second.second, edgeset[i].first);
	}
	cout<<weight<<endl;		
}

Measured memory_bytes: 7980
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

int main(){
  int N,K;
  cin >> N >> K;

  //Kが奇数->abc全部Kの倍数
  if(K%2!=0){
    ll X;
    X=N/K;
    cout << X*X*X << endl;
    return 0;
  }
  //Kが偶数->abc全部Kの倍数またはKの倍数プラスk/2
  else{
    ll X;
    ll Y;
    X=N/K;
    Y=(N+K/2)/K;
    cout << X*X*X+Y*Y*Y << endl;
    return 0;
  }
}


Measured memory_bytes: 384
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
const int fa=401;
const int ma=99999999;
using namespace std;
int n,m;
int mp[fa][fa];
int cost[fa][fa];
struct wgh
{
    int x,y;
}a[10001];
int d[fa],nu;
int path[fa],b[100001];
int ans;bool v[fa];
int x,y,z,w,s,t;
bool spfa()
{
    int i,j,l,r;
    memset(path,0,sizeof(path));
    memset(v,false,sizeof(v));
    for(i=1;i<=n;i++)d[i]=ma;
    l=0;r=1;
    d[s]=0;b[r]=s;v[s]=true;
    while(l<r)
    {
        l++;i=b[l];
        v[i]=false;
        for(j=1;j<=n;j++)
        if(mp[i][j]>0&&d[j]>d[i]+cost[i][j])
        {
            if(!v[j])
            {
                b[++r]=j;
                v[j]=true;
            }
            d[j]=d[i]+cost[i][j];
            path[j]=i;
        }
    }
    if(d[t]==ma)return false;
    return true;
}
int minflow()
{
    int mincost=0,maxflow=0,minf=0;
    if(s==t)return 0;
    while(spfa())
    {
        int now=t,neck=ma;
        while(now!=s)
        {
            int pre=path[now];
            if(neck>mp[pre][now])
            neck=mp[pre][now];
            now=pre;
        }
        maxflow+=neck;
        now=t;
        while(now!=s)
        {
            int pre=path[now];
            mp[pre][now]-=neck;
            mp[now][pre]+=neck;
            cost[now][pre]=-cost[pre][now];
            mincost+=cost[pre][now]*neck;
            //minf+=neck;
            now=pre;
        }
    }
    printf("%d\n",maxflow);
    return mincost;

}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            mp[i][j]=0;
            cost[i][j]=ma;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            mp[x][y]=1;
            cost[x][y]=0;
            mp[y][x]=1;
            cost[y][x]=1;
            nu++;
            a[nu].x=x;a[nu].y=y;
        }
        scanf("%d %d",&s,&t);
        ans=minflow();
        printf("%d\n",ans);
        for(i=1;i<=m;i++)
        {
            if(mp[a[i].y][a[i].x]==0)
            printf("%d\n",i);
        }
    }
    return 0;
}

Measured memory_bytes: 0
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

if N <= 2:
    print(1)
    exit()

dp = [1,1]
last_idx = [-1]*(N+10)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Measured memory_bytes: 20480
H, N = map(int, input().split())
dp = [10 ** 100] * H
for _ in range(N):
    A, B = map(int, input().split())
    for i in range(H - 1, -1, -1):
        if A + i >= H:
            dp[i] = min(dp[i], B)
        else:
            dp[i] = min(dp[i], dp[A + i] + B)
print(dp[0])


Measured memory_bytes: 50140
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int main(void) {
  int n, m;
  cin >> n >> m;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int b[m];
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  int a_s[n];
  memcpy(a_s, a, sizeof a);
  sort(a_s, a_s + n);
  int b_s[m];
  memcpy(b_s, b, sizeof b);
  sort(b_s, b_s + m);
  int a_p = n - 1, b_p = m - 1;
  int a_l = 0, b_l = 0;
  int ll;
  long res = 1;
  for (int i = n * m; i > 0; i--) {
    if (n >= 2 && a_s[a_p] == i && a_s[a_p - 1] == i) {
      cout << 0 << endl;
      return 0;
    }
    if (m >= 2 && b_s[b_p] == i && b_s[b_p - 1] == i) {
      cout << 0 << endl;
      return 0;
    }
    if (a_s[a_p] == i && b_s[b_p] == i) {
      a_l++;
      b_l++;
      a_p--;
      b_p--;
    } else if (a_s[a_p] == i && b_s[b_p] != i) {
      res *= b_l;
      res %= 1000000007;
      a_l++;
      a_p--;
    } else if (a_s[a_p] != i && b_s[b_p] == i) {
      res *= a_l;
      res %= 1000000007;
      b_l++;
      b_p--;
    } else {
      ll = a_l * b_l;
      if (ll - (n*m-i) <= 0) {
        cout << 0 << endl;
        return 0;
      } else {
        res *= ll - (n*m-i);
        res %= 1000000007;
      }
    }
  }
  cout << res << endl;
  return 0;
}
        


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

const ll infll=9223372036854775806;
const int inf=2147483646;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(20);
	ll i,j,k,n,m,a[100000],t,ans=0,b1,c1;
	cin>>n>>m;
	vector<pair<int,int>> b;
	for (i=0;i<n;i++){
		cin>>a[i];
	}
	for (i=0;i<m;i++){
		cin>>b1>>c1;
		b.push_back(make_pair(c1,b1));
	}
	sort(a,a+n);
	sort(b.begin(),b.end());
	t=m-1;
	for (i=0;i<n;i++){
		if (t>=0&&b[t].second==0){
			t--;
		}
		if (t>=0&&b[t].first>a[i]){
			ans+=b[t].first;
			b[t].second--;
		}
		else {
			ans+=a[i];
		}
	}
	cout<<ans;
	return 0;
}

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

const int Maxn = 18;
const int MaxN = 1 << Maxn;

int n;
int best[MaxN][2];

void Insert(int best[], int val)
{
	if (val > best[0]) best[1] = best[0], best[0] = val;
	else if (val > best[1]) best[1] = val;
}

int Check(int mask) { return mask == 0? 0: best[mask][0] + best[mask][1]; }

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 1 << n; i++)
		scanf("%d", &best[i][0]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 1 << n; j++) if (!(j & 1 << i)) {
			int nj = (j | 1 << i);
			Insert(best[nj], best[j][0]);
			Insert(best[nj], best[j][1]);
		}
	for (int i = 1; i < 1 << n; i++) {
		int res = Check(i);
		for (int j = 0; j < n; j++) if (i & 1 << j)
			res = max(res, Check((i ^ 1 << j) | ((1 << j) - 1)));
		printf("%d\n", res);
	}
	return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int count = 0;
    for (int i = a; i <= b; i++) {
        if (c % i == 0) {
            count += 1;
        }
    }

    cout << count << endl;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)     for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = m; i < (int)(n); i++)
#define Graph vector<vector<int>>
#define MOD 1000000007 
typedef pair<int, int> PII;
typedef long long ll;

int main(){
  ll N;
  cin >> N;

  ll j = 1;
  ll MAX_j = j;

  while(N >= j * j){
    if((N % j) == 0){
      MAX_j = j;
    }
    j++;
  }

  ll tmp = max(MAX_j, (N / MAX_j));
  int digits = 1;
  while(tmp > 9){
    tmp /= 10;
    digits++;
  }

  cout << digits << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define INF 0x3f3f3f3f
#include<ext/rope>
using namespace __gnu_cxx;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<double,double> pdd;
ll a,b;
int main()
{
    while(cin>>a)
      cout<<a*a*a<<'\n';
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	string d;
	cin >> d;
	if (d == "SAT") {
		cout << 1 << endl;
	}
	else if (d == "FRI") {
		cout << 2 << endl;
	}
	else if (d == "THU") {
		cout << 3 << endl;
	}
	else if (d == "WED") {
		cout << 4 << endl;
	}
	else if (d == "TUE") {
		cout << 5 << endl;
	}
	else if (d == "MON") {
		cout << 6 << endl;
	}
	else if (d == "SUN") {
		cout << 7 << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int a, b;
    cin >> a >> b;

    cout << ((a < 10 && b < 10) ? a * b : -1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<ll> v(N);
    map<ll, int> m;
    for(int i=0; i<N; ++i) {
        cin >> v[i];
        m[v[i]]++;
    }
    sort(v.begin(), v.end());
    double ave = 0;
    set<ll> s;
    vector<vector<ll>> cmb(51, vector<ll>(51));
    cmb[0][0] = 1;
    for(int i=1; i<=50; ++i) {
        for(int j=0; j<=i; ++j) {
            cmb[i][j] = cmb[i-1][j] + (j-1 >= 0 ? cmb[i-1][j-1] : 0);
        }
    }
    map<ll, int> cnt;
    for(int i=0; i<A; ++i) {
        ave += v[v.size()-1-i];
        s.insert(v[v.size()-1-i]);
        cnt[v[v.size()-1-i]]++;
    }
    ave /= A;
    ll res = 0;
    if(s.size() == 1) {
        for(int i=A; i<=B; ++i) {
            res += cmb[m[v[v.size()-1]]][i];
        }
    } else {
        ll mi = v[v.size()-A];
        res = cmb[m[mi]][cnt[mi]];
    }
    cout << fixed << setprecision(8) << ave << endl;
    cout << res << endl;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
AB = []

for i in range(N):
  tmp = list(map(int,input().split()))
  AB.append(tmp)

AB_2 = sorted(AB,key = lambda x: x[0])

nokori = M
price = 0

for j in AB_2:
  if nokori <= j[1]:
    price += j[0] * nokori
    break
  else:
    price += j[0] * j[1]
    nokori -= j[1]
  
print(price)

Measured memory_bytes: 29788
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void print(int a[],int n){
    bool isFirst = true; 

    for(int i=0;i<n;i++){
        if(isFirst){
            cout<<a[i];
            isFirst=false;
        }else{
            cout<<" "<<a[i];
        }
    }
    cout<<"\n";
}

double insertionSort(int A[],int N){
    int i,j,k;
    int tmp;
    for (i=1;i<N; i++){
        tmp=A[i];
        j=i-1;
        while (j>=0 and A[j]>tmp)
        {
            A[j+1]=A[j];
            j--;
            A[j+1] = tmp;
        }
        print(A,N);
    }
    return 0;

}

int main()
{
    int n;
    std::cin >> n;
    int a[n];

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

    print(a,n);
    insertionSort(a,n);

    return 0;

}





Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

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

  int ans = 0;
  REP(i, 0, 3) {
    // if ( strcmp(*S[i], *T[i]) )
    if ( S[i] == T[i] )
      ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int m = Integer.parseInt(in.next());

            int s[] = new int[m];
            int c[] = new int[m];
            for (int i = 0; i < m; i++) {
                s[i] = Integer.parseInt(in.next());
                c[i] = Integer.parseInt(in.next());
            }

            int lp = 0;
            int el = 0;
            if (n == 1) {
                lp = 0;
                el = 9;
            }
            if (n == 2) {
                lp = 10;
                el = 99;
            }
            if (n == 3) {
                lp = 100;
                el = 999;
            }
            int flg = 0;
            for (int i = lp; i <= el; i++) {
                String t = Integer.toString(i);
                flg = 0;
                for (int j = 0; j < m; j++) {
                    if (String.valueOf(t.charAt(s[j] - 1)).equals(String.valueOf(c[j]))) {
                        ++flg;
                    }
                }
                if (flg == m) {
                    out.println(t);
                    return;
                }
            }
            out.println(-1);
        }

    }
}



Measured memory_bytes: 21972
package main

import (
  "fmt"
)

func main() {
  var x, y int
  fmt.Scanf("%d %d", &x, &y)
  
  ans := 0
  switch (x){
    case 1:
    	ans += 300000
    case 2:
    	ans += 200000
    case 3:
    	ans += 100000
  }
  switch (y){
    case 1:
    	ans += 300000
    case 2:
    	ans += 200000
    case 3:
    	ans += 100000
  }
  if x+y == 2 {
    ans += 400000
  }
  fmt.Printf("%d\n", ans)
}

Measured memory_bytes: 1832
import std.stdio;
import std.conv;
import std.algorithm;
import std.range;
import std.string;
import std.typecons;
import std.math;
import std.random;
import std.range;
import std.functional;
sizediff_t minIndex(alias pred = "a < b", Range)(Range range)
if (isForwardRange!Range && !isInfinite!Range &&
    is(typeof(binaryFun!pred(range.front, range.front))))
{
    if (range.empty) return -1;

    sizediff_t minPos = 0;

    static if (isRandomAccessRange!Range && hasLength!Range)
    {
        foreach (i; 1 .. range.length)
        {
            if (binaryFun!pred(range[i], range[minPos]))
            {
                minPos = i;
            }
        }
    }
    else
    {
        sizediff_t curPos = 0;
        Unqual!(typeof(range.front)) min = range.front;
        for (range.popFront(); !range.empty; range.popFront())
        {
            ++curPos;
            if (binaryFun!pred(range.front, min))
            {
                min = range.front;
                minPos = curPos;
            }
        }
    }
    return minPos;
}


void selsort(T)(T a, out int sw)
{
    sw = 0;
    for (size_t i = 0; i < a.length; i++)
    {
        auto min = a[i..$].minIndex + i;
        if (a[i] > a[min])
        {
            swap(a[i], a[min]);
            sw++;
        }
    }
}
void main()
{
    readln;
    auto a = readln().strip.split(" ").map!(to!int).array;
    int sw;
    a.selsort(sw);
    writeln(a.map!(to!string).join(" "));
    writeln(sw);
}


Measured memory_bytes: 2504
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define all(a) begin(a),end(a)
#define sz(a) (int)(a.size())
#define deb(a) cout << #a << ": " << a << ENDL;
#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;


int main()
{   _
    lli n; cin >> n;
    set<ii> st;
    lli cnt = 1;
    lli cur = 7;
    if(7 % n == 0) {
        cout << 1 << ENDL;
        return 0;
    }
    lli nxt = (11 % n);
    while(true) {
        ++cnt;
        cur = (7LL * nxt) % n;
        if(cur == 0) {
            cout << cnt << ENDL;
            return 0;
        }
        nxt = (nxt * 10LL) % n;
        nxt = (nxt + 1LL) % n;
        ii p = {nxt, cur};
        if(st.count(p)) {
            cout << -1 << ENDL;
            return 0;
        }
        st.insert(p);
    }
    return 0;
}


Measured memory_bytes: 66140
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.0000001
using namespace std;

int calc(int x,int y){
	if(y == 0){
		return x;
	}else{
		return calc(y,x%y);
	}
}

int main(){

	int x,y;
	scanf("%d %d",&x,&y);

	int ans = (x-1)+(y-1)+2;

	int common;
	if(x >= y){
		common= calc(x,y);
	}else{
		common = calc(y,x);
	}

	int bunshi = x/common;
	int bunbo = y/common;

	int tyouhuku = 0;
	int value = 0;

	for(int i = 0; i < y-1; i++){
		value += bunshi;
		if(value%bunbo == 0)tyouhuku++;
	}

	ans -= tyouhuku;

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

	return 0;
}

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

int main(void)
{
    int sum, n, mmin, mmax, a;
    while(1) {
        sum = 0; mmax = -1; mmin = 114514810;
        cin >> n;
        if(n == 0) break;
        
        for(int i=0; i<n; i++) {
            cin >> a;
            sum += a;
            mmax = max(mmax, a);
            mmin = min(mmin, a);
        }
        sum = sum - mmax - mmin;
        cout << sum / (n-2) << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1160
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i+1)] = i
  #print(c)
print(len(c))

Measured memory_bytes: 56792