akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
	int h, w;
	char ch;
	int num[26];
	cin >> h >> w;
	for(int i = 0; i < 26; i++) num[i] = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> ch;
			num[ch - 'a']++;
		}
	}
	int cnt4 = 0, cnt2 = 0, cnt1 = 0;
	for(int i = 0; i < 26; i++){
		while(num[i] >= 4){
			cnt4++;
			num[i] -= 4;
		}
		while(num[i] >= 2){
			cnt2++;
			num[i] -= 2;
		}
		if(num[i] == 1) cnt1++;
	}
	if(w % 2 == 0 && h % 2 == 0){
		if(cnt4 * 4 == w * h){
			printf("Yes\n");
			return 0;
		}else{
			printf("No\n");
			return 0;
		}
	}else if(w % 2 != 0 && h % 2 != 0){
		cnt4 -= (w - 1) * (h - 1) / 4;
		if(cnt4 < 0){
			printf("No\n");
			return 0;
		}
		cnt2 += cnt4 * 2;
		if(cnt2 == (w + h - 1) / 2 && cnt1 == 1){
			printf("Yes\n");
			return 0;
		}else{
			printf("No\n");
			return 0;
		}
	}else if(w % 2 == 0){
		cnt4 -= w * (h - 1) / 4;
		if(cnt4 < 0){
			printf("No\n");
			return 0;
		}
		cnt2 += cnt4 * 2;
		if(cnt2 == w / 2){
			printf("Yes\n");
			return 0;
		}else{
			printf("No\n");
			return 0;
		}
	}else if(h % 2 == 0){
		cnt4 -= (w - 1) * h / 4;
		if(cnt4 < 0){
			printf("No\n");
			return 0;
		}
		cnt2 += cnt4 * 2;
		if(cnt2 == h / 2){
			printf("Yes\n");
			return 0;
		}else{
			printf("No\n");
		}
	}
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]

ans = 1
L = [0]*(N+2)
for i in range(N+1):
    L[i+1] = L[i]+A[i]

v = 1
for i in range(1, N+1):
    v = min(2*v, L[-1]-L[i])
    ans += v
    v -= A[i]
    if v < 0:
        ans = -1
        break
if A[0] > 0:
    ans = -1
    if N == 0 and A[0] == 1:
        ans = 1

print(ans)

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

/*
N以下の整数で、iで始まってjで終わる数を配列に入れていく。
G[i][j]とG[j][i]から一つずつ取った組み合わせなので
G[i][j]*G[j][i]の総和を求めれば良い！！！！

最初は、最初の数と最後の数だけ求めて
あとは全探索にしようと思ったけど
最初からN以下で数えていけばいい、そこがポイント！
*/

int digit(int N)
{
  int count=0;
  while (N>0)
  {
    N/=10;
    count++;
  }
  return (count);
}

int main()
{
  int N;cin>>N;
  int d = digit(N);
  
  int G[10][10];
  for (int i=0;i<=9;i++)
  {
    for (int j=0;j<=9;j++)
      G[i][j]=0; 
  }
  
  for (int i=1;i<=N;i++)
  {
    int dd = digit(i);
    int head = i/pow(10,dd-1);//最初の数
    int foot = i % 10;//最後の数
    //cout<<i<<" "<<head<<" "<<foot<<endl;
    G[head][foot]++;
  }
  
  int count=0;
  for (int i=0;i<=9;i++)
  {
    for (int j=0;j<=9;j++)
    {
      count += G[i][j]*G[j][i];  
    }
  }
  cout<<count<<endl;  
}

Measured memory_bytes: 256
#pragma target("avx")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define rep(i,b,e) for(ll i=b; i<e; i++)
#define be(vec) vec.begin(),vec.end()
#define print(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define scan(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	ll n, k;
	scanf("%ld %ld", &n, &k);
	double ans = 0;
	rep(i, 1, n+1){
		int x = i;
		double tmp = 1;
		while(x<k){
			x *= 2;
			tmp *= 0.5;
		}
		ans += tmp / (double)n;
	}
	printf("%0.10lf", ans);
	return 0;
}


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

int main()
{
    int N, a, b;
    bool x = true;
    int64_t limit = 0;//締め切り
    int64_t task = 0;//時間
    cin >> N;

    vector<pair<int64_t, int64_t>> list;

    for (int i = 0; i < N; i++)
    {
        cin >> a >> b;
        list.push_back(make_pair(b, a));//締め切り、作業時間
    }

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

    for (int i = 0; i < N; i++)
    {
        task += list.at(i).second;

        if (list.at(i).first < task)
        {
            x = false;
            break;
        }
    }
    if(x)
        cout << "Yes";
    else
        cout << "No";
}


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

using namespace std;

typedef long long ll;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    int k;
    cin >> s >> k;
    for (int i = 0; i < s.size(); i += k)
    {
        cout << s[i];
    }
}


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

#define ll long long
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll mod = 1000000007;
ll INF = 1e9 + 5;

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


