akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

ll modinv(ll a, ll m)
{
  ll b = m, x = 1, y = 0;
  while (b > 0)
  {
    ll q = a / b, r = a - q * b, s = x - q * y;
    a = b, b = r;
    x = y, y = s;
  }
  return mod(x, m);
}

int main()
{
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (ll i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }

  vector<ll> S(N + 1);
  S.at(0) = 0, S.at(1) = 0;
  for (ll i = 2; i <= N; i++)
  {
    S.at(i) = (S.at(i - 1) + modinv(i, MOD)) % MOD;
  }

  ll ans = 0;
  for (ll i = 0; i < N; i++)
  {
    ll tmp = A.at(i) * (S.at(i + 1) + 1 + S.at(N - i));
    ans += tmp;
    ans %= MOD;
  }
  for (ll i = 1; i <= N; i++)
  {
    ans *= i;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

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

    if(a == 'A'){
        cout << 'T' << endl;
    }else if(a == 'T'){
        cout << 'A' << endl;
    }else if(a == 'C'){
        cout << 'G' << endl;
    }else{
        cout << 'C' << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N=int(input())
import numpy as np
h= np.array(list(map(int,input().split())))
h=np.append(h,[0])
m=np.max(h)
count=0
if N==1:
    print(m)
else:
    for i in range(m):
        for j in range(N):
            if h[j]>0 and h[j+1]<=0:
                count+=1
        h=h-1
    print(count)


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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

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

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int n, m;
	cin >> n >> m;
	vi a(n);
	rep(i, n) cin >> a[i];

	int sum = 0;
	rep(i, n) sum += a[i];
	int ans = 0;
	rep(i, n){
		if(sum <= 4 * m * a[i]){
			ans++;
			cerr << a[i] << endl;
		}
	}
	cerr << ans << endl;

	cout << (ans >= m ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll              int
#define pb              push_back
#define ppb             pop_back
#define endl            '\n'
#define mii             map<ll,ll>
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define vs              vector<string>
#define all(a)          (a).begin(),(a).end()
#define F               first
#define S               second
#define sz(x)           (ll)x.size()
#define hell            1000000007
#define inf             (ll)1e18 + 5
#define PI              ((double)3.14159265358979323844)
#define DECIMAL(n)      cout << fixed << setprecision(n);
#define rep(i,a,b)      for (ll i=a;i<b;i++)
#define repr(i,a,b)     for (ll i=a-1;i>=b;i--)
#define lbnd            lower_bound
#define ubnd            upper_bound
#define mp              make_pair
#define ios             ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ordered_set     tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define trace(...)      __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

using namespace std;
using namespace __gnu_pbds;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//primes for hashing 937,991,1013,1409,1741

ll n;
ll can[25][25];
ll dp[25][1<<22];

ll calc(ll x,ll mask){
	if (mask==0)return 1;
	if (dp[x][mask]!=-1)return dp[x][mask];
	dp[x][mask]=0;
	rep(i,0,n){
		if ((mask & (1<<i)) && can[x-1][i]){
			dp[x][mask]=(dp[x][mask]%hell+calc(x-1,(mask & ~(1<<i)))%hell)%hell;
		}
	}
	return dp[x][mask];
}

void solve() {
    cin>>n;
    rep(i,0,n){
    	rep(j,0,n)cin>>can[i][j];
    }
    memset(dp,-1,sizeof dp);
    cout<<calc(n,(1<<n)-1)<<endl;
}

signed main() {
    ios
    ll test=1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  bool ok = false;
  while (N) {
    ok |= N%10 == 7;
    N /= 10;
  }

  cout << (ok?"Yes":"No") << endl;

  return 0;
}

Measured memory_bytes: 3624
#include <set>
#include <string>
#include <iostream>

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::set<std::string> dic;
    int n;
    std::cin >> n;
    for(int i = 0; i < n; ++i){
        std::string command, str;
        std::cin >> command >> str;
        if(command[0] == 'i'){
            dic.insert(str);
        }else
        if(command[0] == 'f'){
            std::cout << (dic.find(str) != dic.end() ? "yes" : "no") << std::endl;
        }
    }
    return 0;
 }

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

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

	//x1==0 x1<=x2<=x3 

	//s==a*b-k*(b-l) となるa,b,k,lを見つければよい　出力は0,b,k,0,a,l
	//どうやってみつけるの
	//sにわずかに大きいa*bを設定する→a*b-sについてx*yの形で因数分解、k,b-lにする。x*yは素数でも成立する
	long long a, b, k, l;
	a = ceil(sqrt(s));
	b = ceil(sqrt(s));
	long long xy = (a * b) - s;
	l = b - 1;
	k = xy;
	cout << 0 <<" "<< b <<" "<< k <<" "<< 0 << " " << a << " " << l;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n; cin >> n;
  vector<vector<int>> num(10, vector<int>(10, 0));

  for(int i = 1; i <= n; ++i) {
    if(i%10 == 0) continue;
    string s = to_string(i);
    ++num[s.front()-'0'][s.back()-'0'];
  }
  int ans = 0;
  for(int i = 1; i <= 9; ++i) {
    for(int j = 1; j <= 9; ++j) {
      ans += num[i][j] * num[j][i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include<bitset>
#include<stdio.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int INF = 100000000;

bool isOK(int a[],int index,int key){
    if(a[index] >= key){
        return true;
    }else{
        return false;
    }
}

int binary_search(int a[],int n,int key){
    int left = -1;
    int right = n;

    while(right-left>1){
        int mid = left + (right - left)/2;
        if(isOK(a,mid,key)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}

int factrial(int n){
    if(n==0){
        return 1;
    }else{
        return n*factrial(n-1);
    }
}

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

    int top = 0;
    rep(i,3){
        if(s[i]=='o'){
            top++;
        }
    }

    cout << 700 + top*100 << endl;
    return 0;
}



Measured memory_bytes: 256
// AUTHOR : Kishan Srivastav
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main() {
	ios
#ifndef ONLINE_JUDGE
	in;
	out;
#endif
	ll n;
	cin>>n;
	string t="";
	while(n>0){
		n--;
		t += 'a'+ (n%26);
		n /= 26;
	}
	reverse(t.begin(),t.end());
	cout<<t<<endl;
}

Measured memory_bytes: 3644
/*
      author : nishi5451
      created: 11.08.2020 20:43:24
*/

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


int main(){
    ll n;
    cin >> n;
    if(n%2==0) cout << n << endl;
    else cout << 2*n << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>

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


	return 0;
}

Measured memory_bytes: 584
//fLIP

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int n,m,k;cin>>n>>m>>k;
    rep(i,0,n+1){
        rep(j,0,m+1){
            if(k==i*m+j*n-i*j*2){
                cout<<"Yes"<<nnn;
                return 0;
            }
        }
    }
    cout<<"No"<<nnn;
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<P,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define print(v) cout<<v<<endl;
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;

int main(){
    ll N;
    cin >> N;
    vector<vector<ll>> dp(2, vector<ll>(N, 0));
    vector<vector<ll>> A(2, vector<ll>(N, 0));
    for(ll i=0;i<2;i++)
        for(ll j=0;j<N;j++)cin>>A[i][j];
    for(ll i=0;i<2;i++)
        for(ll j=0;j<N;j++){
            ll rec=0;
            if(i>0)chmax(rec,dp[i-1][j]);
            if(j>0)chmax(rec,dp[i][j-1]);
            rec+=A[i][j];
            dp[i][j]=rec;
        }
    print(dp[1][N-1])

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

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

    vector <int> ans(N+1);

    for (int a = 1; a <= 100; ++a) {
        int a2 = a*a;

        if (a2 > N) {
            continue;
        }

        for (int b = 1; b <= 100; ++b) {
            int b2a = a2 + b*b;
            if (b2a > N) {
                continue;
            }

            for (int c = 1; c <= 100; ++c) {
                int sum = b2a + c*c + a*b + a*c + b*c;

                if (sum <= N) {
                    ++ans[sum];
                }
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << endl;
    }

    return 0;
}

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

using namespace std;

using ll = long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
constexpr ll mo2 = 998244353;


ll mypow(ll a,ll n){
    ll ret = 1ll;
    while(n > 0){
        if(n&1)ret *= a;
        a *= a;
        n>>= 1;
    }
    return ret;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll x;
    cin>>x;
    int i;
    long double left = 1.01*100;
    for(i=1;i<=4000;++i){
        if(left >= x) break;
        left *= 1.01;
        left = floor(left);
    }
    cout << i << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
using namespace std;

void swap(int& x,int& y){
    int tmp;
    tmp=x;
    x=y;
    y=tmp;
}

int main(){
    int a,b;
    for(int i=1;i<=3000;i++){
        scanf("%d %d",&a,&b);
        if(a==0&&b==0)break;
        if(a>b)swap(a,b);
        printf("%d %d\n",a,b);
    }
}


Measured memory_bytes: 2568
package main

import (
	"fmt"
	"math"
	"strconv"
)

func main() {
	// Code for B - 1 21
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	var S float64
	A := strconv.Itoa(a)
	B := strconv.Itoa(b)
	C, _ := strconv.Atoi(A + B)
	S = math.Sqrt(float64(C))

	if math.Round(S) == S {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1836
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
int main(void)
{
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> a(N), A(Q);
    rep(i, Q)
    {
        cin >> A[i];
    }
    rep(i, N)
    {
        a[i] = K;
    }
    rep(i, Q)
    {
        a[A[i] - 1] += 1;
    }
    rep(i, N)
    {
        a[i] -= Q;
    }
    rep(i, N)
    {
        if (a[i] <= 0)
        {
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
        
    }
}


Measured memory_bytes: 1408
#include<stdio.h>

int main(void)
{
	int i,j,h,w;
	scanf("%d %d",&h,&w);
	while((h != 0) || (w != 0)){
		for(i=0;i<h;i++){
			if((i == 0) || (i == h-1)){
				for(j=0;j<w;j++){
					printf("#");
				}
				printf("\n");
			}else{
				for(j=0;j<w;j++){
					if((j == 0) || (j == w-1)){
						printf("#");
					} else{
						printf(".");
					}
				}
				printf("\n");
			}
		}
		printf("\n");
		scanf("%d %d",&h,&w);
	}
		
	return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;


int main(){
  int n;
  cin>>n;
  int a[105];
  for(int i=1;i<=n;i++)cin>>a[i-1]>>a[i];

  int dp[105][105]={};
  for(int i=0;i<105;i++)
    for(int j=0;j<105;j++)dp[i][j]=INF*(i!=j);

  for(int l=0;l<n;l++){
    for(int i=0;i<n-l;i++){
      int j=i+l;
      for(int k=i;k<j;k++){
	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
      }
    }
  }

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

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

using namespace std;
  int a[200010];
  int ans[200010];
int main(){
  int n;
  cin>>n;
  for(int i=2;i<=n;i++) cin>>a[i];
  for(int i=2;i<=n;i++) ans[a[i]]++;
  for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
}

Measured memory_bytes: 5108
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<string>
using namespace std;

int main() {

	int n;

	cin >> n;
	int max = n;
	printf("%d:", n);

	int i = 2;

	while (n != 1) {
		if (n % i == 0) {
			printf(" %d", i);
			n /= i;
		}
		else break;
	}
	i = 3;
	while (n != 1 && i * i <= max) {
		if (n % i == 0) {
			printf(" %d", i);
			n /= i;
		}
		else i += 2;
	}
	if (n != 1)printf(" %d",n);


	printf("\n");


	//system("pause");
	return 0;
}


Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define PI 3.14159265359
using namespace std;

int main() {
	string s;
	int maxlen = 0;
	string maxstr = "";
	vector<pair<int, string> > v(1000, pair<int, string>(0, "-"));

	while (cin >> s) {
		if (s.size() > maxlen) {
			maxlen = s.size();
			maxstr = s;
		}

		for (int i = 0; i < v.size(); i++) {
			string &s2 = v.at(i).second;
			int &cnt = v.at(i).first;

			if (s2 == "-") {
				s2 = s;
				cnt = 1;
				break;
			}
			else {
				if (s2 == s) {
					cnt++;
					break;
				}
			}
		}
	}
	/*
	for (int i = 0; i < 10; i++) {
		int x = v.at(i).first;
		string s0 = v.at(i).second;

		cout << x << ' ' << s0 << endl;
	}*/

	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	cout << v.at(0).second << ' ' << maxstr << endl;
}


Measured memory_bytes: 3148
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/aoj0030/input.txt"));
			System.setOut(new PrintStream(new FileOutputStream("src/xxxyyyy/result.txt")));
		} catch (FileNotFoundException e) {
		}
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int s = sc.nextInt();
			if (n == 0 && s == 0)
				break;
			System.out.println(solve(n, s));
		}
	}


	int solve(int N, int sum) {
		if (sum > 45)
			return 0;
	int [][][]dp = new int[N + 1][11][sum + 1];
		dp[0][0][0] = 1;
		for (int n = 0; n < N; n++) {
			for (int min = 0; min <= 9; min++)
				for (int s = 0; s <= sum; s++) {
					for(int add = min; add <= 9; add++) {
						if( s + add <= sum)
							dp[n + 1][add + 1][s + add] += dp[n][min][s];
					}
				}
			
		}
		int res = 0;
		for(int i = 0; i < 11; i++)
			res += dp[N][i][sum];
		return res;
	}

	void debug(Object... os) {
		System.err.println(deepToString(os));
	}
}

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

int detectYYorMM(int readVal){
    if(0 == readVal){
        return 0;
    }else if(1 <= readVal && readVal <= 12){
        return 1;
    }else{
        return 2;
    }
}

int main(){
    std::string s;
    std::cin >> s;

    int former = detectYYorMM(std::stoi(s.substr(0,2)));
    int latter = detectYYorMM(std::stoi(s.substr(2,2)));

    std::string ans;
    switch(10 * former + latter){
        case 0:
            ans = "NA";
            break;
        case 1:
            ans = "YYMM";
            break;
        case 2:
            ans = "NA";
            break;
        case 10:
            ans = "MMYY";
            break;
        case 11:
            ans = "AMBIGUOUS";
            break;
        case 12:
            ans = "MMYY";
            break;
        case 20:
            ans = "NA";
            break;
        case 21:
            ans = "YYMM";
            break;
        case 22:
            ans = "NA";
            break;
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
char p[2010][2010];
int n, m, Q, S[2010][2010][3];
int Calc(int x1, int y1, int x2, int y2, int ck){
    return S[x2][y2][ck] - S[x1][y2][ck] - S[x2][y1][ck] + S[x1][y1][ck];
}
int main(){
    int i, j, k, x1, x2, y1, y2;
    scanf("%d%d%d",&n,&m,&Q);
    for(i=1;i<=n;i++){
        scanf("%s",p[i]+1);
        for(j=1;j<=m;j++)S[i][j][0] = p[i][j]-'0';
        for(j=1;j<m;j++)S[i][j][1] = (p[i][j+1]-'0')*(p[i][j]-'0');
        if(i!=1)for(j=1;j<=m;j++)S[i-1][j][2] = (p[i][j]-'0')*(p[i-1][j]-'0');
    }
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<3;k++)S[i][j][k]+=S[i-1][j][k]+S[i][j-1][k]-S[i-1][j-1][k];
    while(Q--){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",Calc(x1-1,y1-1,x2,y2,0) - Calc(x1-1,y1-1,x2,y2-1,1) - Calc(x1-1,y1-1,x2-1,y2,2));
    }
}

Measured memory_bytes: 52992
# -*- coding: utf-8 -*-
# はじめてのぱいそん！
# Aの和 + not(A)の和 = ΣAと対称性から、答えはceil(ΣA / 2)以上の最小の部分和になる
# dp[i][j] = A_1～A_iで部分和jを作れるか？とすると, O(max(A_i) * N^2)で間に合わないように見える.
# しかしdp[i][j]の遷移は「シフト, コピー」のみなので、ビット演算によって高速化できる。
# pythonでは間に合わないよなあ…と一見思うかもしれないが、ビット演算の内部はおそらくc++なので多分間に合う。
# for文を使うと、一気に低速になるので(体感c++の50倍時間がかかる）、配列の和・値の検索あたりでは、ライブラリを使いたいところ。

n = int(input())
a = [int(i) for i in input().split()]
dp = 1
for i in range(0, len(a)):
	dp = (dp | (dp << a[i]))

asum = 0
for i in range(0, len(a)):
	asum += a[i]

for i in range(int((asum + 1) / 2), asum + 1):
	if (dp >> i) & 1:
		print(i)
		break


Measured memory_bytes: 5424
#include<iostream>

using namespace std;

int main() {
	int n, x;

	cin >> n >> x;

	int l[105];
	for (int i = 0; i < n; i++) {
		cin >> l[i];
	}
	int sum = 0;
	int ans = 1;
	for (int j = 0; j < n; j++) {
		sum += l[j];
			if (sum <= x) {
				ans += 1;
			}
			else {
				break;
			}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
r,c = [int(x) for x in input().split()]
       
a = [[0 for i in range(c)] for j in range(r)] #c:列 r:行
for i in range(r):
    a[i] = [int(x) for x in input().split()]


b = [[0 for row in range(c+1)]for line in range(r+1)]
for i in range(r):
    for j in range(c):
            b[i][j] = a[i][j]
            
for i in range(r):
    b[i][c] = sum(b[i])

for j in range(c):
    for i in range(r):
        b[r][j] += b[i][j]
        
b[r][c] = sum(b[r])

for i in range (r + 1):
    print(" ".join(map(str,b[i])))


Measured memory_bytes: 5776
/*

Author: Ayush Shah :)
Institution: BIT Mesra :)

*/


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


/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;  //find_by_order(), order_of_key() 
*/


#define deb(x) cout << #x << " " << x << endl
#define fast  ios_base::sync_with_stdio(false), cin.tie(NULL) , cout.tie(NULL)
#define ll long long int 
#define ld long double
#define pb  push_back
#define mp  make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define forn(i,a,n) for(ll (i) = a;(i) <= (n); (i)++)
#define vi vector<int >
#define vl vector<ll >
#define pi pair<int , int>
#define pl pair<ll , ll>
#define vpi vector< pi >
#define vpl vector< pl >
#define bigint int64_t
#define mod 1000000007
#define endl '\n'
const ll INF = 1e9 + 5;

//template<typename T>
// typedef tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


ll power(ll x, ll n){
    if(n==0)
    return 1;
    
    if(n%2)
    return (x*power((x*x)%mod, (n-1)/2))%mod;
    else
    return power((x*x)%mod, n/2);
}



int main()
{
  
      fast;

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

    
    int n, k;
    cin >> n ;
    ll h[n];
    ll dp[n];
    dp[0] = 0;
    for(int i=1; i<n; i++)
    dp[i] = INF;
    for(int i=0; i<n; i++){
    	cin >> h[i];
    }
    for(int i=0; i<n; i++){
    	for(int j: {i+1, i+2}){
    		if(j < n)
    		dp[j] = min(dp[j], dp[i]+abs(h[i] - h[j])); 
    	}
    }
    
    cout << dp[n-1] << endl;
    



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




    return 0;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<pair<int,int> >red(n);
  vector<pair<int,int> >blue(n);
  for(int i=0;i<n;++i){
    cin>>red[i].first>>red[i].second;
  }
  for(int i=0;i<n;++i){
    cin>>blue[i].first>>blue[i].second;
  }
  sort(red.begin(),red.end());
  sort(blue.begin(),blue.end());
  vector<int>by;
  int ans=0;
  
  while(! red.empty()){
    int temp_x=red.back().first;
    int temp_y=red.back().second;
    
    red.pop_back();
    while( (not blue.empty()) && (temp_x < blue.back().first) )  {
      by.push_back(blue.back().second);
      blue.pop_back();
    }
    int j = -1;
    for(int i=0;i<by.size();++i){
      if(temp_y<by[i]){
        if(j==-1 || by[i] < by[j]){
          j=i;
         }
       }
     }
     if(j != -1){
        by.erase(by.begin() + j);
        ++ans;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
import math
import sys
# import os
# f = open('input.txt', 'r')
# sys.stdin = f

n = int(input())
h = list(input().split())
h = [int(i) for i in h]
dp = [100000]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2, n):
    dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))
print(dp[n-1])


Measured memory_bytes: 13716
#define _USE_MATH_DEFINES
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

/*
thx
http://kmjp.hatenablog.jp/entry/2016/11/25/0930
2点を同時に動かす
動き方は{RR,RD,DR,DD}の4通り
同じ地点に到達するのはスタート地点と
移動後に同じ場所になるかだけ、
以前の位置には到達できない(RかDの移動だけなので)
*マンハッタン距離として増加方向だけ許されている
*/
void solve(){
	int H,W;
	cin>>H>>W;
	vector<vector<int> > A(H,vector<int>(W));
	for(int h=0;h<H;++h){
		for(int w=0;w<W;++w){
			cin>>A[h][w];
		}
	}

	vector<vector<vector<LL> > > dp(H+W,
		vector<vector<LL> >(H,
			vector<LL>(W,0)
			)
			);
	dp[0][0][0] = A[0][0];
	for(int i=0;i<H+W-2;++i){//
		int x1,x2,y1,y2;
		//位置を順番に総当り
		for(y1=0;y1<H;++y1){
		for(y2=0;y2<H;++y2){
			x1 = i-y1;
			x2 = i-y2;
			//範囲外,y1は範囲内ループさせてる
			if(x1<0 || x1>=W || x2<0 || x2>=W)continue;
			LL v = dp[i][y1][y2];
			//RR
			if(x1+1<W && x2+1<W ){
				if(y1==y2){//同じ位置なので増えるの移動先はひとつ
					dp[i+1][y1][y2] = max(dp[i+1][y1][y2],v+A[y1][x1+1]);
				}else{
					dp[i+1][y1][y2] = max(dp[i+1][y1][y2],v+A[y1][x1+1]+A[y2][x2+1]);
				}
			}
			//RD
			if(x1+1<W && y2+1<H){
				if(x1+1==x2){
					dp[i+1][y1][y2+1]=max(dp[i+1][y1][y2+1],v+A[y1][x1+1]);
				}else{
					dp[i+1][y1][y2+1]=max(dp[i+1][y1][y2+1],v+A[y1][x1+1]+A[y2+1][x2]);
				}
			}
			//DR
			if(y1+1<H && x2+1<W){
				if(y1+1==y2){
					dp[i+1][y1+1][y2]=max(dp[i+1][y1+1][y2],v+A[y1+1][x1]);
				}else{
					dp[i+1][y1+1][y2]=max(dp[i+1][y1+1][y2],v+A[y1+1][x1]+A[y2][x2+1]);
				}
			}
			//DD
			if(y1+1<H && y2+1<H){
				if(y1==y2){//y1+1==y2+1
					dp[i+1][y1+1][y2+1]=max(dp[i+1][y1+1][y2+1],v+A[y1+1][x1]);
				}else{
					dp[i+1][y1+1][y2+1]=max(dp[i+1][y1+1][y2+1],v+A[y1+1][x1]+A[y2+1][x2]);
				}
			}
		}}
	}
	LL ans = dp[H+W-1-1][H-1][H-1];
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()


Measured memory_bytes: 128896
n = int(input())
houses = [[[0] * 10 for i in range(3)] for i in range(4)]

for i in range(n):
  a, b, c, d = map(int, input().split())
  houses[a-1][b-1][c-1] += d

i = 0
for house in houses:
  for line in house:
    for num in line:
      print('', num, end = '')
    print()
  if i < 3:
    print('#' * 20)
  i += 1



Measured memory_bytes: 5632
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>
#include <stack>
#include <algorithm>
#include <stdio.h>
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a < b)
	{
		cout << "a < b" << endl;
	}
	else if (a > b)
	{
		cout << "a > b" << endl;
	}
	else if (a == b)
	{
		cout << "a == b" << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println(solve(in.nextInt(), in.nextInt(), in.nextInt()));
    }
    public static int solve(int A, int B, int K) {
        int c = 0;
        for (int i = Math.max(A, B); ; i--) {
            if (A % i == 0 && B % i == 0) {
                if (++c == K) {
                    return i;
                }
            }
        }
    }
}


Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,a,b,c;
	cin>>a>>b>>c;
	for(i=0;i<=b;i++)
	{
		if(i*a%b==c)
		{
			cout<<"YES\n";
			return 0;
		}
	}
	cout<<"NO\n";
	return 0;
}

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

int main(){
int x,y;
cin>>x>>y;
int ans=0;
if(x==1&&y==1){
    cout<<1000000<<endl;
    return 0;
}
if(x==1){
    ans+=300000;
}else if(x==2){
    ans+=200000;
}else if(x==3){
    ans+=100000;
}
if(y==1){
    ans+=300000;
}else if(y==2){
    ans+=200000;
}else if(y==3){
    ans+=100000;
}
cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	if(n > 81) printf("No\n");
	else if(n <= 9) printf("Yes\n");
	else{
		int ok = 0;
		for(int i = 2; i <= 9; i++){
			if(n % i == 0){
				int t = n / i;
				if(t <= 9 && t >= 1){
					ok = 1; break;
				}
			}
		}
		printf("%s\n", ok ? "Yes" : "No");
	}
}

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

public class Main {
	static PrintWriter out;
	static StringBuilder sb;
	static long mod = 998244353;
	static int inf = (int) 1e15;
	static ArrayList<Integer>[] ad;
	static int n, k;
	static long[][] memo;
	static char[][] g;
	static boolean[] vis;
	static long ans, tem;
	static long[] a;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int n = sc.nextInt();
		long ans = 0;
		ad = new ArrayList[n + 1];
		long[] pr = new long[n + 1];
		for (int i = 0; i <= n; i++)
			ad[i] = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int x = sc.nextInt();
			ad[x].add(i);
			ans += ad[x].size() - 1;
		}
        for(int i=1;i<=n;i++) {
        	long tem=ad[i].size()*(ad[i].size()-1)/2;
        	long tem1=(ad[i].size()-1)*(ad[i].size()-2)/2;
        	for(int j:ad[i])
        		pr[j]=ans-tem+tem1;
        }
        for(int i=0;i<n;i++)
        	out.println(pr[i]);
		out.close();
	}

	static long cal(int i, int u, int p) {
		if (memo[i][u] != -1)
			return memo[i][u];
		long ans = 1;
		for (int v : ad[i]) {
			if (v == p)
				continue;
			if (u == 0) {
				long tem = 0;
				tem = (2 * cal(v, 0, i)) % mod;
				tem = (tem + 2 * cal(v, 1, i)) % mod;
				tem = (tem - cal(v, 2, i) + mod) % mod;
				ans = ans * tem % mod;
			} else if (u == 1) {
				long tem = 0;
				tem = (2 * cal(v, 0, i)) % mod;
				tem = (tem + cal(v, 1, i)) % mod;
				tem = (tem - cal(v, 2, i) + mod) % mod;
				ans = ans * tem % mod;
			} else {
				long tem = 0;
				tem = cal(v, 0, i) % mod;
				tem = (tem + cal(v, 1, i)) % mod;
				tem = (tem - cal(v, 2, i) + mod) % mod;
				ans = ans * tem % mod;
			}
		}
		return memo[i][u] = ans;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

Measured memory_bytes: 69584
n, m, q = map(int, input().split())
abcd = [list(map(int , input().split())) for _ in range(q)]

ans = 0
import itertools
for a in itertools.combinations_with_replacement(range(1, m+1), n):
    tmp = 0
    for j in abcd:
        if a[j[1]-1] - a[j[0]-1] == j[2]:
            tmp += j[3]
    ans = max(ans, tmp)
print(ans)


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

using namespace std;

bitset<4000005> b;

int S,N;

int main() {

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N;

b=1;

for(int i=0; i<N; i++){
  int a;
  cin>>a;
  S+=a;
  b|=b<<a;
}

if(S%2) S++;

for(int i=S/2; i<=4000000; i++){
  if(b[i]){
    cout<<i<<endl;
    return 0;
  }
}

}


Measured memory_bytes: 1792
#include <iostream>
#define X 3000
using namespace std;

int main(){
      int R,G,B,N;
      int ans=0;

      cin >> R >> G >> B >> N;  

      for(int i=0;i <= X;i++){
            for(int j=0;j <= X; j++){
                  int k = N - i * R - j *G;
                  if(k >= 0 && k % B ==0)ans++;
            }
      }
      cout << ans << endl;
}


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

int n, m, q;
vector<int> a, b, c, d;

int score(vector<int>& retu) {
    int score = 0;
    for (int i = 0; i < q; i++) {
        if ((retu[b[i]] - retu[a[i]]) == c[i]) score += d[i];
    }
    return score;
}

void dfs(vector<int>& retu, int keta, int& s) {
    if (keta == 0) {
        for (int i = 1; i <= m; i++) {
            retu[keta] = i;
            if (keta == n - 1) {
                s = max(s, score(retu));
            }
            else {
                dfs(retu, keta + 1, s);
            }
        }
    }
    else if (keta == n - 1) {
        for (int i = retu[keta - 1]; i <= m; i++) {
            retu[keta] = i;
            s = max(s, score(retu));
        }
    }
    else {
        for (int i = retu[keta-1]; i <= m; i++) {
            retu[keta] = i;
            dfs(retu, keta + 1, s);
        }
    }
}

int main(void) {

    cin >> n >> m >> q;

    a = vector<int>(q);
    b = vector<int>(q);
    c = vector<int>(q);
    d = vector<int>(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }

    // 全探索
    auto retu = vector<int>(n);
    int score = 0;
    dfs(retu, 0, score);

    cout << score << endl;

    return 0;

}


Measured memory_bytes: 3580
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int L=0;
	int R=mod;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		L=max(L,p);
		R=min(R,q);
	}
	printf("%d\n",max(0,R-L+1));
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
const long MOD = 1000000007;
#define all(a) a.begin(), a.end()
#define eall(a) a.begin()+1, a.end()
#define show(ans)  cout << ans << endl;


int main(){
std::priority_queue<
      long,                // 要素の型はint
      std::vector<long>,   // 内部コンテナはstd::vector (デフォルトのまま)
      std::greater<long>   // 昇順 (デフォルトはstd::less<T>)
    > que;
long N, M, tmp, Btmp, Ctmp;
cin >> N >> M;
erep(i, N){
    cin >> tmp;
    que.push(tmp);
}
vector<pair<long, long>> v;
erep(i, M){
    cin >> Btmp >> Ctmp;
    v.push_back(make_pair(Ctmp, Btmp));
}
sort(all(v));
reverse(all(v));




// rep(i, v.size()){
//     cout << v[i].first << "," << v[i].second << endl;
// }


long k = 0;
rep(i, v.size()){
    if(k > N) break;
    erep(j, v[i].second){
        if(k > N) break;
        k++;
        que.push(v[i].first);
        que.pop();
    }
}


// while(!que.empty()){
//     show(que.top());
//     que.pop();
// }



long sum = 0;
while(!que.empty()){
    sum += que.top();
    que.pop();
}
show(sum);
return 0;
}

Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;
const int N=1e5+5;
const int mod=1e9+7;
int n,p1,p2,val[N],fac[N],ifac[N],pos[N];

namespace utils{
	template <class T> inline void apn(T &x,const T y){x>y?x=y:0;}
	template <class T> inline void apx(T &x,const T y){x<y?x=y:0;}
	inline int nxi(){
		int x=0;
		char c;
		while(((c=getchar())>'9'||c<'0')&&c!='-');
		const bool f=(c=='-')&&(c=getchar());
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

template <class T>
inline int fpow(int x,T t){
	int ans=1;
	for(; t; x=(lint)x*x%mod,t>>=1){
		if(t&1) ans=(lint)ans*x%mod;
	}
	return ans;
}

void init(){
	fac[0]=1;
	for(int i=1; i<=n+1; ++i){
		fac[i]=(lint)fac[i-1]*i%mod;
	}
	ifac[n+1]=fpow(fac[n+1],mod-2);
	for(int i=n+1; i>=1; --i){
		ifac[i-1]=(lint)ifac[i]*i%mod;
	}
}

inline int C(const int x,const int y){
	if(x<y||y<0) return 0;
	return (lint)fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}

int main(){
	n=nxi();
	init();
	for(int i=1; i<=n+1; ++i){
		val[i]=nxi();
		if(pos[val[i]]) p1=pos[val[i]],p2=i;
		else pos[val[i]]=i;
	}
	for(int i=1; i<=n+1; ++i){
		int tmp=((lint)C(n-1,i)+C(n-1,i-1)*2+mod-C(n-p2+p1,i-1))%mod;//0,1
		printf("%d\n",(tmp+C(n-1,i-2))%mod);//2
	}
	return 0;
}


Measured memory_bytes: 2816
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007


signed main(){
    vector<int> v;
    int N;
    double x[10],y[10];

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
        v.push_back(i);
    }

    double sum=0;
    double c=0;
    do{
        c++;
        for(int i=1;i<v.size();i++){
            sum+=sqrt(pow(x[v[i]]-x[v[i-1]],2)+pow(y[v[i]]-y[v[i-1]],2));
        }
    }while(next_permutation(v.begin(),v.end()));
    printf("%.12f\n",sum/c);
}


Measured memory_bytes: 3828
import math
(n, m) = map(int, input().split())
sm = int(math.sqrt(m)) + 1
params = {m:1}
for i in range(1, sm + 1):
    if m % i == 0 :
        params[i] = 1
        params[m // i] = 1
params = sorted(params)
mdn = m // n
maxans = 0
for i in params:
    if n > m / i:
        break
    maxans = i
print(maxans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using Graph = vector<vector<bool>>;
const int MOD = 1e9 + 7;

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

    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; ++i)
        cin >> w[i] >> v[i];
    int ma = W / w[0];

    static int dp[103][103][303];
    for (int i = 0; i < N; ++i) {
        int tmp = w[i] - w[0];
        for (int j = 0; j <= min(i, ma); ++j) {
            for (int k = 0; k <= 300; ++k) {
                dp[i + 1][j + 1][k] = dp[i][j + 1][k];
                if (k - tmp >= 0)
                    dp[i + 1][j + 1][k] = max(dp[i][j][k - tmp] + v[i], dp[i + 1][j + 1][k]);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= ma; ++i)
        ans = max(ans, dp[N][i][min(W - w[0] * i, 300)]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10752
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <chrono>
using namespace std;

using namespace std;
using ll = long long;

int main() {
	int x, y;
	cin >> x >> y;
	cout << x + y/2 << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define SORT(v) sort(v.begin(), v.end())
#define veci(a, n) vector<int> a(n)
#define vecs(a, n) vector<string> a(n)
#define pb(a) push_back(a)

int main(){
    int N;
    cin >> N;
    veci(a, N);
    REP(i, N) cin >> a.at(i);
    SORT(a);
    cout << a.at(N-1)-a.at(0) << endl;
    return 0;
}


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

bool compare(const int x, const int y)
{
	return x > y;
}

int main()
{
	std::unordered_map<int, int> mapa;
	int count = 0;
	int n;
	std::cin >> n;
	
	int a[100010] = { 0 }, change[100010] = { 0 }, identify[100010] = { 0 };
	for (int i = 0; i < n; ++i)
	{
		std::cin >> a[i];
		
		if (mapa.find(a[i]) != mapa.end())
			++change[mapa[a[i]]];
		else
		{
			mapa.insert(std::make_pair(a[i], count));
			identify[count] = a[i];
			++change[count];
			++count;
		}
	}
	
	std::vector<long long int> vec;
	
	for (int i = 0; i < count; ++i)
	{
		if (change[i] > 1)
		{
			vec.push_back(identify[i]);
			change[i] -= 2;
		}
		if (change[i] > 1)
		{
			vec.push_back(identify[i]);
		}
	}
	
	std::sort(vec.begin(), vec.end(), compare);
	if (vec.size() < 2)
		std::cout << 0;
	else
		std::cout << (vec[0] * 1LL) * vec[1];
}

Measured memory_bytes: 5540
n = int(input())
a = list(map(int, input().split()))
A = [0]*(n)
num = 1000000007
ans = 0
for i in range(1, n):
    A[i] = int((A[i-1] + a[i-1])%num)
for i in range(n-1, 0, -1):
    ans += int((A[i]*a[i])%num)
    ans = int(ans % num)
print(int(ans))

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    char a, b;
    cin >> a >> b;
    if (a == 'H')
    {
        OP(b);
    }
    else
    {
        cout << (b == 'H' ? 'D' : 'H') << endl;
    }

    return 0;
}

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

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if (b - a == c - b)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	
}

Measured memory_bytes: 384
<?php
class In {
    private $array = [];
    private $length = 0;
    private $count = 0;

    function __construct()	{
        while (!feof(STDIN)) {
            $str = trim(fgets(STDIN));
            $this->array = array_merge($this->array, explode(' ', $str));
        }
        $this->length = count($this->array);
    }
    
    public function get(int $i){
        $this->array[$i];
    }

    public function next() {
        return $this->array[$this->count++];
    }
    public function hasNext() {
        return $this->count < $this->length;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
    public function nextString() {
        return (string)$this->next();
    }
}

class Out {
    public static function line($str = "") {
        echo $str . PHP_EOL;
    }
}

$in = new In();
Out::line(str_replace("0", "9", str_replace("9", "1", str_replace("1", "0", $in->nextString()))));


Measured memory_bytes: 4856
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>

using namespace std;

int main()
{
    int x; scanf("%d", &x);
    if(x)
        printf("0");
    else
    {
        printf("1");
    }
    return 0;
    
}

Measured memory_bytes: 1644