akhauriyash/Code-Regression huggingface dataset:
n, m  = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
li = [list(map(int, input().split())) for _ in range(m)]
li.sort(key = lambda x:(-x[1], x[0] ))
b_point=0
for i in range(n):
    if a[i] < li[b_point][1]:
        a[i] =  li[b_point][1]
        li[b_point][0] -= 1
        if li[b_point][0] == 0:
            b_point += 1 
            if b_point == m:
                break
    else:
        break

print(sum(a))

Measured memory_bytes: 42448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> i_i;

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((ll)(x).size())

const double PI  = acos(-1.0);
const double EPS = 1e-9;
const int INF = 1e9+10;
const ll mod = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define print(x) cerr << #x << " is " << x << endl;
//#define print(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 


int main()
{
    ll N;
    cin >> N;
    ll ans = 0;
    for (ll x = 1; x <= N; x++){
        ll y = N/x;
        ans += x * y * (y + 1)/2;
    }
    cout << ans;
    return 0;
 
}


Measured memory_bytes: 3624
<?php
    fscanf(STDIN, "%s", $s);
    $result = '';
    if($s == 'Sunny'){
        $result = 'Cloudy';
    }elseif($s == 'Cloudy'){
        $result =  'Rainy';
    }else{
        $result = 'Sunny';
    }
    echo $result;
  ?>

Measured memory_bytes: 3700
#include<iostream>

using namespace std;