Measured memory_bytes: 1792
W,H,N=map(int,input().split())
X=[list(map(int,input().split())) for _ in range(N)]
x1=0
x2=W
y1=0
y2=H
for i in range(N):
    if X[i][2]==1:
        x1=max(x1,X[i][0])
    elif X[i][2]==2:
        x2=min(x2,X[i][0])
    elif X[i][2]==3:
        y1=max(y1,X[i][1])
    else:
        y2=min(y2,X[i][1])
print((y2-y1)*(x2-x1) if (y2-y1)>0 and (x2-x1)>0 else 0)

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

using namespace std;
int main()
{
    string a;
    cin >> a;
    char b = a[(int)a.length()-1];

    if(b=='3'){
        cout << "bon";
    }
    else if(b=='0'||b=='1'||b=='6'||b=='8'){
        cout << "pon";
    }
    else{
        cout << "hon";
    }
}

Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (int i = (int)(x); i < (int)(n); i++)
#define repfr(i, x, n) for (int i = (int)(x)-1; i >= (int)(n); i--)
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
#define INF 1e9
using ll = int64_t;
#define waru 1000000007

std::int64_t gcd(std::int64_t a, std::int64_t b) {
  // a >= b && b != 0
  std::int64_t c;
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
std::int64_t gcd_s(std::int64_t aa, std::int64_t bb) {
  std::int64_t a = max(aa, bb);
  std::int64_t b = min(aa, bb);
  std::int64_t c;
  if (b == 0) {
    return -1;
  }
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
void rle(std::vector<std::pair<char, std::int64_t>> &data, std::string str) {
  char now = str[0];
  std::int64_t count = 0;
  for (std::int64_t i = 0; i < str.size() + 1; i++) {
    if (i == str.size()) {
      data.push_back(make_pair(str[i - 1], count));
      break;
    } else if (now != str[i]) {
      data.push_back(make_pair(now, count));
      now = str[i];
      count = 0;
    }
    count++;
  }

  return;
}

std::map<ll, ll> m;
void Main() {
  //自動整形防止用コメント
  ll n;
  std::cin >> n;
  std::vector<ll> a(n);
  for (auto &x : a) {
    std::cin >> x;
  }

  //同じ長さの棒が２本以上あること
  //その中で最大の長さの棒を取ること
  priority_queue<ll> q;
  for (auto &x : a) {
    q.push(x);
  }

  ll an[2];
  ll index = 0;
  while (!q.empty()) {
    ll tmp = q.top();
    q.pop();

    if (tmp == q.top() && !q.empty()) {
      an[index] = tmp;
      q.pop();
      index++;
      if (index == 2) {
        std::cout << an[0] * an[1] << '\n';
        return;
      }
    }
  }

  std::cout << 0 << '\n';

  return;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 2168
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)

using namespace std;
typedef long long int ll;

// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
 public:
  int64_t a;

  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
};
// }}}

const ll M = 1e9 + 7;
using mint = modint<M>;
std::vector<ll> fac(3000000, 1), finv(3000000, 1), inv(3000000, 1);

void c4_init(ll m) {
    for (ll i = 2; i < 3000000; i++) {
        fac[i] = fac[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        finv[i] = finv[i - 1] * inv[i] % m;
    }
}

ll c4(ll n, ll k, ll m) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % m) % m;
}

ll N, K;
mint ans(0);
string s;

int main(void) {
  c4_init(M);
  cin >> K >> s;
  N = s.size();
  for (ll j = N-1; j < N + K; j++) {
    ans += mint(c4(j, N-1, M)) * mint(25).pow(j- (N-1)) * mint(26).pow((N+K-1) - j);
  }
  cout << ans.value() << endl;
  return 0;
}


