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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
#define pb push_back

#define INF int(1e9)
#define EPS 1e-9
#define MOD int(1e9 + 7)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	int arr[n + 1];
	for(int i = 1; i <= n; i++)
		cin >> arr[i];
	int freq[n + 1];
	memset(freq, 0, sizeof freq);
	vi ans;
	for(int i = n; i > 0; i--) {
		if(freq[i] % 2 != arr[i]) {
			ans.pb(i);
			for(int j = 1; j * j <= i; j++) {
				if(i % j == 0) {
					if((i / j) != j)
						freq[i / j]++;
					freq[j]++;
				}
			}
		}
	}
	cout << ans.size() << '\n';
	for(int i : ans)
		cout << i << " ";
	cout << "\n";
	return 0;
}


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

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define Rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define X first
#define Y second
#define PB(a) push_back(a)
#define MP(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

template <typename T> inline T read() {
    static T _, __; static char c_;
    for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}
//EOT

const int maxn = 45;

int n, m;
int sum[maxn][maxn], dp[maxn][maxn][maxn][maxn], x, y, vis[maxn][maxn][maxn][maxn];

inline void Init() {
    static char str[maxn];
    n = read<int>(), m = read<int>();
    For(i, 1, n) {
        scanf("%s", str + 1);
        For(j, 1, m)
            if (str[j] == 'P') x = i, y = j;
            else if (str[j] == '#') sum[i][j] = 1;
    }
    For(i, 1, n) For(j, 1, m)
        sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

inline int getsum(int x1, int y1, int x2, int y2) {
    //if (sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1] < 0)
        //cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
    return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}

int DFS(int x1, int y1, int x2, int y2) {
    if (!chkmax(vis[x1][y1][x2][y2], 1)) return dp[x1][y1][x2][y2];
    int &ans = dp[x1][y1][x2][y2] = INF;
    chkmin(ans, getsum(x1, y1, x, y));
    chkmin(ans, getsum(x1, y, x, y2));
    chkmin(ans, getsum(x, y1, x2, y));
    chkmin(ans, getsum(x, y, x2, y2));
    For(i, x1 + 1, x) For(j, y1 + 1, y) if (i != x1 || j != y1)
        chkmin(ans, DFS(i, j, x2, y2) + getsum(i, y1, x2, j - 1) + getsum(x1, j, i - 1, y2));
    For(i, x, x2 - 1) For(j, y, y2 - 1) if (i != x2 || j != y2)
        chkmin(ans, DFS(x1, y1, i, j) + getsum(i + 1, y1, x2, j) + getsum(x1, j + 1, i, y2));
    For(i, x, x2 - 1) For(j, y1 + 1, y) if (i != x2 || j != y1)
        chkmin(ans, DFS(x1, j, i, y2) + getsum(x1, y1, i, j - 1) + getsum(i + 1, j, x2, y2));
    For(i, x1 + 1, x) For(j, y, y2 - 1) if (i != x1 || j != y2)
        chkmin(ans, DFS(i, y1, x2, j) + getsum(x1, y1, i - 1, j) + getsum(i, j + 1, x2, y2));
    return ans;
}

int main() {

    Init();
    printf("%d\n", DFS(1, 1, n, m));

    return 0;
}

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

int main(void){

  int N, K;
  scanf("%d %d\n", &N, &K);

  long long num=0;
  long long ans=0;

  num = N/K;
  ans = num * num * num;

  if(!(K%2)){
    num = N/(K/2) - N/K;
    ans += num * num * num;
  }

  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
#define MOD 1000000007
// a^b mod MOD
ll powmod(ll a,ll b){
	ll out=1;
	ll p=a%MOD;
	while(b){
		if(b&1)out=out*p%MOD;
		p=p*p%MOD;
		b>>=1;
	}
	return out;
}
int main(){
	int n;
	cin>>n;
	vi in(n);
	rep(i,n)cin>>in[i];
	sort(all(in));
	bool h=true;
	if(n%2&&in[0]||n%2==0&&in[0]!=1)h=false;
	rep(i,n-1)if((i+n)%2&&in[i+1]-in[i]!=2||(i+n)%2==0&&in[i+1]!=in[i])h=false;
	if(h)cout<<powmod(2,n/2)<<endl;
	else cout<<0<<endl;
}










Measured memory_bytes: 640
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}

type BitSet []uint64
func NewBitSet(N int) *BitSet {
  B := BitSet(make([]uint64, N / 64 + 1))
  return &B
}
func (B *BitSet) ShOr(N int) {
  n, k := N / 64, N % 64
  for i := len((*B)) - 1; 0 <= i; i-- {
    x := i - n
    if x < 0 { break }
    (*B)[i] |= (*B)[x] << uint(k)
    if 0 < k && 0 < x { (*B)[i] |= (*B)[x - 1] >> uint(64 - k) }
  }
}
func (B *BitSet) Get(N int) uint64 {
  n, k := N / 64, N % 64
  return ((*B)[n] >> uint(k)) % 2
}

func Solve() {
  var N int
  NextInt(&N)
  var A []int
  NextIntVec(&A)
  S := SumInt(A...)
  B := NewBitSet(S)
  (*B)[0]++
  for _, a := range A {
    B.ShOr(a)
  }
  for i := S - S / 2; i <= S; i++ {
    if B.Get(i) == 1 {
      Write(i)
      break
    }
  }
  return
}

func main() {
  Solve()
  Output()
}

Measured memory_bytes: 1280
#include <stdlib.h>
#include <stack>
#include <list>
#include <string>
#include <iostream>
using namespace std;

int main(){
	string cross_section;
	stack<int> positions;
	list<pair<int, int> > water_area;
	int result = 0;
	cin >> cross_section;

	int end_position = cross_section.length();
	for(int current_position = 0; current_position < end_position; ++current_position){
		int merge_area = 0;
		if(cross_section[current_position] == '_'){
			continue;
		}else if(cross_section[current_position] == '\\'){
			positions.push(current_position);
		}else if(cross_section[current_position] == '/'){
			if(!positions.empty()){
				result += current_position - positions.top();
				while(!water_area.empty()){
					if(water_area.front().first > positions.top()){
						merge_area += water_area.front().second;
						water_area.pop_front();
					}else{
						break;
					}
				}
				water_area.push_front(pair<int, int>(positions.top(), merge_area + current_position - positions.top()));
				positions.pop();
			}
		}
	}
	cout << result << endl;
	cout << water_area.size();
	while(!water_area.empty()){
		cout << " " << water_area.back().second;
		water_area.pop_back();
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 1328
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    ll n=s.size();
    rep(i,n){
        char now=s[i];
        if(s[i+1]==now){
            cout<<i+1<<" "<<i+2<<endl;
            return 0;
        }
        if(s[i+2]==now){
            cout<<i+1<<" "<<i+3<<endl;
            return 0;
        }
    }
    cout<<-1<<" "<<-1<<endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#define ll long long
const int MOD = 1e9+7;
using namespace std;

bool judge(int i, int m, vector<int> &s, vector<int> &c){
	for (int j = 0; j < m; j++){
		if (to_string(i)[s[j]-1] - '0' != c[j]) return false;
	}
	return true;
}

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> s(m);
	vector<int> c(m);
	for (int i = 0; i < m; i++){
		cin >> s[i] >> c[i];
	}
	for (int i = 0; i <= 999; i++){
		if (to_string(i).length() == n){
			if (judge(i, m, s, c)){
				cout << i << endl;
				return 0;
			}
		}
	}
	cout << -1 << endl;
	return 0;
}

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

std::vector<std::vector<int>> vec;

int n, m, x, y;

void dfs(int edge, std::vector<bool> bool_vec, int& c) {
    if (bool_vec[edge]) {
        return;
    }
    bool_vec[edge] = true;
    bool all_true = true;
    for (int i = 1; i <= n; i++) {
        if (bool_vec[i] == false) {
            all_true = false;
            break;
        }
    }
    if (all_true) {
        c++;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (vec[edge][i] == 1) {
            dfs(i, bool_vec, c);
        }
    }
}




int main() {
    std::cin >> n >> m;
    vec.assign(n+1, std::vector<int>(n+1, 0));
    for (int i = 0; i < m; i++) {
        std::cin >> y >> x;
        vec[y][x] = 1;
        vec[x][y] = 1;
    }
    int c = 0;
    std::vector<bool> bv(n+1, false);
    dfs(1, bv, c);
    std::cout << c << std::endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
	int n; cin >> n;
	int a[n][3], d[n][3];
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	d[0][0] = a[0][0]; d[0][1] = a[0][1], d[0][2] = a[0][2];
	for (int i = 1; i < n; ++i)
	{
		d[i][0] = max(d[i-1][1], d[i-1][2]) + a[i][0];
		d[i][1] = max(d[i-1][0], d[i-1][2]) + a[i][1];
		d[i][2] = max(d[i-1][0], d[i-1][1]) + a[i][2];
	}
    cout << max(max(d[n-1][0], d[n-1][1]), d[n-1][2]);
}

Measured memory_bytes: 5932
import java.util.*;

public class Main{
    public static void main(String[] args){
	     Scanner sc=new Scanner(System.in);
       int[] n=new int[3];
       n[0]=Integer.parseInt(sc.next());
       n[1]=Integer.parseInt(sc.next());
       n[2]=Integer.parseInt(sc.next());

       int count5=0;
       int count7=0;

       for(int i=0;i<3;i++){
         if(n[i]==5) count5++;
         if(n[i]==7) count7++;
       }

       if(count5==2 && count7==1) System.out.println("YES");
       else System.out.println("NO");

    }
}


Measured memory_bytes: 21332
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
ll test[12345678];
signed main() {
	ll n, m, q, k, a = 0, b = 0, c = 0, cnt = 0; string s, t; char z;
	cin >> z;
	if (97 <= (ll)z) { cout << 'a' << endl; }
	else { cout << 'A' << endl; }
	return 0;
}

Measured memory_bytes: 3620
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define copy(a, b) memcpy(b,a,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define rep1(i, n) for(int i=1;i<=(int)n;++i)
#define per1(i, n) for(int i=(int)n;i>=1;--i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef long double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;
typedef vector<db> vdb;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const db EPS = 1e-15;
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

//

int32_t main() {
  FAST_IO;
  int a, b;
  cin >> a >> b;
  cout << (a * b) / __gcd(a, b) << '\n';
  rtn 0;
}


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

#define INF 1000000000

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, m, u, v, s, t;
    cin >> n >> m;
    vector< vector<int> > e(n + 1);
    for (int i = 0; i < m; ++i) cin >> u >> v, e.at(u).push_back(v);
    cin >> s >> t;
    vector< vector<int> > mem(n + 1, vector<int>(3, INF));
    mem.at(s).at(0) = 0;
    queue< pair<int, int> > q;
    q.push({s, 0});
    while (!q.empty()) {
        pair<int, int> next = q.front();
        q.pop();
        for (auto i = e.at(next.first).begin(); i != e.at(next.first).end(); ++i) {
            if (mem.at(*i).at((next.second + 1) % 3) > mem.at(next.first).at(next.second) + 1) {
                mem.at(*i).at((next.second + 1) % 3) = mem.at(next.first).at(next.second) + 1;
                q.push({*i, (next.second + 1) % 3});
            }
        }
    }
    cout << (mem.at(t).at(0) == INF ? -1 : mem.at(t).at(0) / 3) << endl;
    return 0;
}


Measured memory_bytes: 11264
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
    string S;
    cin >> S;

    int num[4];
    rep(i, 4) num[i] = S[i] - '0';
    rep(i, 1 << 3) {
        int res = num[0];
        string str = "";
        str += num[0] + '0';
        rep(j, 3) {
            if (i & (1 << j)) {
                res += num[j + 1];
                str += '+';
            } else {
                res -= num[j + 1];
                str += '-';
            }
            str += num[j + 1] + '0';
        }
        if (res == 7) {
            str += "=7";
            cout << str << endl;
            return 0;
        }
    }
}


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

ll n,a1,a2,ai,sum,x,half;

int main(){
	cin>>n;
	cin>>a1>>a2;
	sum=a1+a2;
	for(ll i=2;i<n;i++) scanf("%lld",&ai), x^=ai;
	if((sum-x)%2||sum<x){//a+b=a^b+(a&b)*2 
		puts("-1"); return 0;
	}
	half=(sum-x)/2;//a^b 
	if(half>a1||half&x){
		puts("-1"); return 0;
	}
	for(ll i=40;i>=0;i--){
		ll add=1ll<<i;//注意强转ll 
		if(add&x) {
			if(half+add<=a1) half+=add;
		}
	}
	if(half==0){//a全部变成0 ，不和题意 
		puts("-1"); return 0;
	}
//cout<<a1<<" "<<half<<endl;
	cout<<a1-half<<endl;
	return 0;
}


Measured memory_bytes: 3764
package main
 
import(
  "fmt"
  "strconv"
	"bufio"
	"os"
	"strings"
)
 
var sc = bufio.NewScanner(os.Stdin)
 
func Rr() []string {
  sc.Scan()
  slice := strings.Split(sc.Text(), " ")
  return slice
}
 
func abc138b(rerow []string, N int){
	sum := 0.0
	ans := 0.0
	for _,num := range rerow{
		ans,_ := strconv.ParseFloat(num,32)
		sum = sum + 1 / ans
	}
	ans = 1 / sum
	fmt.Println(ans)
}	
 
func main(){
	flag := 0
	N := 0
	var s []string
	for i := 0; i < 2; i++{
		if flag != 1{
			s = Rr()
			N,_ = strconv.Atoi(s[0])
		} else {
			s = Rr()
		}
	}
	abc138b(s,N)
}

Measured memory_bytes: 640
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func getCombinationTable(n, k, p int) [][]int {
	table := make([][]int, n+1)
	table[0] = make([]int, k+1)
	table[0][0] = 1
	for i := 1; i <= n; i++ {
		table[i] = make([]int, k+1)
		table[i][0] = 1
		for j := 1; j <= k; j++ {
			table[i][j] = (table[i-1][j] + table[i-1][j-1]) % p
		}
	}
	return table
}

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

	prime := 1000000000 + 7

	nBalls := nextInt()
	nBoxes := nextInt()

	table := getCombinationTable(nBoxes, nBalls, prime)
	fmt.Println(table[nBoxes][nBalls])
}



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

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> D(N);
    bool zero = false;
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    if (zero) {
        cout << 0 << endl;
        return 0;
    }
    sort(D.begin(), D.end());
    vector<int> tim{0};
    for (int i = 0; i < N; i++) {
        if (i % 2 == 1) {
            tim.push_back(D[i]);
        } else {
            tim.push_back(24 - D[i]);
        }
    }
    sort(tim.begin(), tim.end());
    tim.push_back(24);
    int mini = 25;
    for (int i = 0; i < tim.size() - 1; i++) {
        mini = min(mini, tim[i + 1] - tim[i]);
    }
    cout << mini << endl;

    return 0;
}


