akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound

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

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

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

//memo
// setprecision()


int main() {
  int N;
  cin >> N;
  
  
  
  cout << N/3 << endl;
  
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int a,i,j;
  scanf("%d", &a);
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
      if(i*j==a){
        printf("Yes\n");
        return 0;
      }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
    long long ans=0;
	vector<int>a(n),b(n),c(n);
	int counta=0,countb=0,countc=0;
	for (int i=0;i<n;++i) cin>>a[i];
	for (int i=0; i<n;++i) cin>>b[i];
	for (int i=0; i<n;++i) cin>>c[i];
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	for (int i=0;i<n;++i) {
		long long mona = distance(a.begin(), lower_bound(a.begin(), a.end(), b[i]));
		long long monc = distance(upper_bound(c.begin(), c.end(), b[i]), c.end());
		ans+=mona*monc;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] a = new int[num];
        int[] result = new int[num];
        a[0] = 0;
        for (int i = 1; i < num; i++){
            a[i] = sc.nextInt();
        }
        for (int i = 1; i < num; i++){
            result[a[i] - 1]++;
        }
        for (int i = 0; i < num; i++){
            System.out.println(result[i]);
        }
    }
}


Measured memory_bytes: 62904
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	t=1;
	while(t--){
	  vector<int> arr(1000001,0);
	  int n;
	  cin>>n;
	  vector<int> p(n);
	  for(int i=0;i<n;i++){
	  	cin>>p[i];
	  	arr[p[i]]++;
	  }
	  int count=0;
	  for(int i=0;i<n;i++){
	  	int flag=0;
	  	if(arr[p[i]]>1)
	  	continue;
	  	for(int j=2;j<=sqrt(p[i]);j++){
	  		if(p[i]%j==0){
	  			if(arr[j]!=0||arr[p[i]/j]!=0)
	  			{
	  				flag=1;
	  				break;
				}
			  }
		 }
		 if(p[i]!=1&&arr[1]!=0)
		 flag=1;
		 if(flag==0)
		 count++;
	  }
	  cout<<count<<"\n";
	}
	return 0;
}

Measured memory_bytes: 7952
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<long long>> vvll;
typedef long double ld;
typedef std::vector<long double> vld;
typedef std::vector<std::vector<long double>> vvld;
using namespace std;
void yesno(bool state);

void Main(){
    string N,N_;
    cin >> N;

    transform(N.begin(),N.end(),N_.begin(),::toupper);
    yesno(N[0]==N_[0]);

}

int main(int argc, char const *argv[])
{
    Main();
    return 0;
}

void yesno(bool state){
    if(state)
        cout << "A" << endl;
    else
        cout << "a" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

int main() {
    cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);

    ll H, W, K;
    cin >> H >> W >> K;
    vvc c(H, vc(W));
    rep(i,H) rep(j,W) cin >> c[i][j];

    ll ans = 0;
    rep(bh, 1<<H) rep(bw, 1<<W) {
        ll tmp = 0;
        rep(i, H) rep(j, W) {
            if(bh>>i&1) continue;
            if(bw>>j&1) continue;
            if(c[i][j] == '#') tmp++;
        }
        if(tmp == K) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3660
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>

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

const long long MAX = 5100000;
const long long INF = 1LL << 60;
//const long long mod = 1000000007LL;
//const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

ll mod = 1;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	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*(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;
	}
};

mint dp[300][2000];

int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	ll n, k; scanf("%lld %lld %lld", &n, &k, &mod);
	dp[0][0] = 1;
	for (ll i = 0; i <= n * 2; i++) {
		for (ll S = 0; S < (1 << k) - 1; S++) {
			if (!(S >> (k - 1) & 1)) {
				ll nS = (S << 1) + 1;
				dp[i + 1][nS] += dp[i][S];
			}
			if (S != 0) {
				ll left = 0;
				for (ll j = 0; j < k; j++) {
					if (S >> j & 1) left = j;
				}
				ll nS = S - (1 << left);
				nS <<= 1;
				dp[i + 1][nS] += dp[i][S];
			}
		}
	}
	mint res = dp[n * 2][0];
	//横にばーってしてから横にばー
	if (n == k) res += 1;
	cout << res.x << endl;
	return 0;
}


Measured memory_bytes: 7924
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    ArrayList[] list = new ArrayList[n];
    for(int i = 0; i < n; i++) {
      list[i] = new ArrayList<Integer>();
    }
    for(int i = 0; i < m; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      list[a].add(b);
      list[b].add(a);
    }
    int[] ans = new int[n];
    for(int i = 0; i < n; i++) {
      ans[i] = -1;
    }
    LinkedList<Integer> que = new LinkedList<Integer>();
    que.add(0);
    while(que.size() > 0) {
      int v = que.poll();
      ArrayList<Integer> e = list[v];
      for(int i = 0; i < e.size(); i++) {
        int c = e.get(i);
        if((ans[c] == -1) && (c > 0)) {
          ans[c] = v;
          que.add(c);
        }
      }
    }
    System.out.println("Yes");
    for(int i = 1; i < n; i++) {
      System.out.println(ans[i] + 1);
    }
  }
}