Measured memory_bytes: 75548
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const long long int MOD = 1000000007;
int main() {
    long long int N, ans = 1; cin >> N;
    for (int i = 1; i <= N; ++i)  {
        ans *= i;
        ans = ans % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3568
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;



const int max_comb=200000;
vector<ll> fac(max_comb+1); //n! (mod M)
vector<ll> ifac(max_comb+1); //k!^(-1) (mod M)

ll mpow(ll x, ll n){ //x^n(mod M)
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll minv(ll x){
    return mpow( x, MOD-2 );
}

ll comb(int a, int b){     // C(a,b) = a! * b!^(-1) * (a-b)^(-1)
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

ll perm(int a, int b){     // P(a,b) = a! * (a-b)!^(-1)
    if(b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b] % MOD;
    return tmp * fac[a] % MOD;
}

void pre_comb()
{
    fac[0] = 1;
    ifac[0] = 1;
    for(int i = 0; i<max_comb; i++){
        fac[i+1] = fac[i]*(i+1) % MOD; // n!(mod M)
        ifac[i+1] = ifac[i]*minv(i+1) % MOD; // k!^(-1) (mod M)
    }
    return;
}

int main(int argc, char* argv[])
{
    int h,w,a,b;
    scanf("%d%d%d%d", &h, &w, &a, &b);

    pre_comb();

    ll ans=0;
    int i=0;
    for(i=0; i<w-b; i++) {
        ll ans0 = comb(h-1-a+b+i,b+i) * comb(a-1+w-b-1-i, w-b-1-i) %MOD;
        ans = (ans + ans0)%MOD;
    }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 3328
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const (
	N     = 100
	INFTY = 1 << 21
)

type Graph struct {
	M [N][N]int
	d [N]int
}

func (g *Graph) bfs(s, n int) string {
	var q []int
	q = append(q, s) // push

	for i := 0; i < n; i++ {
		g.d[i] = INFTY
	}
	g.d[s] = 0

	for len(q) != 0 {
		u := q[0]
		q = q[1:] // pop
		for v := 0; v < n; v++ {
			if g.M[u][v] == 0 || g.d[v] != INFTY {
				continue
			}
			g.d[v] = g.d[u] + 1
			q = append(q, v) // push
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		if g.d[i] == INFTY {
			out.WriteString(fmt.Sprintf("%d -1\n", i+1))
			continue
		}
		out.WriteString(fmt.Sprintf("%d %d\n", i+1, g.d[i]))
	}

	return strings.TrimRight(out.String(), "\n")
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	var g Graph
	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		u--
		for j := 0; j < k; j++ {
			sc.Scan()
			v, _ := strconv.Atoi(sc.Text())
			v--
			g.M[u][v] = 1
		}
	}

	return g.bfs(0, n)
}

func main() {
	fmt.Println(answer(os.Stdin))
}



Measured memory_bytes: 1272
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=205,M=3e4,inf=1e8;
int n,m,i,j,S,T;
int et,he[N];
struct edge{int l,to,flow;}e[M];
char get(){
	char c=getchar();
	for (;c!='.'&&c!='o'&&c!='S'&&c!='T';c=getchar());
	return c;
}
void line(int x,int y,int flow){
	e[++et].l=he[x];he[x]=et;
	e[et].to=y;e[et].flow=flow;
}
void add(int x,int y,int flow){
	line(x,y,flow);line(y,x,flow);
}
int h,t,q[N],d[N];
bool build(){
	for (int i=1;i<=T;i++) d[i]=0;
	h=0;q[t=1]=S;d[S]=1;
	while (h!=t) for (int x=q[++h],y,i=he[x];i;i=e[i].l)
		if (e[i].flow&&!d[y=e[i].to]){
			d[y]=d[x]+1,q[++t]=y;if (y==T) return 1;
		}
	return 0;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int rest=flow,use,i,y;
	for (i=he[x];i&&rest;i=e[i].l) if (e[i].flow&&
 		d[y=e[i].to]==d[x]+1&&(use=dfs(y,min(rest,e[i].flow))))
			e[i].flow-=use,e[i^1].flow+=use,rest-=use;
	if (rest==flow) d[x]=0;return flow-rest;
}
int dinic(){
	int res=0;
	while (build()) res+=dfs(S,inf);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);S=n+m+1;T=S+1;et=1;
	for (i=1;i<=n;i++) for (j=1;j<=m;j++){
		char c=get();
		if (c=='o') add(i,j+n,1);
		if (c=='S') line(S,i,inf),et++,line(S,j+n,inf),et++;
		if (c=='T') line(i,T,inf),et++,line(j+n,T,inf),et++;
	}
	int ans=dinic();
	if (ans>=inf) puts("-1"); else printf("%d",ans);
}

Measured memory_bytes: 384
#include <iostream>
#include <queue>
#include <list>
#include <vector>

using namespace std;

#define MIN(x, y) x<y?x:y
#define MAX(x, y) x<y?y:x
#define ABS(x, y) x<y?(y-x):(x-y)

typedef long long Long;

int main()
{
	Long a, b, n;
	Long p, q;
	Long ans=0;

	cin>>a>>b>>n;

	Long x=0;

	if(b<=n) {
		x=b-1;
	} else {
		x=n;
	}

	p = (a*x)/b;
	q = x/b;
	q = q*a;
	ans = p-q;

/*
	for(x=0; x<=n ; x++) {
		p = (a*x)/b;
		q = x/b;
		q = q*a;
		ans = MAX(ans, p-q);

		cout<<p<<" "<<q<<endl;
	}
*/
	cout<<ans<<endl;

	return 0;
}


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

int main(){
    int r,c,L,R;
    scanf("%d %d",&r,&c);
    int Q[r+1][c+1];
    for(int i=0;i<=r;i++)for(int j=0;j<=c;j++)Q[i][j]=0;
    for(int i=0;i<r;i++){
        L=0;
        for(int j=0;j<=c;j++){
            if(j!=c){
                scanf("%d",&Q[i][j]);
                L+=Q[i][j];
            } else {
                Q[i][j]=L;
            }
        }
    }
    for(int i=0;i<=c;i++){
        R=0;
        for(int j=0;j<=r;j++){
            if(j!=r){
                R+=Q[j][i];
            } else {
                Q[j][i]=R;
            }
        }
    }
    for(int i=0;i<=r;i++){
        for(int j=0;j<c;j++){
            printf("%d ",Q[i][j]);
        }
        printf("%d\n",Q[i][c]);
    }
}


Measured memory_bytes: 2688
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n, q;
string s;
llong com;
llong l, r;
llong idx;
char nch;
vector<vector<llong> > seg;

llong cnt(llong l, llong r) {
    l += n;
    r += n;

    llong cnt[32] = {};

    while (l < r) {
        if (l & 1) {
            for (int i = 0; i < 32; i++) {
                cnt[i] += seg[l][i];
            }
            l++;
        }
        if (r & 1) {
            r--;
            for (int i = 0; i < 32; i++) {
                cnt[i] += seg[r][i];
            }
        }

        l >>= 1;
        r >>= 1;
    }

    llong res = 0;
    for (int i = 0; i < 32; i++) res += (cnt[i] > 0 ? 1 : 0);

    return res;
}

void update(llong idx, char ch) {
    llong k = idx + n;
    seg[k][s[idx] - 'a']--;
    while (k > 1) {
        k >>= 1;
        seg[k][s[idx] - 'a']--;
    }

    s[idx] = ch;
    k = idx + n;
    seg[k][s[idx] - 'a']++;
    while (k > 1) {
        k >>= 1;
        seg[k][s[idx] - 'a']++;
    }
}

int main() {
    cin >> n >> s;
    seg.resize(2 * n, vector<llong>(32, 0));
    for (int i = 0; i < n; i++) {
        seg[i + n][s[i] - 'a'] = 1;
    }
    
    for (int i = n - 1; i > 0; i--) {
        llong l = i * 2;
        llong r = i * 2 + 1;

        for (int j = 0; j < 32; j++) {
            seg[i][j] += seg[l][j] + seg[r][j];
        }
    }

    cin >> q;
    while (q--) {
        cin >> com;

        if (com == 1) {
            cin >> idx >> nch;
            --idx;

            if (s[idx] == nch) continue;

            update(idx, nch);
        }
        else {
            cin >> l >> r;

            --l;
            cout << cnt(l, r) << '\n';
        }
    }

    return 0;
}


Measured memory_bytes: 289924
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define x first
#define y second

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

template <class T>
void read(T &x)
{
	char ch;
	for (ch=getchar();(ch<'0'||ch>'9')&&ch!='-';) ch=getchar();
	x=0;int t=1;if (ch=='-') {ch=getchar();t=-1;}
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	x*=t;
}

const int mod=1000000007;
int a[25][25],b[25],dp[1<<20],g[1<<20][21];

int main()
{
	#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int n,m,k;scanf("%d%d%d",&n,&m,&k);n--;
	if (!n) {puts("1");return 0;}
	memset(a,-1,sizeof(a));
	for (int i=0;i<k;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        a[x-1][n-y]=z;
    }
    dp[0]=1;
    for (int i=0;i<m;i++)
    {
        for (int j=0;j<(1<<n);j++)
        {
            for (int k=0;k<n;k++) b[k]=(j>>k)&1;
            int s=dp[j],x=-1;
            for (int k=0;k<n;k++)
            {
                if (b[k])
                {
                    if (x!=-1) s=(s+g[j-(1<<k)+(1<<x)][k])%mod; else s=(s+g[j-(1<<k)][k])%mod;
                }
                else
                    x=k;
                g[j][k]=s;
            }
            //x=0;
            //for (int k=1;k<n;k++) if (b[k]) x=k;
            //for (int k=x;k<n;k++) g[j][k]=(g[j][k]+dp[j])%mod;
        }
        for (int j=0;j<(1<<n);j++)
        {
            dp[j]=g[j][n-1];
            for (int k=0;k<n;k++)
                if (a[i][k]!=-1&&(((j>>k)&1)^a[i][k])) {dp[j]=0;break;}
        }
        //printf("%d %d %d %d\n",dp[0],dp[1],dp[2],dp[3]);
    }
    int ans=0;
    for (int i=0;i<(1<<n);i++) ans=(ans+dp[i])%mod;
    printf("%d\n",ans);
	return 0;
}



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

using namespace std;

double products(vector<int> &A, int j){
    double p = 1;
    for(int i=0; i<(int)A.size(); i++){
        if(i==j) continue;
        p *= A.at(i);
    }
    return p;
}

        

int main(){
    int N; cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A.at(i);
    
    double sum = 0;
    for(int j=0; j<N; j++) sum += products(A,  j);
    
    double pro = products(A, N);
    
    printf("%le\n", pro / sum);   
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 using namespace std;
 
 // #define  int           long long
 #define pb                push_back
 #define ppb               pop_back
 #define pf                push_front
 #define ppf               pop_front
 #define all(x)            (x).begin(),(x).end()
 #define uniq(v)           (v).erase(unique(all(v)),(v).end())
 #define sz(x)             (int)((x).size())
 #define fr                first
 #define sc                second
 #define pint              pair<int,int>
 #define rep(i,a,b)        for(int i=a;i<b;i++)
 #define mem1(a)           memset(a,-1,sizeof(a))
 #define mem0(a)           memset(a,0,sizeof(a))
 #define ppc               __builtin_popcount
 #define ppcll             __builtin_popcountll
 #define vint			   vector<int>
 #define vpint			   vector<pair<int,int>>
 #define mp                make_pair


 void reader() 
 { 
 #ifndef ONLINE_JUDGE 
 freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout); 
 #endif
 }
 
 void fastIO() {ios_base::sync_with_stdio(false); cin.tie(NULL);}
 
 
 
 void solve()
 {
 
 int e=1e9+7;
 int n;
 cin>>n;
 long long int a[n],b[n];
 rep(i,0,n)
 {
 	cin>>a[i];	
 	b[i]=a[i];
 } 
 rep(i,1,n)
 b[i]+=b[i-1];

int sum=0;
 for(int i=0;i<n-1;i++)
 	sum=((sum%e)+(1LL*(a[i]%e)*((b[n-1]-b[i])%e))%e)%e;

if(n==1)
	cout<<a[0];
else
cout<<sum;
 
 
 }
 
 
 
 signed main()
 {
 	reader(); fastIO();
 	long long t=1;
 	//cin>>t;
 	while(t--) solve();
 	return 0;
 }

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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/g.in", "r", stdin);
//  freopen("../IO/g.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

using u32 = uint32_t;

static constexpr u32 dbj[32] = {
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

u32 get(u32 v) {
  return 1u << (u32) dbj[((v & -v) * 0x077CB531U) >> 27];
}


void dfs(u32 mask, u32 a, u32 b) {
  if ((mask & (mask - 1)) == 0) {
    cout << a << ' ' << b << ' ';
  } else {
    u32 c = get(a ^ b);
    u32 d = get(mask ^ c);
    dfs(mask ^ c, a, a ^ d);
    dfs(mask ^ c, a ^ d ^ c, b);
  }
}

void solve(std::istream &in, std::ostream &out) {
  u32 k;
  in >> k;
  u32 a = 0, b = 0;
  in >> a >> b;
//  {
//    int n;
//    in >> n;
//    for (int i = 0; i < n; ++i) {
//      u32 z;
//      in >> z;
//      --z;
//      a |= 1u << z;
//    }
//    in >> n;
//    for (int i = 0; i < n; ++i) {
//      u32 z;
//      in >> z;
//      --z;
//      b |= 1u << z;
//    }
//  }
  if (__builtin_popcount(a ^ b) & 1) {
    out << "YES\n";
    dfs((1u << k) - 1, a, b);
  } else {

    out << "NO\n";
  }
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <string>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

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

	int sizet = str.length() - 1;

	cout << str[0] << str.length()-2 << str[sizet] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

#define REP(i,n) for(int i=0; i<n; i++)
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
 
#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define SIZE 86400	// 60*60*24

using namespace std;
typedef long long ll;

int main(){
	while(1){
		int n, data[SIZE], h, m, s, t, ans;
		
		cin >> n;
		if (n==0) break;
		REP(i,SIZE) data[i] = 0;
		ans = 0;
		
		REP(i,n){
			//debug(i);
			scanf("%d:%d:%d", &h, &m, &s);
			t = h*60*60 + m*60 + s;
			//debug(t);
			data[t]++;
			scanf("%d:%d:%d", &h, &m, &s);
			t = h*60*60 + m*60 + s;
			//debug(t);
			data[t]--;		
		}
		
		
		
		for (int i=1; i<SIZE; i++) data[i]+=data[i-1];
		
		REP(i,SIZE){
			if (ans<data[i]){
				ans = data[i];
			}
		}
			
		
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3440
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int k = sc.nextInt();
      double n0 = (double) 1/n;
      double count = 0;
      int point = 0;
      double per = 0;
      for(int i = 1;i <= n;i++){
        point = i;
      	while(point < k){
        	count++;
            point = point*2;
        }
        per += n0*Math.pow(0.5,count);
        count = 0;
      }
      System.out.println(per);
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

ld a,b,x;

void solve(){
  cin >> a >> b >> x;
  if(x>=a*a*b/2){
    cout << 180*atan(2*(b/a-x/(a*a*a)))/pi << endl;
  }
  else{
    cout << 180*atan(a*b*b/(2*x))/pi << endl;
  }
}

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

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>

using namespace std;

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

#define maxN 5011

int n, k, i, a[maxN];
bitset<maxN> B[maxN], aux, mask;
int ans;

bool useful(const bitset<maxN>& b1, const bitset<maxN>& b2, int need) {
    int i, j;

    for (j = 0; j + 1 < k; j++);

    for (i = 0; i < k; i++) {
        if (i + j >= k) j--;

        while (j >= 0) {
            if (b2[j]) break;
            j--;
        }
        if (j < 0) return false;

        if (b1[i] && i + j >= need && i + j < k)
            return true;
    }

    return false;
}

int main()
{
   // freopen("test.in","r",stdin);

    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]), a[i] = min(a[i], k);

    ans = n;
    for (i = 0; i < k; i++) mask[i] = 1;

    B[0][0] = 1;
    for (i = 1; i <= n; i++)
        B[i] = mask & (B[i - 1] | (B[i - 1] << a[i]));

    aux[0] = 1;
    for (i = n; i > 0; i--) {

        if (useful(B[i - 1], aux, k - a[i]))
            ans--;

        aux = mask & (aux | (aux << a[i]));
    }

    printf("%d", ans);


    return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int  main()
{
	vector<string> tag;
	int n;
	cin >> n;

	string tmp_txt;
	cin >> tmp_txt;
	tag.push_back(tmp_txt);
	bool yesno = false;
	for (int i = 1; i < n; i++) {
		cin >> tmp_txt;
		for (int j = 0; j < tag.size(); j++) {
			if (tag[j] == tmp_txt)yesno = true;
		}
		if (tag[i - 1][tag[i - 1].length() - 1] != tmp_txt[0])yesno = true;
		tag.push_back(tmp_txt);
	}
	if (yesno)cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();

		System.out.println(core(s));
	}
	
	static String core(String s) {
		char a = s.charAt(0);
		a++;
		
		
		char cs[] = new char[1];
		cs[0]=a;
		return new String(cs);
	}	
}

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


using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){
  
  int d;
  int res = 0;
  cin >> d;
  vector<int> c(26);
  rep(i,26)cin >> c[i];
  vector<vector<int>> v(d,vector<int>(26));
  vector<int> contest(d);
  vector<int> last(26,0);
  vector<int> satisfy(26,0);
  rep(i,d)rep(j,26){
    int x;cin >> x;
    v[i][j] = x;
  }
  for(int i = 1;i <= d;i++){
    cin >> contest[i-1];
    contest[i-1]--;
    last[contest[i-1]] = i;
    res += v[i-1][contest[i-1]];
    rep(j,26)res -= c[j]*(i-last[j]),satisfy[j] += c[j]*(i-last[j]);
  }
  int Q;cin >> Q;
  while(Q--){
    int day,pos;cin >> day >> pos;
    day--,pos--;
    int pre = contest[day];
    res += satisfy[pos];
    res += satisfy[pre];
    res -= v[day][pre];
    res += v[day][pos];
    satisfy[pos] = satisfy[pre] = 0;
    last[pos] = last[pre] = 0;
    contest[day] = pos;
    for(int i = 1;i <= d;i++)last[pos] = (contest[i-1] == pos ? last[pos] = i : last[pos]),satisfy[pos] += c[pos]*(i-last[pos]);
    for(int i = 1;i <= d;i++)last[pre] = (contest[i-1] == pre ? last[pre] = i : last[pre]),satisfy[pre] += c[pre]*(i-last[pre]);
    res -= (satisfy[pos]+satisfy[pre]);
    cout << res << endl;
  }

  
  


  return 0;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=1<<18;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

int n;
ll a[maxn];
vector<ll> v;

int BIT[maxn];
int low(int n){return n&(-n);}
void add(int n){
    for(int i=n;i<maxn;i+=low(i)) BIT[i]++;
}
int query(int n){
    int ret=0;
    for(int i=n;i>0;i-=low(i)) ret+=BIT[i];
    return ret;
}

int main()
{
	IOS;
	ll k;
    cin>>n>>k;
    REP(i,n) cin>>a[i+1];
    REP(i,n) a[i+1]-=k;
    //REP(i,n) cout<<a[i]<<" \n"[i==n-1];
    REP(i,n) a[i+1]=a[i+1]+a[i];
    n++;
    //REP(i,n) cout<<a[i]<<" \n"[i==n-1];
    REP(i,n) v.pb(a[i]);
    SORT_UNIQUE(v);
    REP(i,n) a[i]=1+GET_POS(v,a[i]);
    //REP(i,n) cout<<a[i]<<" \n"[i==n-1];
    ll ans=0;
    REP(i,n){
        ans+=query(a[i]);
        add(a[i]);
    }
    cout<<ans<<'\n';
}


Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    ll p,q;
    cin>>p>>q;
    q/=__gcd(p,q);
    ll ans=1;
    for(int i=2;i*i<=q;++i){
        if(q%i==0) ans*=i;
        while(q%i==0) q/=i;
    }
    cout<<ans*q<<endl;
    return 0;
}


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

int main() {
  int A[12] = {0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0};
  int x, y;

  cin >> x >> y;

  if (A[x - 1] == A[y - 1]) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
    
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int X = scanner.nextInt();
        int[] C = new int[N];
        int[][] A = new int[N][M];
        for (int i = 0; i < N; i++) {
            C[i] = scanner.nextInt();
            for (int j = 0; j < M; j++) {
                A[i][j] = scanner.nextInt();
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < (1<<N); i++) {
            int cost = 0;
            int[] understand = new int[M];
            // System.out.println(i);
            for (int j = 0; j < N; j++) {
                int buyj = (i>>j)&1;
                if(buyj == 1){
                    cost += C[j];
                    for (int k = 0; k < M; k++) {
                        understand[k] += A[j][k];
                    }
                }
            }
            // for (int j = 0; j < M; j++) {
            //     System.out.print(understand[j]);
            // }
            // System.out.println("");
            boolean res = true;
            for (int j = 0; j < M; j++) {
                if(understand[j] < X) res = false;
            }
            if(res) ans = Math.min(ans, cost);
        }
        if(ans==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);
    }
}

Measured memory_bytes: 37416
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int X;
  cin>>X;
  cout<<X/500*1000+((X-500*(X/500))/5)*5<<endl;
}

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

using namespace std;

int main() {
    int n, m;
    long long answer = 0;
    cin >> n >> m;
    priority_queue<int> q;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        q.push(a);
        answer += a;
    }
    for (int i = 0; i < m; ++i) {
        int t = q.top();
        q.pop();
        answer -= t / 2;
        if (t % 2 != 0) --answer;
        q.push(t / 2);
    }
    cout << answer << endl;
}


Measured memory_bytes: 892
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		String[] s = saori.nextHayami().split("");
		int ans = 0;
		for(int i = 0;i < s.length - 2;i++){
			if(s[i].equals("A") && s[i+1].equals("B") && s[i+2].equals("C")){
				ans++;
			}
		}
		System.out.println(ans);
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);

int main()
{
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    int cnt = 0;
    rep(i, N)
    {
        while (a[i] % 2 == 0)
        {
            cnt++;
            a[i] /= 2;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
N, K = gets.chomp.split(" ").map(&:to_i)

max_k = (N - 1) * (N - 2) / 2
if K > max_k
  puts -1
  exit
end

m = N - 1 + max_k - K
puts m
2.upto(N) do |i|
  puts "1 #{i}"
end
ring = (2..N).to_a
rsize = ring.size
(max_k - K).times do |k|
  s, i = k.divmod(rsize)
  j = (i + 1 + s) % rsize
  puts "#{ring[i]} #{ring[j]}"
end


Measured memory_bytes: 1788
N,Y = map(int,input().split())

flag = 0
for x in range(Y//10000+1) :
    if flag != 0 :
        break
    else :
        for y in range(Y//5000+1) :
            if flag != 0 :
                break
            else :
                z = N-x-y
                if z >= 0 and (10000*x+5000*y+1000*z) == Y :
                    ans = [x,y,z]
                    flag = 1
if flag == 0 :
    print(-1,-1,-1)
else :
    print(ans[0],ans[1],ans[2])
    

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

typedef long long ll;

using namespace std;

int main() {
    int N; cin >> N;
    ll a[N]; for(int i = 0; i < N; ++i) cin >> a[i];
    long long res = 0;
    for(int i = 0; i < N; ++i) {
        while(a[i]%2==0) a[i] /= 2, ++res;
    }
    cout << res << endl;

}


Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.stream.Stream;

public class Main {

  static int n, ans;
  static long[] l;

  public static void main(String[] args) throws Exception {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);

    String[] in = br.readLine().split(" ");
    n = Integer.parseInt(in[0]);
    in = br.readLine().split(" ");
    l = Stream.of(in).mapToLong(Long::parseLong).toArray();

    br.close();

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
          if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i]) continue;
          if ((Math.abs(l[i] - l[j]) < l[k]) && (l[i] + l[j] > l[k])) ans++;
        }
      }
    }

    out.println(ans);

    out.flush();
  }
}


Measured memory_bytes: 34944
import math

def main():
    N, M = [int(i) for i in input().split()]

    result = 0
    if N >= 2:
        c = math.factorial(N) // (math.factorial(2) * math.factorial(N - 2))
        result += c
    if M >= 2:
        c = math.factorial(M) // (math.factorial(2) * math.factorial(M - 2))
        result += c
    print(result)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int A[100010], B[100010];
ll sum, tmp, cnt;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    sum += A[i];
  }
  tmp = (ll)N * (N + 1) / 2;
  if (sum % tmp != 0) {
    cout << "NO" << endl;
    return 0;
  }
  cnt = sum / tmp;
  ll neg = 0;
  for (int i = 0; i < N; i++) {
    B[i] = A[i] - A[(i - 1 + N) % N];
    B[i] = B[i] - cnt;
    if (B[i] > 0 || B[i] % N != 0) {
      cout << "NO" << endl;
      return 0;
    }
    neg += -B[i] / N;
  }
  cout << (neg == cnt ? "YES" : "NO") << endl;

  return 0;
}