int main()
{
	string s;
	getline(cin,s);
	for(int i=0;i<s.length();i++)
	{
		if(s[i]>='a'&&s[i]<='z')s[i]+='A'-'a';
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 3144
#include<iostream>
#define ll long long
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_set>
#include <iomanip>
using namespace std;
ll ans = 0;



int main()
{
    ll n;
    cin>>n;
    long double ans=0;
    long double  arr[n+1];
    arr[0] = 0;
    for(int i =1; i<=n; ++i)
    {
        cin>>arr[i];
    }
    long double dp[n+1][n+1] = {0};

    for(int i=0; i<=n; ++i)
    {
        for(int j=0; j<=n; ++j)
        {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = 1;
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<=n; ++j)
        {
            if(j==0)
            {
                dp[i][j] = ( (long double)1 - arr[i])*dp[i-1][j];
                continue;
            }
            else
            {
                dp[i][j] = dp[i-1][j]*( (long double)1 - arr[i]) + dp[i-1][j-1]*arr[i];
            }
        }
    }

    for(int i = n; i> n/2; --i)
    {
        ans += dp[n][i];
    }
    cout<<setprecision(10);
    cout<<ans;


    return 0;
}


Measured memory_bytes: 140928
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, m;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  cout << (n == m ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
num = input("").split(" ")
num = [int(i) for i in num]
K = int(input(""))

for i in range(0, K):

    if num[1] >= num[2]:
        num[2] = num[2] * 2

    elif num[0] >= num[1]:
        num[1] = num[1] * 2

    elif num[0] >= num[2]:
        num[2] = num[2] * 2

    else:
        num[2] = num[2] * 2

if num[2] > num[1] > num[0]:
    print("Yes")
else:
    print("No")

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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

#define ull unsigned ll

const int maxn = 505;
int n;
int s[maxn], t[maxn];
ull _u[maxn], _v[maxn];
int u[maxn], v[maxn];
int cur[maxn][maxn];
ull ans[maxn][maxn];

bool chk() {
	rep(i, n) if (s[i]) {
		ull x = 0;
		rep(j, n) x |= ans[i][j];
		if (x != _u[i]) return 0;
	}
	rep(i, n) if (!s[i]) {
		ull x = -1;
		rep(j, n) x &= ans[i][j];
		if (x != _u[i]) return 0;
	}
	rep(i, n) if (t[i]) {
		ull x = 0;
		rep(j, n) x |= ans[j][i];
		if (x != _v[i]) return 0;
	}
	rep(i, n) if (!t[i]) {
		ull x = -1;
		rep(j, n) x &= ans[j][i];
		if (x != _v[i]) return 0;
	}
	return 1;
}

int main() {
	scanf("%d", &n);
	rep(i, n) scanf("%d", &s[i]);
	rep(i, n) scanf("%d", &t[i]);
	rep(i, n) scanf("%llu", &_u[i]);
	rep(i, n) scanf("%llu", &_v[i]);
	rep(b, 64) {
		rep(i, n) u[i] = _u[i] >> b & 1;
		rep(i, n) v[i] = _v[i] >> b & 1;
		rep(i, n) rep(j, n) cur[i][j] = 0;
		vector <int> vr, vc;
		bool R[2], C[2];
		rep(f, 2) R[f] = C[f] = 0;
		rep(i, n) {
			if (!s[i] && u[i]) {
				rep(j, n) cur[i][j] = 1;
				R[1] = 1;
			} else if (s[i] && !u[i]) {
				rep(j, n) cur[i][j] = 0;
				R[0] = 1;
			} else {
				vr.pb(i);
			}
		}
		rep(j, n) {
			if (!t[j] && v[j]) {
				rep(i, n) cur[i][j] = 1;
				C[1] = 1;
			} else if (t[j] && !v[j]) {
				rep(i, n) cur[i][j] = 0;
				C[0] = 1;
			} else {
				vc.pb(j);
			}
		}
		if (vr.size() == 1) {
			rep(i, vc.size()) {
				if (R[v[vc[i]]]) cur[vr[0]][vc[i]] = u[vr[0]];
				else cur[vr[0]][vc[i]] = v[vc[i]];
			}
		} else if (vc.size() == 1) {
			rep(i, vr.size()) {
				if (C[u[vr[i]]]) cur[vr[i]][vc[0]] = v[vc[0]];
				else cur[vr[i]][vc[0]] = u[vr[i]];
			}
		} else {
			rep(i, vr.size()) rep(j, vc.size()) {
				cur[vr[i]][vc[j]] = (i + j) & 1;
			}
		}
		rep(i, n) rep(j, n)
			ans[i][j] |= ((ull) cur[i][j]) << b;
	}
	if (!chk()) { puts("-1"); return 0; }
	rep(i, n) rep(j, n) {
		printf("%llu", ans[i][j]);
		putchar(j + 1 == n ? '\n' : ' ');
	}
	return 0;
}


Measured memory_bytes: 8504
def main():
  #xの根を求める
  def find(x):
      if par[x] < 0:
          return x
      else:
          px = find(par[x])
          wei[x] += wei[par[x]]
          par[x] = px
          return px

  #xの根から距離
  def weight(x):
      find(x)
      return wei[x]


  #w[y]=w[x]+wとなるようにxとyを併合
  def unite(x,y,w):
      w += wei[x]-wei[y]
      x = find(x)
      y = find(y)

      if x == y:
          return False
      else:
          #sizeの大きいほうがx
          if par[x] > par[y]:
              x,y = y,x
              w = -w
          par[x] += par[y]
          par[y] = x
          wei[y] = w
          return True

  #xとyが同じ集合に属するかの判定
  def same(x,y):
      return find(x) == find(y)

  #x,yが同じ集合に属するときのwei[y]-wei[x]
  def diff(x,y):
      return weight(y)-weight(x)

  import sys
  input = sys.stdin.readline  
  n,m = [int(i) for i in input().split()]
  par = [-1]*n
  wei = [0]*n

  for i in range(m):
    l,r,d = [int(i) for i in input().split()]
    if not same(l-1,r-1):
      unite(l-1,r-1,d)
    else:
      if diff(l-1,r-1) == d:
        continue
      else:
        print('No')
        exit()

  print('Yes')
if __name__ == '__main__':
    main()

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

const int mod=1e9+7;
ll modpow(ll a,ll n){
    ll res=1;
    while(n>0){
        if(n&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
int main(){
    int n;cin>>n;
    ll ans=(modpow(10,n)-(modpow(9,n)*2)%mod+modpow(8,n))%mod;
    cout<<(ans+mod)%mod<<endl;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
#define ld double
#define FOR(i,a,n) for (int i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (int i=(n);i>=(a);--i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define f first
// #define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// I am questioning life and universe and 
// everything else after looking at this

const ll MAXN = 105;
const ll MAXK = 1e5 + 5;
const ll MOD = 1e9 + 7;
ll a[MAXN];
ll dp[MAXN][MAXK],prefix[MAXN][MAXK];
ll n,k;

ll rec_dp(ll,ll);

ll rec_prefix(ll idx,ll candies){
    if(candies < 0) return 0;
    if(idx == 0) return 1;

    ll &ans = prefix[idx][candies];
    
    if(ans != -1) return ans;

    ans = (rec_prefix(idx,candies-1) + rec_dp(idx,candies))%MOD;

    return ans;
}

ll rec_dp(ll idx,ll candies){
    if(candies < 0) return 0;
    if(idx == 0) return 1;

    ll &ans = dp[idx][candies];

    if(ans != -1) return ans;

    ans = (rec_prefix(idx-1,candies) - rec_prefix(idx-1,candies-a[idx]-1) + MOD)%MOD;

    return ans;
}

void solve(){

    memset(dp,-1,sizeof(dp));
    memset(prefix,-1,sizeof(prefix));
    
    cin>>n>>k;

    FOR(i,1,n) cin>>a[i];

    cout<<rec_dp(n,k);
}

signed main(){


    ll t;
    t = 1; 
    // cin>>t;
    FOR(tt,1,t){
        solve();
    }
    
}

Measured memory_bytes: 168960
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less   
using namespace __gnu_pbds;  
using namespace std;  
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> set1;
ll find(ll a,ll p[])
{
   //cout<<"find "<<a<<endl;
   if(a==p[a])
   return a;
   else return p[a]=find(p[a],p);

}
void join(ll a,ll b,ll p[],ll sz[])
{
   a=find(a,p);
   b=find(b,p);
   if(a!=b)
   {
      if(sz[a]<sz[b])
      swap(a,b);
      sz[a]+=sz[b];
      p[b]=a;
   }
}
ll power(ll a,ll b,ll mod)
{
   ll res=1;
   while(b>0)
   {
      if(b&1)
      res=(res*a)%mod;
      b=b/2;
      a=(a*a)%mod;
   }
   return res;
}
ll inverse(ll x, ll p)
{
   return power(x,p-2,p);
}
ll hash1(ll x,ll y)
{
   return x+y+x*y;
}
//ll f[200000]={0};
ll mod=1000000007;
/*void ini()
{
   f[0]=1;
   for(ll i=1;i<=200000;i++)
   f[i]=(i*f[i-1])%mod;
}*/



/*ll ncr(ll n,ll r)
{
   ll res=1;
   ll k=f[n];
   ll v=inverse(f[n-r],mod);
   ll u=inverse(f[r],mod);
   ll x=(u*v)%mod;
   k=(k*x)%mod;
   return k;
}*/
/*struct edge
{
   ll from;
   ll to;
};
void dfs(ll v,ll vis[],ll dp[],vector<ll> adj[])
{
   ll k=adj[v].size();
   for(ll i=0;i<k;i++)
   {
      ll u=adj[v].at(i);
      if(vis[u]==0)
      {
         vis[u]=1;
         dfs(u,vis,dp,adj);
         dp[v]=max(dp[v],dp[u]+1);
      }
      else
      dp[v]=max(dp[v],dp[u]+1);
   }
}*/
ll f1(ll l,ll r,ll dp[][3001],ll a[])
{
  // cout<<l<<" form to "<<r<<endl;
   if(dp[l][r]!=-1)
   return dp[l][r];
   else if(l==r)
   {
      dp[l][r]=a[l];
    //  cout<<"dp["<<l<<"]["<<r<<"]"<<" "<<dp[l][r]<<endl;
      return dp[l][r];
   }
   else if(r-l==1)
   {
      
       dp[l][r]=max(a[r]-a[l],a[l]-a[r]);
    //   cout<<"dp["<<l<<"]["<<r<<"]"<<" "<<dp[l][r]<<endl;
       return dp[l][r];
   }
   else
   { dp[l][r]=max(a[l]+min(-a[r]+f1(l+1,r-1,dp,a),-a[l+1]+f1(l+2,r,dp,a)),a[r]+min(-a[l]+f1(l+1,r-1,dp,a),-a[r-1]+f1(l,r-2,dp,a)));
  // cout<<"dp["<<l<<"]["<<r<<"]"<<" "<<dp[l][r]<<endl;
   return dp[l][r];
   }
}


int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
    cin>>a[i];
    ll dp[n+1][3001];
    for(ll i=0;i<n;i++)
    {
       for(ll j=0;j<n;j++)
       dp[i][j]=-1;
    }
    
    cout<<f1(0,n-1,dp,a)<<endl;
   /* for(ll i=0;i<n;i++)
    {
       for(ll j=i;j<n;j++)
       cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
    }*/
    return 0;
}

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

bool isZero(vector<vector<int> > &v) {
    for (int i=0; i<v.size(); ++i) {
        for (int j=0; j<v[i].size(); ++j) {
            if (v[i][j] != 0) {
                return false;
            }
        }
    }
    return true;
}

int judge(vector<vector<int> > &v, int cnt) {
    if (cnt == 3 && isZero(v)) {
        return 1;
    }
    for (int i=0; i<3; ++i) {
        for (int j=0; j<9; ++j) {
            if (3 <= v[i][j]) {
                v[i][j] -= 3;
                if (judge(v, cnt + 1) == 1) {
                    return 1;
                } else {
                    v[i][j] += 3;
                }
            }
            if (j+2 < 9 && v[i][j] && v[i][j+1] && v[i][j+2]) {
                v[i][j] --; v[i][j+1] --; v[i][j+2] --;
                if (judge(v, cnt + 1) == 1) {
                    return 1;
                } else {
                    v[i][j] ++; v[i][j+1] ++; v[i][j+2] ++;
                }
            }
        }
    }
    return 0;
}

int main() {
    int t; cin >> t;
    while (t--) {
        vector<int> num(9);
        for (int i=0; i<9; ++i) cin >> num[i];
        vector<char> color(9);
        for (int i=0; i<9; ++i) cin >> color[i];

        vector<vector<int> > v(3, vector<int>(9));
        for (int i=0; i<9; ++i) {
            if (color[i] == 'R') {
                v[0][num[i]-1] ++;
            } else if (color[i] == 'G') {
                v[1][num[i]-1] ++;
            } else if (color[i] == 'B') {
                v[2][num[i]-1] ++;
            }
        }

        cout << judge(v, 0) << endl;
    }
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string str1, str2, ans;
    cin >> str1 >> str2;
    int p1 = str1.length();
    int p2 = str2.length();
    int c = 0;
    while (p1 > 0 || p2 > 0) {
      int a = 0, b = 0;
      if (p1 > 0) {
        a = str1[--p1] - '0';
      }
      if (p2 > 0) {
        b = str2[--p2] - '0';
      }
      ans = to_string((a + b + c) % 10) + ans;
      c = (a + b + c) / 10;
    }
    if (c != 0) {
      ans = to_string(c) + ans;
    }
    if (ans.length() > 80) {
      cout << "overflow\n";
    } else {
      cout << ans << "\n";
    }
  }
  return 0;
}


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

int main() {
	string s;
  	cin >> s;
  	
  	if(s[2]==s[3] && s[4]==s[5]) {
      cout << "Yes" << endl;
    }else {
      cout << "No" << endl;
    }
  
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000
#define NIL -1
 
struct node {
  int p, l, r, t;
};
struct node T[MAX];

void depth(int);
int height(int);
void print(int);

int n, H, D[MAX], h[MAX];
 
int main()
{
  int i, d, v, c, l, r;
   
  scanf("%d", &n);
   
  for ( i = 0; i < n; i++ ) {
    T[i].p = NIL;
    T[i].l = NIL;
    T[i].r = NIL;
  }
   
  for ( i = 0; i < n; i++ ) {
    scanf("%d %d %d", &v, &l, &r);
    if(l != NIL) {
      T[l].p = v;
    }
    if(r != NIL) {
      T[r].p = v;
    }
    T[v].l = l;
    T[v].r = r;
  }
  for ( i = 0; i < n; i++ ){
    if(T[i].l != NIL) {
      T[i].t++;
    }
    if(T[i].r != NIL) {
      T[i].t++;
    }
  }
   
  for ( i = 0; i < n; i++ ) {
    if(T[i].p==NIL) {
      D[i] = 0; 
      depth(i); 
      break;
    }
  }
  for ( i = 0; i < n; i++ ) {
    h[i] = height(i); 
  }
 
  for ( i = 0; i < n; i++ ) {
    print(i);
  }

  return 0;
}

void depth(int u)
{
  int d = 0;

  if(T[u].r != NIL) {
    D[T[u].r] = D[u]+1;
    depth(T[u].r);
  }
  if(T[u].l != NIL) { 
    D[T[u].l] = D[u]+1;
    depth(T[u].l);
  }
}
 
int height(int u)
{
  int a = 0, s = 0;

  if(T[u].r == NIL && T[u].l == NIL) 
    return 0;
  if(T[u].l != NIL) {
    a = height(T[u].l)+1;
  }
  if(T[u].r != NIL) {
    s = height(T[u].r)+1;
  }
  if(a > s) 
    return a;
  else 
    return s;
}
 
void print(int u)
{
  printf("node %d: parent = %d,", u, T[u].p);
  if(T[u].p == NIL)
    printf(" sibling = -1, ");
  else if(T[T[u].p].r == u)
    printf(" sibling = %d, ", T[T[u].p].l);
  else if(T[T[u].p].l == u)
    printf(" sibling = %d, ", T[T[u].p].r);
  printf("degree = %d, ", T[u].t);
  printf("depth = %d, height = %d, ", D[u], h[u]);

  if(T[u].p == NIL)
    printf("root\n");
  else if(T[u].t == 0)
    printf("leaf\n");
  else
    printf("internal node\n");
}

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

ll n;

int main() {
	cin>>n;
	ll a[n+1], b[n+1], ans=0;
	map <ll, ll> m;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
		b[i]=i+a[i];
	}
	for (int i=1; i<=n; i++) {
		ans+=m[i-a[i]];
		m[b[i]]++;
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 29384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007;

ll dp[(1<<21)+5];

int main(){
  int N;
  cin >> N;
  vector<vector<int>> v(N, vector<int>(N,0));
  rep(i,N){
    rep(j,N){
      cin >> v[i][j];
    }
  }

  dp[0] = 1;
  for(ll S=0; S<(1<<N); S++){
    int num = 0;
    rep(i,N) if((S>>i)&1) num++;
    rep(j,N){
      if((((S>>j)&1) == 0) && v[num][j] == 1){
        dp[S | (1<<j)] += dp[S];
        dp[S | (1<<j)] %= MOD;
      }
    }
  }

  cout << dp[(1<<N)-1] << endl;
  
  return 0;
}


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

using namespace std;

int main(){
    long long n;
    cin >> n;
    vector<long long> a(n+1),b(n);
    for(long long i = 0;i < n+1;i ++){
        cin >> a.at(i);
    }
    for(long long i= 0;i < n;i ++){
        cin >> b.at(i);
    }

    long long ans = 0;

    for(long long i = 0;i < n;i ++){
        ans += min(a.at(i),b.at(i));
        b.at(i) -= min(a.at(i),b.at(i));

        ans += min(a.at(i+1),b.at(i));
        a.at(i+1) -= min(a.at(i+1),b.at(i));
    }

    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main() {
  int ans = 0;
  int R, G, B, N;
  cin >> R >> G >> B >> N;
  for(int r = 0; r <= 3000; r++) {
  	for(int g = 0; g <= 3000; g++) {
      if (r * R + g * G > N) break;
      if ((N - (r * R + g * G)) % B != 0) continue;
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

#define rep(i, n) for(int i = 0;i < n;i++)
const int INF = 1LL << 30;
const int MOD = 1000000007;

double dd(std::vector<int> a, std::vector<int> b, int n){
    double dist = 0;
    rep(i,n){
        dist += (a[i]-b[i])*(a[i]-b[i]);
    }
    return sqrt(dist);
}

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

    int n,d; cin >> n >> d;

    std::vector<std::vector<int>> x(n, std::vector<int>(d));
    rep(i,n) rep(j,d) cin >> x[i][j];

    int cnt = 0;

    rep(i,n) for(int j=i+1; j<n; j++){

        double dist = dd(x[i],x[j],d);
        if(dist == (int) dist) cnt++;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"io"
	"os"
)

func main() {
	solve(os.Stdin, os.Stdout)
}

func solve(in io.Reader, out io.Writer) {
	var a, b int
	fmt.Fscanf(in, "%d%d", &a, &b)

	fmt.Fprintln(out, (a-1)*(b-1))
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	defaultBufferSize = 1024
	maxBufferSize     = 1e6
	Mod               = 1e9 + 7
)

var sc = bufio.NewScanner(os.Stdin)

// sc.Buffer(make([]byte, defaultBufferSize), maxBufferSize)

func readInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

func readInt64() int64 {
	sc.Scan()
	i, err := strconv.ParseInt(sc.Text(), 10, 64)
	if err != nil {
		panic(err)
	}
	return int64(i)
}

func readfloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func ModComb(n, k int) int {
	if k == 0 {
		return 1
	}
	x, y := n, k
	for i := 1; i < k; i++ {
		x = x * (n - i) % Mod
		y = y * (k - i) % Mod
	}
	inv := ModInv(y)
	return x * inv % Mod
}

func ModFact(x int) int {
	fact := 1
	for i := 1; i <= x; i++ {
		fact = fact * i % Mod
	}
	return fact
}

func ModInv(x int) int {
	return ModPow(x, Mod-2)
}

func ModPow(a, n int) int {
	res := 1
	for n > 0 {
		if n%2 != 0 {
			res = res * a % Mod
		}
		a = a * a % Mod
		n /= 2
	}
	return res
}

func pow(a, n int) int {
	if n == 0 {
		return 1
	}

	ans := 0
	if n%2 == 0 {
		ans = pow(a*a, n/2)
	} else {
		ans = a * pow(a*a, (n-1)/2)
	}
	return ans
}

func intSliceReverse(slice []int) []int {
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
	return slice
}

func stringReverse(str string) string {
	runes := []rune(str)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func primeFactorization(x int) map[int]int {
	result := make(map[int]int, 0)
	for i := 2; i*i <= x; i++ {
		for x%i == 0 {
			result[i]++
			x /= i
		}
	}
	if x != 1 {
		result[x]++
	}
	return result
}

func isPrime(x int) bool {
	if x == 1 {
		return false
	}
	for i := 2; i*i <= x; i++ {
		if i == x {
			continue
		}
		if x%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	sc.Split(bufio.ScanWords)

	n := readInt()

	ans := 0
	for i := 1; i <= n; i++ {
		a := readInt()
		if i%2 != 0 && a%2 != 0 {
			ans++
		}
	}
	fmt.Println(ans)
}


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

int main(){
    ll x,y,X,Y;cin>>x>>y>>X>>Y;
    rep(i,0,Y-y)cout<<'U';
    rep(i,0,X-x)cout<<'R';
    rep(i,0,Y-y)cout<<'D';
    rep(i,0,X-x)cout<<'L';
    cout<<'L';
    rep(i,0,Y-y+1)cout<<'U';
    rep(i,0,X-x+1)cout<<'R';
    cout<<'D'<<'R';
    rep(i,0,Y-y+1)cout<<'D';
    rep(i,0,X-x+1)cout<<'L';
    cout<<'U';
}







Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	int dp[55][55];
	for(int i=0;i<55;i++){
		for(int j=0;j<55;j++){
			dp[i][j]=1e9;
		}
	}
	dp[0][0]=0;
	int h,w; cin >> h >> w;
	char a[h][w];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> a[i][j];
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i+1][j]-'0');
			dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a[i][j+1]-'0');
		}
	}
	cout << dp[h-1][w-1] << endl;
}


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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define dump_1(x1) cerr << #x1 << ": " << x1 << endl
#define dump_2(x1, x2) \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define dump_3(x1, x2, x3)                                                \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << endl
#define dump_4(x1, x2, x3, x4)                                            \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << endl
#define dump_5(x1, x2, x3, x4, x5)                                        \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define dump(...) \
  CHOOSE((__VA_ARGS__, dump_5, dump_4, dump_3, dump_2, dump_1, ~))(__VA_ARGS__)
#define check(s) cerr << s << endl

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using namespace std;

using ll = long long;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

ll f(ll A, ll B) { return 1 + max((ll)floor(log10(A)), (ll)floor(log10(B))); }

void solve(ll N) {
  ll ans = LINF;
  rep(i, N / 2 + 1) {
    ll a = i + 1;
    ll b = N / a;
    if (a > b) break;

    if (a * b == N) ans = min(ans, f(a, b));
  }
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll N;
  scanf("%lld", &N);
  solve(N);
  return 0;
}


Measured memory_bytes: 4024
//ITP1_8 //

#include <stdio.h>
#include <string.h>
int main(void)
{
	char str[1110];
	int a[1110];
	int n;
	int i;
	int j=0;
		

	while(1){
		scanf("%s" ,str);
		if (str[0]=='0') break;
		n = strlen(str);
		for (i=0;i<n;i++){
			a[j] += str[i]-'0';
		}
		j++;
	}

	for(i=0;i<j;i++){
		printf("%d\n" , a[i]);
	}
	return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int a,b,c,d,e,f;

double perc(double a,double b){
  return b/(a+b);
}
int main(){
  cin >> a >> b >> c >> d >> e >> f;
  vector<int> w,s;
   
  rep(i,f+1)rep(j,f+1){
    if(a*i*100 + b*j*100 <= f && a*i*100+ b*j*100 > 0) w.push_back(a*i*100+b*j*100);
  }  
  rep(i,f+1)rep(j,f+1){
    if(c*i+d*j <= f) s.push_back(c*i+d*j);
  }
  sort(w.begin(),w.end()); w.erase(unique(w.begin(),w.end()),w.end());
  sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end());

  double ans_d = 0; int ans_w = 100*a; int ans_s = 0;
  rep(i,w.size())rep(j,s.size()){
    
    if(perc(100,e) >= perc(w[i],s[j]) && w[i]+s[j] <= f){
      if(ans_d < perc(w[i],s[j])){
        ans_d = perc(w[i],s[j]);
        ans_w = w[i]; ans_s = s[j];
      }
    }
  }
  
  printf("%d %d",ans_w + ans_s,ans_s);
  
  return 0;
}

Measured memory_bytes: 1400
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

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

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

int N;
long long L[86];

int main() {
    cin >> N;
    L[0] = 2;
    L[1] = 1;
    if (N <= 1) {
        cout << L[N] << endl;
        return 0;
    }

    for (int i = 2; i <= N; i++) {
        L[i] = L[i - 1] + L[i - 2];
    }

    cout << L[N] << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  lll a,b,c,k;

  cin >> a >> b >> c >> k;

  lll sum  = 0;
  lll rest = k;

  // a
  if(a <= rest){
    sum = a;
    rest -= a;
  }
  else{
    sum = rest;
    rest = 0;
  }
  
  //cout << "sum:" << sum << endl;
  //cout << "rest:" << rest << endl;
  // b
  if( b <= rest){
    rest -= b;
  }
  else{
    rest = 0;
  }

  //cout << "sum:" << sum << endl;
  //cout << "rest:" << rest << endl;
  
  // c
  if( c <= rest){
    sum -= c;
  }
  else{
    sum -= rest;
    rest = 0;
  }
  
  //cout << "sum:" << sum << endl;
  //cout << "rest:" << rest << endl;
  
  cout << sum << endl;
   

  return 0;
}


Measured memory_bytes: 3644
;; D - String Formation

(defun process-query (q hd tl reversed)
  (if (zerop q)
      (list hd tl reversed)
      (case (read)
            (1 (process-query (1- q) tl hd (not reversed)))
            (2 (let* ((f (read))
                      (c (read-char))
                      (hd2 (if (eql f 1) (cons c hd) hd))
                      (tl2 (if (eql f 2) (cons c tl) tl)))
                     (process-query (1- q) hd2 tl2 reversed))))))

(defun solve (s q)
  (destructuring-bind (hd tl reversed)
                      (process-query q nil nil nil)
    (format t "~a~a~a~%"
      (coerce hd 'string)
      (if reversed (nreverse s) s)
      (coerce (nreverse tl) 'string))))

(defun main ()
  (let ((s (read-line))
        (q (read)))
    (solve s q)))

(main)


Measured memory_bytes: 62184
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e9;

int a[110000];

int main(){
	
	long long int n, S;
	cin >> n >> S;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	a[0] = 0;
	n++;
	
	int ans = INF;
	int sum = 0;
	int id = 0;
	
	for(int i = 0; i < n; i++){
		sum -= a[i];
		while(sum < S){
			if(id >= n){
				break;
			}
			id++;
			sum += a[id];
		}
		//cout << i << " " << id << endl;
		if(sum >= S){
			ans = min(ans, id - i);
		}
	}
	
	if(ans == INF){
		cout << "0" << endl;
	}else{
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3508
#include <iostream>
#include <cmath>

using namespace std;

int main(){
  long long x = 11;
  long long m=0;
  long long n;
  long long ans[57] = {};
  while (m<=55) {
    long long d = 2;
    long long max_d = ceil(sqrt((double)(x)));
    bool is_prime = true;
    while (d <= max_d) {
      if (x % d == 0) {
	is_prime = false;
	break;
      }
      d++;
    }
    if (is_prime) {
      ans[m] = x;
      m++;
    }
    x += 10;
  }
  cin >> n;
  for (int i=0;i<n;i++) {
    cout << ans[i];
    if (i<n-1) {
      cout << " ";
    } else {
      cout << endl;
    }
  }
  return(0);
}


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

int n,x[200000],y[200000],ans=1e9,nx,ny;
char u[200000],nu;
vector<pair<int,char>> line[200001],diag[400001];

void Hor(){
  for(int i=0;i<200001;i++) line[i].clear();
  for(int i=0;i<n;i++) line[x[i]].push_back({y[i],u[i]});
  for(int i=0;i<200001;i++){
    sort(line[i].begin(),line[i].end());
    for(int j=1;j<line[i].size();j++){
      if(line[i][j-1].second=='U' && line[i][j].second=='D'){
        ans=min(5*(line[i][j].first-line[i][j-1].first),ans);
      }
    }
  }
}

void Ver(){
  for(int i=0;i<400001;i++) diag[i].clear();
  for(int i=0;i<n;i++) diag[x[i]+y[i]].push_back({y[i],u[i]});
  for(int i=0;i<400001;i++){
    sort(diag[i].begin(),diag[i].end());
    for(int j=1;j<diag[i].size();j++){
      if(diag[i][j-1].second=='U' && diag[i][j].second=='R'){
        ans=min(10*(diag[i][j].first-diag[i][j-1].first),ans);
      }
    }
  }
}

void Rot(){
  for(int i=0;i<n;i++){
    nx=200000-y[i];ny=x[i];
    if(u[i]=='R')nu='U';
    if(u[i]=='U')nu='L';
    if(u[i]=='L')nu='D';
    if(u[i]=='D')nu='R';
    x[i]=nx;y[i]=ny;u[i]=nu;
  }
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>u[i];
  for(int i=0;i<4;i++){
    if(i<2)Hor();
    Ver();
    Rot();
  }
  if(ans<1e9)cout<<ans<<endl;
  else cout<<"SAFE"<<endl;
}


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

int main() {
  int D;
  cin >> D;
  
  vector<int> c(27), tmp(27);
  vector<vector<int>> s(D+1 , vector<int>(27));
  for (int i = 1; i <= 26; i++)  cin >> c.at(i);
  for (int i = 1; i <= D; i++)  for(int j = 1; j <= 26; j++)  {
    cin >> s.at(i).at(j);
  }
  
  vector<int> last(27);
  for (int i = 1; i <= 26; i++) last.at(i) = 0;
  
  vector<int> t(D+1);
  for (int i = 1; i <= D; i++)  cin >> t.at(i);
  
  int sf;
  for (int i = 1; i <= D; i++) {
    sf += s.at(i).at(t.at(i));
    last.at(t.at(i)) = i;
    
    for (int j = 1; j <= 26; j++) {
      sf -=c.at(j)*(i-last.at(j));
    }
    
    
    cout << sf << endl;
    
  }
  
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

bitset<8055> TX, TY;

char A[8055];
vector<int> XV, YV;

int N, X, Y, DX, DY;

int main() {
	scanf(" %s%d%d", A, &X, &Y);
	N = strlen(A);
	int i = 0;
	for(; i < N && 'F' == A[i]; i++) X--;
	for(int c = 0; i < N; i++) {
		if('T' == A[i]) {
			if(DX) {
				XV.eb(DX);
				DX = 0;
			}
			if(DY) {
				YV.eb(DY);
				DY = 0;
			}
			c ^= 1;
		}
		if('F' == A[i]) (c ? DY : DX)++;
	}
	if(DX) {
		XV.eb(DX);
		DX = 0;
	}
	if(DY) {
		YV.eb(DY);
		DY = 0;
	}
	X = abs(X); Y = abs(Y);

	TX[0] = TY[0] = true;
	for(int v : XV) {
		TX = (TX<<v) | (TX>>v);
	}
	for(int v : YV) {
		TY = (TY<<v) | (TY>>v);
	}
	puts(TX[X] && TY[Y] ? "Yes" : "No");
	return 0;
}

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

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { x.modm(y.modpow(mod - 2)); }

void main()
{
	auto K = RD;
	auto S = RD!string;

	if (S.length <= K)
		writeln(S);
	else
	{
		writeln(S[0..K], "...");
	}

	stdout.flush;
	debug readln;
}

Measured memory_bytes: 2704
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

class Combination {
public:
  static const ll MOD = 1e9 + 7;
  static const ll MAX = 100100;

private:
  long long fac[MAX], finv[MAX], inv[MAX];

  ll max;
  ll mod;

public:
  // テーブルを作る前処理
  Combination(ll aMax, ll aMod) : max(aMax), mod(aMod) {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < max; i++) {
      fac[i] = fac[i - 1] * i % mod;
      inv[i] = mod - inv[mod % i] * (mod / i) % mod;
      finv[i] = finv[i - 1] * inv[i] % mod;
    }
  }

  // 二項係数計算
  long long combi(ll n, ll k) {
    if(n < k)
      return 0;
    if(n < 0 || k < 0)
      return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> as(N);
  for(int i = 0; i < N; ++i) {
    cin >> as[i];
  }
  sort(as.begin(), as.end());
  Combination C(Combination::MAX, Combination::MOD);
  ll ans_max = 0;
  ll ans_min = 0;
  for(int i = 0; i < N; ++i) {
    ans_min += as[i] * C.combi((N - i) - 1, K - 1);
    ans_min %= Combination::MOD;
    ans_max += as[i] * C.combi(i, K - 1);
    ans_max %= Combination::MOD;
  }
  ll ans = (Combination::MOD + ans_max - ans_min) % Combination::MOD;
  cout << ans << endl;
  /*
  for(int l = 0; l + K <= N; ++l) {
    for(int r = as.size() - 1; r - l >= K - 2; --r) {
      // cout << l << " - " << r << endl;
      ll value = as[r] - as[l];
      auto cmb = C.combi(r - l - 1, K - 2);
      // cout << l << " - " << r << " : " << value << "*" << cmb << endl;
      ans += value * cmb;
      ans %= Combination::MOD;
    }
  }
  cout << ans << endl;
  */
  return 0;
}

Measured memory_bytes: 3328
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		int x = stdIn.nextInt();
		int y = stdIn.nextInt();


		int answer = x % y;

		while (answer != 0) {
			x = y;
			y = answer;
			answer = x % y;
		}

		System.out.println(y);
	}
}

Measured memory_bytes: 26328
s = list(input())
k = int(input())

for i in range(len(s)):
    a = 26-(ord(s[i])-97)
    # print(ord(s[i]))
    # print(a)
    if k >= a and a != 26:
        k -= a
        s[i] = "a"
# print(k)
s[-1] = chr(ord(s[-1]) + k % 26)
# print(ord(s[-1]))
print("".join(s))


Measured memory_bytes: 79548
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
//10の1/2乗（ルート）pow(10, 0.5)
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int k,s;
  cin >> k >> s;
  int count = 0;
  for(int x=0;x<=k;x++){
	  for(int y=0;y<=k;y++){
        int z = s - x - y;
        if(z >= 0 && z <= k)count++;
      }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long double,long double> P;
int n;
P p[10];
long double ans;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
    sort(p,p+n);
    do{
        for(int i=1;i<n;i++){
            ans+=sqrt((p[i].first-p[i-1].first)*(p[i].first-p[i-1].first)+(p[i].second-p[i-1].second)*(p[i].second-p[i-1].second));
        }
    } while(next_permutation(p,p+n));
    long double N=1;
    for(int i=2;i<=n;i++) N*=i;
    cout<<setprecision(20)<<ans/N<<endl;
    
}


Measured memory_bytes: 3800
#include<bits/stdc++.h>
using namespace std;
     
     
typedef long long ll;
typedef vector <int> vi;
typedef pair <int,int> pi;
typedef tuple <int,int,int> ti;

#define forn(i,a,n) for(int i = a; i < n ; i++)
#define mem(str,a) memset(str, a, sizeof(str));
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(nullptr)
const int MOD = 1e9+7, N = 1e7 + 10, E = 1e-9;
/*
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//vector <int> show;
//for (auto x : show)
//   cout << x << " ";
getline(cin,s);


*/

int main() {
    int n;
    cin >> n;
    long long int power = 1;
    int i = 1;
    while(i <= n) {
        power = (power*i) % MOD;
        i++;
    }
    cout << power << endl;
    return 0;
}


Measured memory_bytes: 256
import heapq
n, m = map(int, input().split())
aL = list(map(int, input().split()))
heap = []
ans = 0
for j in aL:
    heapq.heappush(heap, -j)
for i in range(m):
    max_ = heapq.heappop(heap)
    max_ = -(-max_ // 2)
    heapq.heappush(heap, max_)
while heap:
    a = heapq.heappop(heap)
    ans -= a
print(ans)

Measured memory_bytes: 66968
N, L = map(int, input().split())

T = []

for i in range(N):
    T.insert(i, L+i-1+1)

for i in range(101):
    if T.count(i) != 0:
        T.remove(i)
        break
    elif T.count(-i) != 0:
        T.remove(-i)
        break

print(sum(T))


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

// Type alias
using ll=long long;
using ld=double;

using pi=pair<int,int>;
using pll=pair<ll,ll>;
using pld=pair<ld,ld>;
using ti3=tuple<int, int, int>;

using vi=vector<int>;
using vll=vector<ll>;
using vld=vector<ld>;
using vpi=vector<pi>;
using vpll=vector<ll>;
using vpld=vector<ld>;
using vti3=vector<ti3>;

// Constants
const double EPS = 1e-9;
const int inf = numeric_limits<int>::max();

// Macro
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rrep(i,n) for(int i=int(n-1);i>=0;--i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,a,b) for(int i=int(b-1);i>=int(a);--i)
#define SHOW(a) cout << #a << " = " << a << endl
#define ARR(a,n) for(int i=0;i<int(n);++i) cout << #a << "[" << i << "]" << " = " << a[i] << endl

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

// Funtcions
ll pow(ll base, ll i, ll mod){
  ll a = 1;
  while(i){
    if (i & 1) {
      a *= base;
      a %= mod;
    }
    base *= base;
    base %= mod;
    i >>= 1;
  }
  return a;
}
ll gcd(ll a, ll b){
  while(b){
    ll c = a % b;
    a = b;
    b = c;
  }
  return a;
}
ll lcm(ll a, ll b){
  return a / gcd(a, b) * b;
}
template<typename T> bool chmin(T& a, const T& b) {
  if (a > b) return a = b, true; else return false;
}

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


void solve(){
  double a, b, x;
  cin >> a >> b >> x;

  cout << fixed << setprecision(20);
  if(a * a * b <= 2 * x){
    cout << atan((2.0d * a * a * b - 2.0d * x) / (a * a * a)) / M_PI * 180.0d << endl;
  }else{
    cout << atan(a * b * b / 2.0d / x) / M_PI * 180.0d << endl;
  }
}

int main(){
// FastIO
//ios_base::sync_with_stdio(false);
cin.tie(NULL);
  solve();
  return 0;
}

Measured memory_bytes: 384
#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/



int main(){
    int a,b;
    cin>>a>>b;
    if(a<1||a>9||b<1||b>9)cout<<-1;
    else cout<<a*b;
    return 0;
}


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

template <typename Monoid>
struct SegmentTree
{
  using F = function<Monoid(Monoid, Monoid)>;

  int sz;
  vector<Monoid> seg;

  const F f = [](i64 a, i64 b) { return a + b; };
  const Monoid M1 = 0;

  void init(int n)
  {
    sz = 1;
    while (sz < n)
      sz <<= 1;
    seg.assign(2 * sz, 0);
  }

  void set(int k, const Monoid &x)
  {
    seg[k + sz] = x;
  }

  void build()
  {
    for (int k = sz - 1; k > 0; k--)
    {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x)
  {
    k += sz;
    seg[k] = x;
    while (k >>= 1)
    {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b)
  {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1)
    {
      if (a & 1)
        L = f(L, seg[a++]);
      if (b & 1)
        R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const
  {
    return seg[k + sz];
  }

  template <typename C>
  int find_subtree(int a, const C &check, Monoid &M, bool type)
  {
    while (a < sz)
    {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if (check(nxt))
        a = 2 * a + type;
      else
        M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }

  template <typename C>
  int find_first(int a, const C &check)
  {
    Monoid L = M1;
    if (a <= 0)
    {
      if (check(f(L, seg[1])))
        return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1)
    {
      if (a & 1)
      {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt))
          return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template <typename C>
  int find_last(int b, const C &check)
  {
    Monoid R = M1;
    if (b >= sz)
    {
      if (check(f(seg[1], R)))
        return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for (b += sz; a < b; a >>= 1, b >>= 1)
    {
      if (b & 1)
      {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt))
          return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};

int main()
{
  i64 N, Q;
  string S;
  cin >> N >> S >> Q;
  vector<SegmentTree<i64>> seg(26);
  for (i64 i = 0; i < 26; i++)
    seg[i].init(N);
  for (i64 i = 0; i < N; i++)
    seg[S[i] - 'a'].set(i, 1);
  for (i64 i = 0; i < 26; i++)
    seg[i].build();
  for (i64 _ = 0; _ < Q; _++)
  {
    i64 type;
    cin >> type;
    if (type == 1)
    {
      i64 i;
      char c;
      cin >> i >> c;
      i--;
      if (S[i] != c)
      {
        seg[S[i] - 'a'].update(i, 0);
        seg[c - 'a'].update(i, 1);
        S[i] = c;
      }
    }
    else
    {
      i64 l, r;
      cin >> l >> r;
      i64 ans = 0;
      for (i64 i = 0; i < 26; i++)
      {
        if (0 < seg[i].query(l - 1, r))
          ans++;
      }
      cout << ans << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 214020
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int s,w; cin >> s >> w;
  if(w>=s){
    cout << "unsafe" << endl;
  }
  else{
    cout << "safe" << endl;
  }
  
}

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


int main() {
  int a[3] = {7,5,3};
  int b;
  cin >> b;
  for(int i = 0;i < 4;i++){
    if(i == 3){
      cout << "NO" << endl;
      break;
    }
    if(a[i] == b){
      cout << "YES" << endl;
      break;
    }
  }
}


Measured memory_bytes: 256