Measured memory_bytes: 74772
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

template<int mod>
struct ModInt{
    int x;

    ModInt() : x(0) {}
    
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    
    ModInt &operator+=(const ModInt &p){
        if((x += p.x) >= mod)   x -= mod;
        return *this;
    }
    
    ModInt &operator-=(const ModInt &p){
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p){
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p){
        *this *= p.inverse();
        return *this;
    }
    
    ModInt operator-() const {return ModInt(-x);}

    ModInt operator+(const ModInt &p) const {return ModInt(*this) += p;}

    ModInt operator-(const ModInt &p) const {return ModInt(*this) -= p;}

    ModInt operator*(const ModInt &p) const {return ModInt(*this) *= p;}

    ModInt operator/(const ModInt &p) const {return ModInt(*this) /= p;}

    bool operator==(const ModInt &p) const {return x == p.x;}

    bool operator!=(const ModInt &p) const {return x != p.x;}

    ModInt inverse() const{
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const{
        ModInt ret(1), mul(x);
        while(n > 0){
            if(n & 1)   ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a){
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() {return mod;}
};

using modint = ModInt<mod>;

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

    string s;
    cin >> s;
    int n = s.length();
    vector<vector<modint>> dp(n + 1, vector<modint>(2, 0));
    dp[0][1] = 1;
    for(int i = 0; i < n; ++i){
        if(dp[i][1] != 0){
            if(s[i] == '1'){
                dp[i + 1][1] += dp[i][1] * 2;
                dp[i + 1][0] += dp[i][1];
            }
            else{
                dp[i + 1][1] += dp[i][1];
            }
        }
        if(dp[i][0] != 0){
            dp[i + 1][0] += dp[i][0] * 3;
        }
    }
    modint ans = dp[n][0] + dp[n][1];
    cout << ans << endl;
}

Measured memory_bytes: 5840
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する


int main() {
    ll v[4], n;
    ll a[4] = {1, 2, 4, 8};
    bool use[4] = {true, true, true, true};
    REP(i, 0, 4) {
        cin >> v[i];
        v[i] *= 4;
    }
    cin >> n;
    n *= 4;
    ll ans = 0;

    for (int i = 3; i >= 1; i--) {
        for (int j = 0; j < i; j++){
            if(v[i] * a[j] > v[j] * a[i]){
                use[i] = false;
            }
        }
    }


    for (int i = 3; i >= 0; i--) {
//        if (i > 0 && v[i] > v[i - 1] * 2) {
//            continue;
//        }
//        if (n < a[i]) continue;
        if(!use[i]) continue;
        ans += (n / a[i]) * v[i];
        n %= a[i];
    }
    ans /= 4;
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
S=input()

ans=0
i=0
l=r=0
while i<len(S) and S[i]=='>':
  l+=1
  i+=1
ans+=l*(l+1)//2
while i<len(S):
  l=r=0
  while i<len(S) and S[i]=='<':
    l+=1
    i+=1
  while i<len(S) and S[i]=='>':
    r+=1
    i+=1
  mx,mn=max(l,r),min(l,r)
  ans+=mx*(mx+1)//2
  ans+=mn*(mn-1)//2
print(ans)
    

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

int main(){
  int n, ans=0;
  cin >> n;
  vector<long long> h(n);
  vector<int> a(n);
  for(int i=0; i<n; i++){
    cin >> h[i];
    a[i] = 0;
  }

  for(int i=0; i<n-1; i++){
    if(h[i]>=h[i+1]){
      a[i+1] = a[i] + 1;
    }
  }

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

  cout << a[n-1] << endl;

  return 0;
}


Measured memory_bytes: 1408
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <functional>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi   vector<int> 
#define   co(x)  cout << x << '\n' 
#define   dbg(x)  cerr << #x << " = " << x << '\n' 
#define   bitcount(x)  (int)__builtin_popcount(x) 
#define   sz(x)  (int)x.size()
#define   all(a) a.begin(),a.end() 
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std; 


inline void solve(){
    int  n, m, inf = 1000000 ; 
    cin >> n >> m ; 
    vi g[100005];
    for (int i=0;i<m;i++){
    	int a,b; cin >> a >> b ; 
    	g[a]. pb(b) ; 
    	g[b]. pb(a) ; 
    }
    int  r = inf , cur, ans = 0 ; 
    for (int i=1;i<n;i++){
	    for (auto it: g[i]){ 
	    	if (it>i)  
	    		r = min(r,it); 
	    }
	    if (r - i == 1) { 
	    	ans++; 
	    	r = inf ; 
	    }
    }
    co (ans) ; 
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 9480
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;

int main() {
    int N;
    cin >> N;
    map<int, int> mp;
    for(int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        mp[a]++;
    }
    ll ans = 0;
    for(auto i : mp) {
        if(i.first > i.second)
            ans += i.second;
        else
            ans += i.second - i.first;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4736
#include <stdio.h>
 
main(){

  int i,j,k=0,n;
 
  scanf("%d",&n);
 
  short int A[n+1];
  short int B[n+1];
 
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    if(k<A[i])k=A[i];
  }
   
  int C[k+1];
 
  
  for(i=0;i<=k;i++){
    C[i]=0;
  }
  for(j=1;j<=n;j++){
    C[A[j]]=C[A[j]]+1;
  }
 
  for(i=1;i<=k;i++){
    C[i]=C[i]+C[i-1];
  }
   
  for(j=n;j>=1;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]=C[A[j]]-1;       
  }

  for(i=1;i<=n;i++){
    if(i==1) printf("%d",B[i]);
    else printf(" %d",B[i]);
  }

  printf("\n");
  return 0;
   
   
}
 

 

 



 

Measured memory_bytes: 8456
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 998244353
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll n, ans=0;
	
	cin>>n;

	vll a(n);

	rep(i, n){
		cin>>a[i];
		while(a[i]>0){
			if(a[i]%2) break;
			a[i]/=2;
			ans++;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 384
s = []
t = []
N = int(input())
for _ in range(N):
  s.append(str(input()))
M = int(input())
for _ in range(M):
  t.append(str(input()))

from collections import Counter
sc = Counter(s)
tc = Counter(t)
s_keys, s_values = zip(*sc.most_common())
t_keys, t_values = zip(*tc.most_common())
ans = 0
for i in range(len(s_values)):
  for j in range(len(t_values)):
    minus = 0
    if s_keys[i] == t_keys[j]:
      minus = t_values[j]
      ans = max(ans, s_values[i] - minus)
    if s_keys[i] not in t_keys:
      ans = max(ans, s_values[i])
print(ans)

Measured memory_bytes: 3316
def _gcd(a, b)
  if a > b
    return a if b == 0

    _gcd(b, a % b)
  else
    return b if a == 0

    _gcd(a, b % a)
  end
end

def gcd(numbers)
  ans = numbers.first

  numbers[1..-1].each do |n|
    ans = _gcd(ans, n)
  end

  return ans
end

N = gets.to_i
A = gets.split.map(&:to_i).sort

p gcd(A)


Measured memory_bytes: 10104
import sys
input=sys.stdin.readline

def main():
    k,q=map(int,input().split())
    D=tuple(map(int,input().split()))
    for _ in range(q):
        n,x,m=map(int,input().split())
        x%=m
        Di=[]
        zero=0
        for d in D:
            tmp=d%m
            if tmp==0:
                zero+=1
            Di.append(tmp)
        s=sum(Di)
        cycles=(n-1)//k
        cycle_sum=cycles*s
        remain=(n-1)%k
        #print(remain)
        last=x+cycle_sum
        for i in range(remain):
            last+=Di[i]
        #print(last)
        q=n-1
        q-=zero*cycles
        for i in range(remain):
            if Di[i]==0:
                q-=1
        q-=last//m
        print(q)
    
if __name__=='__main__':
    main()

Measured memory_bytes: 55772
/***************************************** START OF TEMPLATE *********************************************/

#include<bits/stdc++.h>

using namespace std;

#define  SPEED          ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  foo(i,a,n)     for(ll i = (a); i <= n; i++)
#define  frr(i,a,n)     for(ll i = (a); i >= n; i--)
#define  fo(i,n)        for(ll i = 0; i < n; i++)
#define  all(x)         (x).begin(),(x).end()
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  newl           cout<<"\n"
#define  f              first
#define  s              second
#define  pb             push_back
#define  INPa(a,n)      foo(i,1,n) cin>>a[i];
#define  deb2d(a,n,m)   foo(i,1,n){foo(j,1,m){cout<<a[i][j]<<" ";}newl;}    
#define  deb1d(a,n)     foo(i,1,n)cout<<a[i]<<" ";newl;
#define  debv(a)        for(auto it: a)cout<<it<<" ";newl;
#define  deb1(a)        cout<<a<<" ";newl;
#define  deb2(a,b)      cout<<a<<" "<<b<<" ";newl;
#define  deb3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<" ";newl;
#define  deb4(a,b,c,d)  cout<<a<<" "<<b<<" "<<c<<" "<<d;newl;
#define  ll             long long
#define  ld             long double
#define  pll            pair<ll,ll>
#define  vll            vector<ll>
#define  vpll           vector<pll>

const ll   MOD   =  1e+9+7;
const ll   INF   =  LLONG_MAX;
const int  INFi  =  INT_MAX;
const ll   N     =  2e+5+8;

vll adj[N]; ll vis[N];
ll dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

ll test_cases = 1; randomINIT;

/*********************************************************************************************************/
/***************************************** VARIABLE DECLARATIONS *****************************************/
ll a[N];


/***************************************** FUNCTION IMPLEMENTATIONS **************************************/
ll fast_pow(ll x, ll y, ll MOD=MOD){
    ll res=1;
    while(y){
        if(y&1)res=(res*x)%MOD;
        y>>=1;x=(x*x)%MOD;
    }
    return res;
}

ll mod_inverse(ll x, ll MOD=MOD){
    return fast_pow(x,MOD-2,MOD);
}

ll mi2 = mod_inverse(2);
ll sum_till(ll n){
    return n*(n+1)%MOD * mi2%MOD;
}
/***************************************** START OF MAIN FUNCTION ****************************************/
void MAIN(ll tc){
    ll res = 0;
    ll n,p;
    cin>>n>>p;
    foo(k,p,n+1){
        ll st = sum_till(k-1);
        ll en = (sum_till(n) - sum_till(n-k)+ MOD)%MOD;
        //deb3(k,st,en);
        res = (res + (en - st + 1 + MOD)%MOD)%MOD;
    }

    cout<<res;    
}

int main(){
    SPEED;

    //cin>>test_cases;
    foo(i,1,test_cases){
        MAIN(i);
    }
}

Measured memory_bytes: 8360
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main(){
  int n,d;
  cin>>n>>d;
  d=d*2+1;
  cout<<(n+d-1)/d<<endl;
  return(0);
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if (a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}


Measured memory_bytes: 26216
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

string create_code(string s) {
	string str;
	int num = 0;
	str.push_back(s[num]);
	while (num < s.size()) {
		if (s[num] == 'a' || s[num] == 'i' || s[num] == 'u' || s[num] == 'e' || s[num] == 'o') {
			if(num+1 < s.size()) str.push_back(s[num + 1]);
		}
		num++;
	}

	return str;
}

int main()
{
	int n;
	while (cin >> n, n) {
		set<string> code;
		REP(i, 0, n) {
			string s;
			cin >> s;
			code.insert(create_code(s));
		}

		if ((int)code.size() != n) cout << -1 << endl;
		else {
			int k = 1, max_v=0;
			bool flag = false;
			set<string>::iterator itr = code.begin();
			while(itr!=code.end()){
				string codes = *itr;
				int size = codes.size();
				max_v = max(max_v, size);
				itr++;
			}

			while (k <= max_v) {
				set<string> air_code;
				set<string>::iterator itr = code.begin();
				REP(i, 0, n) {
					string ncode = *itr;
					air_code.insert(ncode.substr(0, k));
					itr++;
				}
				if ((int)air_code.size() == n) {
					cout << k << endl;
					flag = true;
					break;
				}

				k++;
			}

			if(!flag) cout << k << endl;
		}
	}

    return 0;
}

Measured memory_bytes: 3100
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include <numeric>
using namespace std;
int main(void) {
	char A[55][55];
	char B[55][55];
	int h,i,j,k,ok,N, M;
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++) {
		scanf(" %s", &A[i]);
	}
	for (i = 0; i < M; i++) {
		scanf(" %s", &B[i]);
	}

	for (h = 0; h <= N - M; h++) {
		for (i = 0; i <= N - M; i++) {
			ok = 1;
			for (j = 0; j < M; j++) {
				for (k = 0; k < M; k++) {
					if (A[h + j][i + k] != B[j][k]) {
						ok = 0; break;
					}
				}
				if (ok == 0) { break; }
			}
			if (ok == 1) { printf("Yes\n"); return 0; }
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
//============================================================================
// Name        : a2a.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	vector<int> a(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(a.rbegin(), a.rend());

	cout << a[0] * 10 + a[1] + a[2] << endl;
}


Measured memory_bytes: 256
use proconio::input;


fn solve(_: i32, x: i32, l: Vec::<i32>) {
    let mut ans: i32 = 1;
    let mut cur: i32 = 0;

    for li in l {
        if cur + li <= x {
            ans += 1;
        }
        cur += li;
    }

    println!("{}", ans);
}


fn main() {
    input! {
        n: i32,
        x: i32,
        l: [i32; n],
    }

    solve(n, x, l);
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

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

int64 SolveCase() {
  int64 n, a, b, c, d;
  cin >> n >> a >> b >> c >> d;

  unordered_map<int64, int64> cache;
  cache[0] = 0;
  cache[1] = d;
  function<int64(int64)> solve_fn = [&](int64 x) -> int64 {
    if (cache.find(x) != cache.end()) {
      return cache[x];
    }

    int64 min = INT64_MAX;
    if (x <= INT64_MAX / d) {
      UpdateMin(min, x * d);
    }
   
    for (const auto [divisor, cost] : vector<tuple<int64, int64>>({{2, a}, {3, b}, {5, c}})) {
      if (x % divisor == 0) {
        UpdateMin(min, solve_fn(x / divisor) + cost);
      }
      int64 r = x % divisor;
      UpdateMin(min, solve_fn(x / divisor) + cost + r * d);
      if (x / divisor + 1 < x) {
        UpdateMin(min, solve_fn(x / divisor + 1) + cost + (divisor - r) * d);
      }
    }

    cache[x] = min;
    return min;
  };
  return solve_fn(n);
}

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

  int num_cases;
  cin >> num_cases;
  for (int i = 0; i < num_cases; i++) {
    cout << SolveCase() << endl;
  }
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main(){
  ll n, c, k; 
  cin >> n >> c >> k;
  ll t[n];
  for(ll i = 0; i < n; i++) cin >> t[i];
  sort(t, t + n);
  ll ans = 0, num = 1, s = t[0];
  for(ll i = 1; i < n; i++){
    if(t[i] > s + k || num == c){
      num = 0;
      ans++;
      s = t[i];
    }
    num++;
  }
  cout << ++ans << endl;
  return 0;
}

Measured memory_bytes: 1024
import collections
n=int(input())
l=[list(input()) for i in range(n)]
for i in range(n):
  l[i].sort()
  l[i]=''.join(l[i])
l=collections.Counter(l)
m=list(l.values())
ct=0
for i in range(len(m)):
  ct+=int(m[i]*(m[i]-1)//2)
print(ct)

Measured memory_bytes: 30612
#include <cstdio>
#include <algorithm>

using namespace std;

using ll=long long int;

const int MAXN=1e5+3;
const int MOD=1e9+7;

int N,K;
ll A[MAXN];
ll Ck[MAXN];

ll fast_power(ll base,int exp){
    if (exp==0) return 1ll;
    auto temp=fast_power(base,exp/2);
    if (exp%2) return ((temp*temp)%MOD)*base%MOD;
    else return (temp*temp)%MOD;
}

ll inverse(ll a){ return fast_power(a,MOD-2);};

void build(){
    ll denom=1,nom;
    for(int i=2;i<K;i++) denom=denom*i%MOD;
    nom=denom;
    denom=inverse(denom);

    for(int i=K-1;i<=N-1;i++){
        Ck[i]=nom*denom%MOD;

        nom=nom*(i+1)%MOD;
        nom=nom*inverse(i-K+2)%MOD;
    }
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%lld",A+i);
    sort(A,A+N);

    build();

    ll ans=0;
    for(int i=0;i<N;i++){
        auto cur=A[i];
        auto large=i,small=N-1-i;
        ans=(ans+(Ck[large]*cur)%MOD)%MOD;
        ans=(ans+(MOD-Ck[small]*cur))%MOD;
    }

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

    return 0;
}

Measured memory_bytes: 2828
<?php
$n = int();
for($i = 0; $i < $n; $i++){
    list($x, $l) = ints();
    $a[] = $x-$l;
    $b[] = $x+$l;
}
$max = - 10**10;
$count = 0;
array_multisort($b, $a);
for($i = 0; $i < $n; $i++){
    if($a[$i] >= $max){
        $count++;
        $max = $b[$i];
    }
}
echo $count;


function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

Measured memory_bytes: 22260
#include <vector>
#include <iostream>

using namespace std;

int main()
{
	int n, c;
	
	while (true)
	{
		scanf("%d", &n);

		if (n == 0) { break; }

		vector<pair<int, int> > r; // (color, number)

		for (int i = 0; i < n; i++)
		{
			scanf("%d", &c);

			if (i == 0)
			{
				r.push_back(make_pair(c, 1));
			}
			else if (i % 2 == 0)
			{
				if (r.back().first == c)
				{
					r.back().second++;
				}
				else
				{
					r.push_back(make_pair(c, 1));
				}
			}
			else
			{
				if (r.back().first == c)
				{
					r.back().second++;
				}
				else
				{
					int prevc = r.back().first;
					int prevn = r.back().second; r.pop_back();

					if (!r.empty())
					{
						r.back().second += prevn + 1;
					}
					else
					{
						r.push_back(make_pair(c, prevn + 1));
					}
				}
			}
		}

		int ret = 0;

		for (int i = 0; i < r.size(); i++)
		{
			if (r[i].first == 0)
			{
				ret += r[i].second;
			}
		}

		printf("%d\n", ret);
	}

	return 0;
}

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

long long solve(int n, int* h, int k)
{
  long long dp[n];
  dp[0] = 0;
  for (int i = 1; i < n; i++)
  {
    dp[i] = INT_MAX;
    for (int j = 1; j <= k && i-j >= 0; j++)
    {
      dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]));
    }
  }
  return dp[n-1];
}

int main()
{
  int n, k;
  cin >> n;
  cin >> k;
  int h[n];
  for (int i=0; i<n; i++)
  {
    cin >> h[i];
  }
  long long r = solve(n, h, k);
  cout << r << endl;
}


Measured memory_bytes: 4328
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

n = lines[0][0]
m = lines[0][1]
x = lines[0][2]
A = 1000000000

skill = []

min_cost = A
for i in (2 ** n)..(2 ** (n+1) - 1) do
  for k in 1..m do
    skill[k-1] = 0
  end
  current_cost = 0
  nishin = i.to_s(2)
  for j in 1..n do
    if nishin[j] == "1" then
      for k in 1..m do
        skill[k-1] += lines[j][k]
      end
      current_cost += lines[j][0]
    end
  end
  achieved = true
  for k in 1..m do
    if skill[k-1] < x then
      achieved = false
      break
    end
  end
  if achieved == true and current_cost < min_cost then
    min_cost = current_cost
  end
end
    
if min_cost == A then
  print -1
else
  print min_cost
end

Measured memory_bytes: 14384
// DSL_5_A Maximum Number of Customers
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct event {
  int t;
  int n;
  bool operator<(const event &e) const { return t < e.t; }
};

int main() {
  int n, t;
  cin >> n >> t;
  vector<event> ev;
  for (int i = 0; i < n; ++i) {
    cin >> t;
    ev.push_back({t, 1});
    cin >> t;
    ev.push_back({t, -1});
  }
  sort(ev.begin(), ev.end());
  int t0 = ev[0].t;
  int curr = 0;
  int M = 0;
  for (auto it = ev.begin(); it != ev.end();) {
    while (it != ev.end() and it->t == t0) {
      curr += it->n;
      ++it;
    }
    M = max(M, curr);
    t0 = it->t;
  }
  cout << M << endl;
}


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

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	gcd(y, x%y);
}

int main() {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	a--;
	ll g = gcd(c, d);
	ll lcm = c * d / g;
	ll div_c = b / c - a / c;
	ll div_d = b / d - a / d;
	ll div_lcm = b / lcm - a / lcm;
	ll div_c_d = div_c + div_d - div_lcm;
	ll ans = b - a - div_c_d;
	cout << ans;
}

Measured memory_bytes: 256
using System;

namespace Atcoder
{
    class Program
        //    ABC127 C - Prison
    {
        private static void Main(string[] args)
        {
            var nm = Console.ReadLine().Split(' ');
            var n = int.Parse(nm[0]);
            var m = int.Parse(nm[1]);

            var ans = 0;

            var lr = Console.ReadLine().Split(' ');
            var l = int.Parse(lr[0]);
            var r = int.Parse(lr[1]);

            for (var i = 1; i < m; i++)
            {
                lr = Console.ReadLine().Split(' ');
                var l2 = int.Parse(lr[0]);
                var r2 = int.Parse(lr[1]);

                if (l2 > r || r2 < l || l > r)
                {
                    ans = -1;
                    break;
                }

                if (l2 > l)
                {
                    l = l2;
                }
                if (r2 < r)
                {
                    r = r2;
                }
            }
            ans = ans < 0 ? 0 : r - l + 1;
            Console.WriteLine(Math.Min(ans,n));
        }
    }
}



Measured memory_bytes: 15292
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n)             for(int i = 0; i < n; i ++)
#define forn1(i, n)            for(int i = 1; i <= n; i ++)
#define pb push_back
#define ll long long int
#define fi first
#define se second
#define ii  pair<long long int, long long int>
#define vi  vector <long long int>
#define vii vector <pair <long long int, long long int > >
#define all(cont)  cont.begin(), cont.end()
#define EPS 1e-9
#define MOD 1000000007
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define range 200010
#pragma GCC optimize ("Ofast")
#define endl '\n'
signed main(){

 //   freopen("test.txt","r",stdin);
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll A,B;
    cin>>A>>B;
    ll x = __gcd(A,B);
    int flag=0;
    if(x==1||x==2){
        cout<<x<<endl;
        return 0;
    }
    ll ans=1;
    while(x%2==0){
        if(!flag){
            ans++;
            flag=1;
        }
        x/=2;
    }
    for(int i=3;i<=sqrt(x);i+=2){
        flag=0;
        while(x%i==0){
            if(!flag){
                ans++;
                flag=1;
            }
            x/=i;
        }
    }
    if(x>2)ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,m,q,ans[N];
vector<int>v[N];
bool f[N]; int mindis[N];
int d[N],b[N],c[N];
inline void dfs(int color,int now,int far)
{
	if(far<=mindis[now])return;
	mindis[now]=far;
	if(!ans[now])ans[now]=color;
	for(int i=0;i<v[now].size();i++)
	{
		dfs(color,v[now][i],far-1);
	}
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)mindis[i]=-1;
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	cin>>q;
	for(int i=0;i<q;i++)
		cin>>b[i]>>d[i]>>c[i];
	for(int i=q-1;i>=0;i--)
	{
		dfs(c[i],b[i],d[i]);
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
}
/*
7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2
************
14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3
*/

Measured memory_bytes: 8440
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define llint long long
#define mod 998244353
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

struct edge{
	llint to, cost;
	edge();
	edge(llint a, llint b)
	{
		to = a, cost = b;
	}
};

llint n, m;
vector<edge> G[1<<18];
llint dist[1<<18];
int S = 1<<17;

void add(int a, int b, int k, int l, int r, llint s, llint c)
{
	if(b < l || r < a) return;
	if(a <= l && r <= b){
		G[S+s].push_back(edge(k, c));
		return;
	}
	add(a, b, k*2, l, (l+r)/2, s, c);
	add(a, b, k*2+1, (l+r)/2+1, r, s, c);
}
void add(llint a, llint b, llint s, llint c)
{
	add(a, b, 1, 0, (1<<17)-1, s, c);
}

void dijkstra()
{
	for(int i = 1; i < (1<<18); i++) dist[i] = inf;
	dist[S+1] = 0;
	
	priority_queue< P, vector<P>, greater<P> > Q;
	Q.push( make_pair(0, S+1) );
	
	llint v, d;
	while(Q.size()){
		d = Q.top().first;
		v = Q.top().second;
		//cout << v << endl;
		Q.pop();
		if(dist[v] < d) continue;
		for(int i = 0; i < G[v].size(); i++){
			if(dist[G[v][i].to] > d + G[v][i].cost){
				dist[G[v][i].to] = d + G[v][i].cost;
				Q.push( make_pair(dist[G[v][i].to], G[v][i].to) );
			}
		}
	}
}


int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	llint l, r, c;
	for(int i = 1; i < S; i++){
		G[i].push_back(edge(i*2, 0));
		G[i].push_back(edge(i*2+1, 0));
	}
	
	for(int i = 1; i <= m; i++){
		cin >> l >> r >> c;
		add(l, r, l, c);
	}
	
	dijkstra();
	if(dist[S+n] >= inf/2) cout << -1 << endl;
	else cout << dist[S+n] << endl;
	
	return 0;
}

Measured memory_bytes: 50936
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


def solve(N, A):
    # 1/1 + 1/2 + 1/3 + ... + 1/Nの累積和を求めておく
    inv_sum = [0]
    for i in range(N):
        inv_sum.append((inv_sum[-1] + pow_mod(i + 1, MOD - 2)) % MOD)
    del inv_sum[0]

    # 各iについて、Σ(j=1, N) 1/(|j - i| + 1)を求めて、
    # それらを係数としてA[i]に掛け、加算する
    ans = 0
    for i in range(N):
        ans += + A[i] * (inv_sum[N - 1 - i] + inv_sum[i] - 1)
        ans %= MOD

    # ansにN!を掛ける
    for i in range(N):
        ans *= (i + 1)
        ans %= MOD
    return ans


N = int(input())
A = inpl()
print(solve(N, A))


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

#define M_PI acos(-1.0)
#define basicR 1.0

int main()
{
	int printOutput;
	long inputS;
	double firstArea, secondArea, differenceValue;
	scanf("%ld", &inputS);

	
	firstArea = M_PI * pow(basicR, 2);
	secondArea = M_PI * pow(inputS, 2);
	differenceValue = secondArea / firstArea;

	printf("%d \n", (int)round(differenceValue));

	return 0;
}


Measured memory_bytes: 128
package main

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

type TupleInt struct {
	val int
	num int
}

func main() {
	sc := NewScanner()
	N, M := sc.NextInt(), sc.NextInt()
	ls := make(SortInterFace, N)

	for i := 0; i < N; i++ {
		ls[i] = TupleInt{sc.NextInt(), sc.NextInt()}
	}

	sort.Sort(ls)

	sum := 0
	ans := 0
	for i := 0; i < N; i++ {
		k := max(0, min(M-sum, ls[i].num))
		sum += k
		ans += k * ls[i].val
	}

	fmt.Println(ans)
}

func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

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

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

type SortInterFace []TupleInt

func (s SortInterFace) Len() int {
	return len(s)
}

// <: up, >: down
func (s SortInterFace) Less(i, j int) bool {
	return s[i].val < s[j].val
}
func (s SortInterFace) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}

func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}

func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

//#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD = 1e9 + 7;

signed main() {
	for (int N, K; cin >> N >> K;) {
		int ans = 1;
		ans *= K;
		rep(i, 1, N)ans *= K - 1;
		cout << ans << endl;
	}

	return 0;
}

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

signed main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  static int c[3];
  for (int i = 0, t; i < N; ++i) {
    cin >> t;
    ++c[t - 1];
  }

  static double dp[301][301][301];
  /*function<double(int, int, int)> dfs = [&](int a, int b, int c) {
    if (a + b + c == 0) return 0.0;
    if (vis[a][b][c]) return dp[a][b][c];
    vis[a][b][c] = 1;
    if (a) dp[a][b][c] += (dfs(a - 1, b + 1, c) + 1) * a / N;
    if (b) dp[a][b][c] += (dfs(a, b - 1, c + 1) + 1) * b / N;
    if (c) dp[a][b][c] += (dfs(a, b, c - 1) + 1) * c / N;
    int d = N - a - b - c;
    // if (d) dp[a][b][c] += (dfs(a, b, c) + 1) * d / N;
    return dp[a][b][c] = (dp[a][b][c] + 1.0 * d / N) * N / (N - d);
  };*/
  for (int i = 0; i < c[2] + 1; ++i) {
    for (int j = 0; j < c[1] + c[2] + 1; ++j) {
      for (int k = 0; k < c[0] + c[1] + c[2] + 1; ++k) {
        if (i + j + k == 0) continue;
        if (i) dp[i][j][k] += (dp[i - 1][j + 1][k] + 1) * i / N;
        if (j) dp[i][j][k] += (dp[i][j - 1][k + 1] + 1) * j / N;
        if (k) dp[i][j][k] += (dp[i][j][k - 1]     + 1) * k / N;
        int l = N - i - j - k;
        dp[i][j][k] = (dp[i][j][k] + 1.0 * l / N) * N / (N - l);
      }
    }
  }

  cout << fixed << setprecision(9) << dp[c[2]][c[1]][c[0]] << endl;

  return 0;
}


Measured memory_bytes: 213376
#include <iostream>
#include <cstdlib>
#include <iostream>
#include <string>
#include <typeinfo>

#define REP(i,n) for(int i=0; i<n; i++)
#define debug(x) cerr << #x << " = " << (x) << endl;


using namespace std;

string eq[50];
int n, j;


int calc(int l, int po){
	//printf("calc(%d, %d)\n",l, j);
	int ans, num;
	bool op;
	char c;
	
	j = po;
	
	if (eq[j][l]=='+') op = true;
	else op = false;
	
	ans = op ? 0 : 1;
	
	j++;
	while(1){
		if (eq[j].length()<=l+1 || j>=n){
			j--;
			break;
		}
		c = eq[j][eq[j].length()-1];
		if (c=='+' || c=='*'){
			num = calc(l+1, j);
		}else{
			num = c-'0';
		}
		ans = op ? ans+num : ans*num;
		//debug(j);
		//debug(ans);
		j++;
	}
	//printf("calc(%d, %d) = %d\n", l, po, ans);
	return ans;
}

int main(){
	while(1){
		//cout << "-------" << endl;
		j = 0;
		cin >> n;
		if (n==0) break;
		REP(i,n){
			cin >> eq[i];
		}
		if (n<=1){
			cout << eq[0] << endl;
			continue;
		}
		cout << calc(0,0) << endl;
	}
	return 0;
}




Measured memory_bytes: 3048
def have_AC(str):
    count=[0]
    for i in range(1,len(str)):
        if(str[i]=='C' and str[i-1]=='A'):
            count.append(count[i-1]+1)
            continue
        count.append(count[i-1])
    return count

n,q=input().split() #nは文字の長さ　qは質問数
s=input() #Sは文字列
n=int(n)
q=int(q)
num=[]
d=have_AC(s)

for i in range(q):
    a,b=input().split()
    a=int(a)
    b=int(b)
    num.append(d[b-1]-d[a-1])

for j in range(len(num)):
    print(num[j])

Measured memory_bytes: 10304
#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() {
    string n;
    cin >> n;
    if(n.at(0)=='9'||n.at(1)=='9') cout << "Yes" << endl;
    else cout << "No" << endl;
    
}

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

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
    const int N=100;