Measured memory_bytes: 1024
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    W, a, b, = il()
    if b <= a + W <= b + W or b <= a <= b + W:
        print(0)
        exit()

    l = min(abs(b - (W + a)), abs(a - (W + b)))
    print(0 if l <= 0 else l)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3892
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        int M = sc.nextInt();
        final int Q = sc.nextInt();
        int[][] LR = new int[N+1][N+1];
        int[][] sum = new int[N+1][N+1];
        for(int i = 0;i < M;i++){
            int li = sc.nextInt();
            int ri = sc.nextInt();
            LR[li][ri]++;
        }
        for(int i = 1;i < N+1;i++){
            for(int j = 1;j < N+1;j++){
                sum[i][j] += sum[i][j-1]+LR[i][j];
            }
        }
        int[] ANS = new int[Q];
        for(int i = 0;i < Q;i++){
            int ans = 0;
            int pi = sc.nextInt();
            int qi = sc.nextInt();
            for(int j = pi;j <= qi;j++){
                ans += sum[j][qi]-sum[j][pi-1];
            }
            ANS[i] = ans;
        }
        for(int i = 0;i < Q;i++)    System.out.println(ANS[i]);
    }
}

Measured memory_bytes: 154384
import scala.io.StdIn._

object Main extends App {

  val Array(n,q) = readLine().split(" ").map(_.toInt)
  val s = readLine()
  val lr = Array.fill(q)(readLine().split(" ").map(_.toInt -1))