Measured memory_bytes: 256
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0 }, dy[] = { 0,1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑


long long digits(string h) {
	long long res = 0;
	for (int i = 0; i < h.length(); ++i) {
		res += h[i] - '0';
	}
	return res;
}

int main() {
	while (1) {
		string n;
		cin >> n;
		if (n == "0") { break; }
		cout << digits(n) << endl;
	}
}


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

int main() {
	vector<int>a(3);
	cin >> a.at(0) >> a.at(1) >> a.at(2);
	sort(a.begin(), a.end());
	ll ans = 0;
	while (!(a.at(0) == a.at(1) && a.at(1) == a.at(2))) {
		if (a.at(1) - a.at(0) >= 2) {
			ans++;
			a.at(0) += 2;
		}
		else if (a.at(1) - a.at(0) == 1) {
			ans++;
			a.at(0)++;
			a.at(2)++;
		}
		else {
			int x = a.at(2) - a.at(1);
			ans += x;
			break;
		}
	}
	cout << ans << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<string> restaurants;
    for (int i = 0; i < n; i++) {
        string name;
        int point;
        cin >> name >> point;
        ostringstream ss;
        ss << name << setw(3) << setfill('0') << 100 - point << ":" << setw(3) << setfill('0') << i + 1;
        restaurants.push_back(ss.str());
    }
    sort(restaurants.begin(), restaurants.end());
    for(int i = 0; i < n; i++){
        int length = restaurants[i].length();
        cout << atoi(restaurants[i].substr(length - 3, length).c_str()) << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
while True:
    n=int(input())
    if n == 0:
        break
    else:
        x=[]
        for i in range (n):
            A=int(input())
            x.append(A)
        x1=sorted(x)
        b=0
        for j in range (0,10):
            m=x1.count(b)
            
            if m==0:
                print("-")
                    
            else:
                print("*"*m)
            b+=1


Measured memory_bytes: 5772
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>

class AABCSwap {
public:
  void solve(std::istream &in, std::ostream &out) {
    int X, Y, Z;
    in >> X >> Y >> Z;
    out << Z << " " << X << " " << Y;
  }
};


int main() {
	AABCSwap solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++)cin >> a[i];
    vector<int> b=a;
    sort(b.begin(),b.end());
    int count=0;
    for(int i=0; i<n; i++){
        if(a[i]!=b[i])count++;
    }
    if(count<=2)cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

int main() {
  int A, B;
  cin >> A >> B;

// within 99
  if (A>0 && A < 10 && B >0 && B<10){
     cout << A*B << endl;
  }
//without 99
  else{
    cout << -1 << endl;
  }
}

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

#include <boost/algorithm/string/replace.hpp>
using namespace std;

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniqueV(x)                                                             \
  sort(x.begin(), x.end());                                                    \
  x.erase(unique(x.begin(), x.end()), x.end());
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y)                                                           \
  cerr << "(" << #x << ", " << #y << ") = "                                    \
       << "(" << x << ", " << y << ")" << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

// ----------------------------------------------

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

  string s;

  cin >> s;

  boost::algorithm::replace_all(s, "?", "D");

  cout << s << endl;

  return 0;
}

Measured memory_bytes: 3756
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  string s;cin>>s;
  string t;cin>>t;
  bool flag=true;
  int n=s.length();
  rep(i,n){
    if(s[i]!=t[i])flag=false;
  }
	if(flag){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define LINY "YES\n"
#define Liny "Yes\n"
#define LINN "NO\n"
#define Linn "No\n"
#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"

int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a*b /gcd(a,b);}

int main(){
  ll N,M; cin>>N>>M;
  vector<ll> s;
  map<ll,ll> mp_count;
  REP(i,N){
    ll a; cin>>a;
    s.push_back(a);
    ++mp_count[a];
  }
  REP(i,M){
    ll b,c; cin>>b>>c;
    s.push_back(c);
    mp_count[c] += b;
  }
  sort(ALL(s),greater<ll>());
  ll card = 0;
  ll score = 0;
  ll idx = 0;
  ll n_pre = -1;
  ll n;
  while(1){
    n = s[idx];
    if(n==n_pre){ ++idx; continue;}
    if(mp_count[n]+card<=N){
      score += mp_count[n]*n;
      card += mp_count[n];
    }else{
      score += (N-card)*n;
      break;
    }
    n_pre = n;
    ++idx;
  }
  cout << score;
  
}

Measured memory_bytes: 14320
#include <bits/stdc++.h>
using namespace std;
#define maxn 200015
#define ull unsigned long long
char s[maxn];
ull a[30];
int main()
{
	scanf("%s",s+1);
	ull n=strlen(s+1),ans=0;
	ans=(ull)n*(n-1)/2+1;
	for (int i=1;i<=n;i++)
	{
		a[s[i]-'a']++;
	}
	for (int i=0;i<26;i++) ans=ans-(ull)(a[i]*(a[i]-1)/2);
	cout<<ans<<endl;
}


Measured memory_bytes: 384
#include<cstdio>
#include<vector>
#include<algorithm>
struct Edge{
    int u,v;
    long long c;
    Edge(int u = 0,int v = 0,long long c = 0):
    u(u),v(v),c(c){}
};
std::vector<Edge>g[100005];
std::vector<int>block;
long long x[100005];
int vis[100005];
Edge e[100005];
int p[100005];
long long sumX[100005];
int used[100005], fake[100005];

void dfs(int u){
    vis[u] = 1, block.push_back(u);
    for(int i = 0; i < (int)g[u].size();i++){
        int v = g[u][i].v;
        if(!vis[v]){
            dfs(v);
        }
    }
}

int cmp(Edge a,Edge b){ return a.c<b.c; }

int find(int u){
    if(p[u]==u) return u;
    else return p[u] = find(p[u]);
}

int solve(int n){
    int size = 0;
    for(int i = 0; i < n; i++){
        int u = block[i];
        p[u] = u;
        sumX[u] = x[u];
        used[u] = fake[u] = 0;
        for(int j = 0; j < (int)g[u].size(); j++){
            int v = g[u][j].v;
            if(v>u) e[++size] = g[u][j];
        }
    }
    std::sort(e+1,e+1+size,cmp);
    int ans = 0;
    for(int i = 1; i <= size; i++){
        int x = find(e[i].u), y = find(e[i].v); 
        long long c = e[i].c;
        if(x==y){
            if(c<=sumX[x]){
                used[x]++;
                ans++;
            }
            else fake[x]++;
        }
        else{
            long long sumXX = sumX[x]+sumX[y];
            if(c<=sumXX){
                ans = ans+fake[x]+fake[y]+1;
                used[y] = used[x]+used[y]+fake[x]+fake[y]+1;
                fake[y] = 0;
                sumX[y] += sumX[x];
                p[x] = y;
            }
            else{
                used[y] += used[x];
                fake[y] += fake[x]+1;
                sumX[y] += sumX[x];
                p[x] = y;
            }
        }
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    long long sum = 0;
    for(int i = 1; i <= n; i++) scanf("%lld",&x[i]), sum += x[i];
    for(int i = 0; i < m; i++){
        int u,v;
        long long c;
        scanf("%d%d%lld",&u,&v,&c);
        g[u].push_back(Edge(u,v,c));
        g[v].push_back(Edge(v,u,c));
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){ 
            block.clear();
            dfs(i);
            /*for(int j = 0; j < (int)block.size(); j++){
                printf("%d ",block[j]);
            }*/
            int add = solve((int)block.size());
            ans += add;
        }
    }
    printf("%d\n",m-ans);
    return 0;
}


Measured memory_bytes: 19784
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC126_C_Dice_and_Coin
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
			int n = input[0];
			int k = input[1];
			int score = 0;
			double ans = 0;

			for (int i = 1; i <= n; i++)
			{
				double div = 1.0;
				score = i;
				while(score < k)
				{
					score *= 2;
					div /= 2.0;
				}

				ans += div;
			}

			ans /= n;
			Console.WriteLine(ans.ToString());
		}
	}
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
#define lint long long
#define inf 100000000000000000
#define mod 1000000007
#define MAX 100005
#define pb push_back
#define vit vector<int>::iterator
typedef pair<int,int> pii;
map<int,int>M;
vector<int> V[MAX];
int A[MAX];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int a=1;a<=100;a++){
        for(int b=1;b<=100;b++){
            for(int c=1;c<=150;c++){
                int sum=a*a+b*b+c*c+a*b+b*c+c*a;
                if(sum<=n)
                    A[sum]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<A[i]<<endl;
    return 0;
}


Measured memory_bytes: 5980
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

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

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr ll LNF = 1e18+7;

constexpr int INF = 1e9+7;

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

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h,w; cin >> h >> w;
    vector<string> s(h);
    rep(i,0,h) cin >> s[i];
    rep(i,0,h){
        rep(j,0,w){
            if(s[i][j]=='#'){
                cout << '#';
                continue;
            }
            int count = 0;
            rep(k,0,8){
                int dh = i + dy[k];
                int dw = j + dx[k];
                if(0<= dh && dh < h && 0<= dw && dw<w && s[dh][dw]=='#'){
                    count++;
                }
            }
            cout << count;
        }
        cout << '\n';
    }
}

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

typedef unsigned long long ll;
const ll MD = 1000000007;
ll n;
ll dp[100005][2];
vector<vector<ll> > adj;
bool seen[100005];

void dfs(ll v) {
    seen[v] = true;
    for (ll p : adj[v]) {
        if (!seen[p]) {
            dfs(p);
            dp[v][0] *= (dp[p][0] % MD + dp[p][1] % MD) % MD;
            dp[v][0] %= MD;
            dp[v][1] *= dp[p][0] % MD;
            dp[v][1] %= MD;
        }
    }
}

int main() {
    cin >> n;
    adj.resize(100005);
    for (ll i = 0; i < n-1; i++) {
        ll x, y; cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (ll i = 0; i < 100005; i++) {
        dp[i][0] = 1ULL;
        dp[i][1] = 1ULL;
    }
    dfs(0);
    cout << (dp[0][0] + dp[0][1]) % MD << "\n";
    return 0;
}


Measured memory_bytes: 11520
#include <iostream>
#include <vector>
#include <map>

using std::cout;
using std::endl;
using std::cin;

int main(int argc, char* argv[])
{
  int n, m;
  cin >> n >> m;

  if(n == m) { cout << "Yes" << std::endl;}
  else{ cout << "No" <<endl;}
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel.Design;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
using System.Xml.Schema;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<int> Slist() {
            var t = ReadLine();
            if (t.Trim().Length == 0) return new List<int>();
            return new List<int>(t.Split().Select(int.Parse)); }
        static void Main(string[] args)
        {
            var r = Sarray()[0];
            WriteLine(r * r);
        }
    }
}


Measured memory_bytes: 18856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	int n;cin>>n;
	int a,b,c,d;cin>>a>>b>>c>>d;
	string s;cin>>s;
	s='#'+s+'#';

	//b,c,dの位置関係がわからない
	//b<c<d or c<b<d or b<d<c
	bool chk=1;
	if(c==d) chk=0;
	else {
		for(int i=a;i<=max(c,d)-1;i++){
			if(s[i]=='#'&&s[i+1]=='#') chk=0;
		}
		if(c>d){
			bool chk2=1;
			for(int i=b;i<=d;i++){
				if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.'){
					chk2=0;
				}
			}
			if(chk2) chk=0;
		}
	}
	if(chk) cout<<"Yes"<<"\n";
	else cout<<"No"<<"\n";
}

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