    char a[N];
    char s[N];

    cin>>a;
    int l = strlen(a)-1;
    for(int i = 0; i < l+1; i++){
        s[l-i] = a[i];
    }

    int c=0;
  if(l%2!=0){
    for(int i = 0; i <= l/2; i++){
        if(s[i] != a[i])c++;
      //cout<<s[i]<<" "<<a[i]<<endl;
    }
  } else{
    for(int i = 0; i <= l/2 -1; i++){
      if(s[i] != a[i])c++;
      //cout<<s[i]<<" "<<a[i]<<endl;
    }
  }

    cout<<c;

    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#define REP(i,n) for(int i = 0; i < (int)n; i++)
using namespace std;

int main(){
  int x,a,b;
  cin >> x >> a >> b;
  string ans;
  if(abs(x-a)<abs(x-b)){
    ans = "A";
  }else{
    ans = "B";
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int p[10];
int c[10];

int main()
{
    int D, G;
    cin >> D >> G;

    for (int i = 0; i < D; i++)
    {
        cin >> p[i] >> c[i];
    }

    int result = 1001;
    for (int f = 0; f < (1 << D); f++)
    {
        int cnt = 0;
        int score = 0;
        for (int i = 0; i < D; i++)
        {
            if (((f >> i) & 1) != 0)
            {
                int point = 100 * (i + 1);
                cnt += p[i];
                score += c[i] + p[i] * point;
            }
        }

        for (int i = D - 1; i >= 0; i--)
        {
            if (((f >> i) & 1) == 0)
            {
                int point = 100 * (i + 1);
                int req = max(0, G - score);

                int d = min(p[i] - 1, (req + point - 1) / point);
                cnt += d;
                score += d * point;
            }
        }

        if (G <= score)
        {
            result = min(result, cnt);
        }
    }

    cout << result << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

int rec(int x) {
    if (x == 1) return 1;
    return 1 + 2 * rec(x / 2);
}

void _main() {
    int N;
    cin >> N;
    cout << rec(N) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
  int A, B, C;
  std::cin >> A >> B >> C;

  bool can = false;

  for ( int i = 1; i <= B; i++ ) {
    int r = i * A % B;
    if ( r == C ) {
      can = true;
      break;
    }
  }
  std::cout << (can ? "YES" : "NO") << std::endl;
  return 0;
}


Measured memory_bytes: 256