  def solve() = {
    val cSum = Array.fill(n)(0)
    for(i <- 0 until n) {
      if(i == 0) cSum(i) = 0
      else if(s(i-1) == 'A' && s(i) == 'C') cSum(i) = cSum(i-1) + 1
      else cSum(i) = cSum(i-1)
    }
    lr.map{ list =>
      cSum(list(1)) - cSum(list(0))
    }.mkString("\n")
  }
  println(solve())

}



Measured memory_bytes: 63780
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

string s;
int k;

int32_t main(){_
    //freopen("input","r",stdin);
    cin >> s;
    cin >> k;    
    for(int i = 0;i < sz(s);i++)
    {
        if(s[i] != 'a' && k >= 26 - s[i] + 'a')
        {
            k -= 26 - s[i] + 'a';
            s[i] = 'a';
        }
    }
    int x = s[sz(s) - 1] - 'a';
    x += k;
    x %= 26;
    s[sz(s) - 1] = 'a' + x;
    rc(s);
}


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

int main()
{

  int a[3];
  rep(i,3) cin >> a[i];
  sort(a,a+3);
  if(a[0] == 5 && a[1] == 5 && a[2] == 7) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3580
# -*- coding: utf-8 -*-
import math
import sys

import math
import sys


## input
n,m,q = map(int, sys.stdin.readline().rstrip().split())

## l,r をinputしてdp
num_s = [[0 for j in range(n+2)] for i in range(n+2)]
for _ in range(m):
  l,r = map(int, sys.stdin.readline().rstrip().split())
  num_s[l][r] += 1

dp = [[0 for j in range(n+2)] for i in range(n+2)]
for i in range(n,0,-1):
  for j in range(i,n+1):
    dp[i][j] = dp[i][j] + dp[i][j-1] + num_s[i][j]

for j in range(1,n+1):
  for i in range(j,0,-1):
    dp[i][j] = dp[i+1][j] + dp[i][j]

ans = []
for _ in range(q):
  p,q = map(int, sys.stdin.readline().rstrip().split())
  ans.append(dp[p][q])

## output
for a in ans:
  print(a)

Measured memory_bytes: 12700
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

if __name__ == '__main__':
    a = [int(i) for i in input().split()]
    a.sort()

    if a[0] +a[1] == a[2]:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 3828
/*************************************************************************
	> File Name: 1.cpp
	> Author: Knowledge_llz
	> Mail: 925538513@qq.com 
	> Blog: https://blog.csdn.net/Pig_cfbsl 
	> Created Time: 2020/7/5 20:21:41
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define LL long long
using namespace std;
int read(){
	char x=getchar(); int u=0,fg=0;
	while(!isdigit(x)){ if(x=='-') fg=1; x=getchar(); }
	while(isdigit(x)){ u=(u<<3)+(u<<1)+(x^48); x=getchar(); }
	return fg?-u:u;
}
const int maxx=2e5+10;
LL a[maxx];
bool cmp(LL x,LL y){ return x>y; } 
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#endif
	int n=read();
	For(i,1,n) a[i]=read();
	sort(a+1,a+n+1,cmp);
	LL ans=0,cnt=1;
	bool op=1;
	For(i,2,n){
		ans+=a[cnt];
		op^=1;
		if(!op) cnt++;
	}
	printf("%lld\n",ans);
	return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

ll n,m,T,k,d;
const ll big = 1000000007;

set<pii> S;
vector<vl> C(200001, vl());

ll f(ll x, ll y){
    ll bottom = n-1;
    for(int c1 = 0; c1 < sz(C[y]); c1++){
        if(C[y][c1]-1 >= x && C[y][c1]-1 < bottom)bottom = C[y][c1]-1;
    }
   // cerr << x << " " << y << "  -  " << bottom << "\n";
    ll res = bottom-x+1;
    if(y < m-1){
        int nextr = -1;
        for(int c1 = x+1; c1 < n; c1++){
            if(S.find({c1,y+1}) == S.end()){
                nextr = c1;
                break;
            }
        }
        if(nextr != -1){
            res = min(res, (nextr-x)+f(nextr,y+1));
        }

    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,e;

    cin >> n >> m >> k;
    for(int c1 = 0; c1 < k; c1++){
        cin >> a >> b;
        a--;
        b--;
        S.insert({a,b});
        C[b].push_back(a);
    }

    ll ans = f(0,0);
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 23424