// 文字列を探索しても良いが, 文字列長が3で固定でRかSのみなので,
// 2^3 = 8通りしかなく, if文を8個書けば済む.
// Rの個数ではなく連続数なので注意

int main() {
  string s;
  cin >> s;
  
  int ans = 0;
  if (s == "RRR") ans = 3;
  if (s == "RRS") ans = 2;
  if (s == "RSR") ans = 1;
  if (s == "SRR") ans = 2;
  if (s == "RSS") ans = 1;
  if (s == "SSR") ans = 1;
  if (s == "SRS") ans = 1;
  if (s == "SSS") ans = 0;
  
  cout << ans << endl;
}


Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdarg>
using namespace std;
int main(){
    int N, Y;
    cin >> N >> Y;
    for(int i = 0; i <= N; i ++){
        for(int j = 0; j <= N-i; j ++){
            int k = N - i - j;
            if (1000 * i + 5000 * j + 10000 * k == Y){
                printf("%d %d %d\n", k, j, i);
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
l=[0]
s=input()
cnt=0
for c in s:
  if (len(l)%2) ^ (c=='0'):
    cnt+=1
  else:
    l.append(cnt)
    cnt+=1
l.append(cnt)
if len(l)%2:
  l.append(cnt)
#print(l)
k = min(k,(len(l)-1)//2)
#print(l,k)
ans = 0
for i in range(0,len(l)-2*k-1,2):
  ans = max(ans,l[i+2*k+1]-l[i])
print(ans)

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

// V??????, NV???????´???°, def????????????, comp???????????¢??°
template<class V, int NV> class SegTree {
public:
	vector<V> val;
	static V const def = (1LL<<31)-1;
	V comp(V l, V r) { return min(l, r); };

	SegTree() { val = vector<V>(NV * 2, def); };
	V getval(int x, int y, int l = 0, int r = NV, int k = 1) {	// [x,y)
		if (r <= x || y <= l) return def;
		if (x <= l && r <= y) return val[k];
		return comp(getval(x, y, l, (l + r) / 2, k * 2), getval(x, y, (l + r) / 2, r, k * 2 + 1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry] = v;
		while (entry>1) entry >>= 1, val[entry] = comp(val[entry * 2], val[entry * 2 + 1]);
	}
};

int main()
{
	int n, q; cin >> n >> q;
	SegTree<ll, 1<<20> st;
	rep(i, 0, q)
	{
		int c, x;
		ll y;
		cin >> c >> x >> y;

		if (c == 0)
		{
			st.update(x, y);
		}
		else
		{
			cout << st.getval(x, y+1) << endl;
		}
	}
}

Measured memory_bytes: 19208
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ll long long int
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define F first
#define S second
#define mset(x,v) memset(x, v, sizeof(x))
#define left(x) 2*x
#define right(x) (2*x) + 1
#define ALL(t) (t).begin(),(t).end() 
#define ret return 0
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define rev(s) reverse(s.begin(),s.end())
#define WL(t) while(t --)
int main()
{
               boost;
               string s,fin="";
               cin>>s;
               int yr,mm,day,cnt=0;
               forn(i,s.size())
               {
                     if(s[i]=='/')
                     {
                           cnt++;
                           if(cnt==1)
                           {
                                 yr=stoi(fin);
                           }
                           else if(cnt==2)
                           {
                                 mm=stoi(fin);
                           }
                           fin.clear();
                     }
                     else
                     fin+=s[i];
               }
               day=stoi(fin);
               //cout<<yr<<" "<<mm<<" "<<day<<endl;
               if(yr<=2019 && mm<=4 && day<=30)
               cout<<"Heisei"<<endl;
               else
               cout<<"TBD"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(a); i++)
typedef long long ll;
template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

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

const ll inf = 1LL<<60;

int main()
{
  ll h,w,k; cin>>h>>w>>k;
  vector<string> c(h);
  rep(i, h) cin>>c[i];

  ll ans = 0;
  for (int hbits=0; hbits<(1<<h); hbits++) {
    for (int wbits=0; wbits<(1<<w); wbits++) {
      ll sum = 0;
      for (int i=0; i<h; i++) {
        if (((hbits>>i)&1) == 0) continue;
        for (int j=0; j<w; j++) {
          if (((wbits>>j)&1) == 0) continue;
          if (c[i][j] == '#') sum++;
        }
      }
      if (sum == k) ans++;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)	
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define double long double
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = pow(10,18);
ll modulo = 998244353  ;
#define MAX (int)(pow(10,6)+ 10)
 
void deal(){
	ll s;
	cin>>s;
	ll sq = sqrt(s);
	if(sq * sq == s){
		cout<<"0 0 0 "<<sq<<" "<<sq<<" "<<sq;
		return;
	}	
	else{
		ll dif = (sq+1)*(sq+1) - s;
		if(dif>=sq){
			cout<<sq+1<<" "<<dif-sq<<" "<<1<<" "<<sq+1<<" "<<0<<" "<<1;
		}
		else{
			cout<<sq+1<<" "<<dif<<" "<<1<<" "<<sq+1<<" "<<0<<" "<<0;
		}
	}
}

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

/*

4 6
4 8 7 8
1 2 4
2 1 2 2
1 3 4
2 1 1 8
1 1 3
1 1 4

acacabbbbbbbacc

cccbbbaaa
*/

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;
const int MAX_N = 200000;
vector<int> to [MAX_N];
int from [MAX_N],outdeg [MAX_N],grundy [MAX_N] [2];
vector<int> G [MAX_N * 2],rG [MAX_N * 2];
int cmp [MAX_N * 2];
bool used [MAX_N * 2];

void dfs(int curr,vector<int>& po)
{
	used [curr] = true;
	for(const auto& it : G [curr]) if(used [it] == false){
		dfs(it,po);
	}
	po.push_back(curr);
}

void rdfs(int curr,int k)
{
	used [curr] = true;
	cmp [curr] = k;
	for(const auto& it : rG [curr]) if(used [it] == false){
		rdfs(it,k);
	}
}

void scc()
{
	memset(used,0,sizeof(used));
	vector<int> po;
	int k = 0;
	FOR(i,0,N * 2) if(used [i] == false){
		dfs(i,po);
	}
	memset(used,0,sizeof(used));
	for(int i = int(po.size()) - 1;i >= 0;i--) if(used [po [i]] == false){
		rdfs(po [i],k++);
	}
}

void add_edge(int from,int to)
{
	G [from].push_back(to);
	rG [to].push_back(from);
}

int main()
{
	scanf("%d",&N);
	FOR(i,0,N){
		int p;
		scanf("%d",&p);
		p--;
		to [p].push_back(i);
		from [i] = p;
		outdeg [p]++;
	}

	queue<int> q;
	FOR(i,0,N) if(outdeg [i] == 0) q.push(i);
	
	memset(grundy,-1,sizeof(grundy));
	while(q.empty() == false){
		int curr = q.front(); q.pop();
		set<int> st;
		for(const auto& it : to [curr]){
			st.insert(grundy [it] [0]);
		}
		grundy [curr] [0] = 0;
		while(st.count(grundy [curr] [0])) grundy [curr] [0]++;
		if(--outdeg [from [curr]] == 0) q.push(from [curr]);
	}

	FOR(i,0,N) if(grundy [i] [0] == -1){
		set<int> st;
		for(const auto& it : to [i]) if(grundy [it] [1] == -1){
			st.insert(grundy [it] [0]);
		}
		grundy [i] [0] = 0;
		while(st.count(grundy [i] [0])) grundy [i] [0]++;
		grundy [i] [1] = grundy [i] [0] + 1;
		while(st.count(grundy [i] [1])) grundy [i] [1]++;
	}

	FOR(i,0,N) if(grundy [i] [1] != -1){
		if(grundy [from [i]] [0] == grundy [i] [0]){
			add_edge(i,from [i] + N);
			add_edge(from [i] + N,i);
			add_edge(i + N,from [i]);
			add_edge(from [i],i + N);
		}
		else if(grundy [from [i]] [0] == grundy [i] [1]){
			add_edge(i,from [i]);
			add_edge(from [i],i);
			add_edge(i + N,from [i] + N);
			add_edge(from [i] + N,i + N);
		}
		else{
			add_edge(i,from [i]);
			add_edge(i + N,from [i]);
		}
	}
	scc();

	bool ans = true;
	FOR(i,0,N) ans &= cmp [i] != cmp [i + N];
	puts(ans ? "POSSIBLE" : "IMPOSSIBLE");

	return 0;
}


Measured memory_bytes: 64240
import numpy as np

D=int(input())
C=np.array(list(map(int,input().split())))
last_day=np.array([-1 for _ in range(26)])
satisfication=np.array([list(map(int,input().split())) for _ in range(D)])
 
for day in range(D):
    today_point_loss=C*(day-last_day)
    today_point=[0 for _ in range(26)]
    for kind in range(26):
        today_point[kind]=satisfication[day][kind]-sum(today_point_loss)+today_point_loss[kind]
 
    if day!=D-1:
        tmp_score=-1*float("inf")
        for kind in range(26):
            nday_point_loss=C*((day+1)-last_day)
            nday_point=[0 for _ in range(26)]
            
            for nkind in range(26):
                if kind!=nkind:
                    nday_point[nkind]=satisfication[day+1][nkind]-sum(nday_point_loss)+nday_point_loss[nkind]
                else:
                    nday_point[nkind]=satisfication[day+1][nkind]-sum(nday_point_loss)+C[nkind]
 
                if today_point[kind]+nday_point[nkind]>tmp_score:
                    tmp_score=today_point[kind]+nday_point[nkind]
                    out=kind
    else:
        out=np.argmax(today_point)
 
    last_day[out]=day
    print(out+1)

Measured memory_bytes: 27436
countStr = {}
maxKeys = []

n = int(input())

for i in range(n):
    s = input()
    countStr.setdefault(s, 0)
    countStr[s] = countStr[s] + 1

maxValue = max(countStr.values())

countStr = list(countStr.items())

for i in countStr:
    if i[1] == maxValue:
        maxKeys.append(i[0])

for i in (sorted(maxKeys)):
    print(i)


Measured memory_bytes: 41560