akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

char line[301];

class rectangle {
	int h; // heigt of rectangle
	int w; // width of rectangle
public:
	int setheight(int height);
	int setwidth(int width);
	int getheight(void);
	int getwidth(void);
	char* linepaint(int hei);
	char* FramePrint(int hei);
};

int rectangle::setheight(int height) {
	if(height >= 3 && height <= 300){
		h = height;
		return 0;
	} else {
		h = -1;
		return -1;
	}
}
int rectangle::setwidth(int width) {
	if(width >= 3 && width <= 300){
		w = width;
		return 0;
	} else {
		w = -1;
		return -1;
	}
}
int rectangle::getheight(void) {
	if(h >= 3 && h <= 300)
		return h;
	else
		return -1;
}
int rectangle::getwidth(void) {
	if(w >=3 && w <= 300)
		return w;
	else
		return -1;
}

char* rectangle::linepaint(int height) {
	//char line[301];
	if(h >= 3 && h <= 300 && w >=3 && w <= 300) {
		if(height >= 0 && height <= h){
			for(int i=0;i<w;i++)
				line[i] = '#';
			line[w]='\0';
			return line;
		} else {
			line[0]='\0';
			return  line;
		}
	} else {
		line[0]='\0';
		return line;
	}
}

char* rectangle::FramePrint(int height) {
	//char line[301];
	if(h >= 3 && h <= 300 && w >=3 && w <= 300) {
		if(height >= 0 && height <= h){
			for(int i=0;i<w;i++){
				if(i==0 || i==w-1)
					line[i] = '#';
				else
					line[i] = '.';
			}
			line[w]='\0';
			return line;
		} else {
			line[0]='\0';
			return  line;
		}
	} else {
		line[0]='\0';
		return line;
	}
}

int main() {
	int h,w,i=0,n;
	class rectangle x[1000];

	while((cin >> h >> w) && !(h ==0 && w == 0)){
		x[i].setheight(h);
		x[i].setwidth(w);
		i++;
	}
	n=i;
	for(i=0;i<n;i++){
		h=x[i].getheight();
		for(int j=0;j<h;j++){
			if(j==0 || j==h-1)
				cout << x[i].linepaint(j) << endl;
			else
				cout << x[i].FramePrint(j) << endl;
		}
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
int n,a[maxn];
vector<int> E[maxn];
void dfs(int x,int p){
    if(E[x].size() == 1)return;
    long long sum = 0;
    long long mx = 0;
    for(int i=0;i<E[x].size();i++){
        int v = E[x][i];
        if(v==p)continue;
        dfs(v, x);
        sum += a[v];
        mx = max(1ll*a[v], mx);
    }
    if(a[x]>sum||sum>2*a[x]){
        cout<<"NO"<<endl;
        exit(0);
    }
    int k=sum-a[x];
    if(k>sum-mx){
        cout<<"NO"<<endl;
        exit(0);
    }
    a[x]-=k;
}
int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d", &x, &y);
        x--,y--;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    if(n==2){
        if(a[0]==a[1])puts("YES");
        else puts("NO");
        return 0;
    }
    int v=0;
    while(E[v].size() == 1) v++;
    dfs(v, -1);
    if(a[v]==0)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


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

int N, u, v;
vector<int> adj[100000];

void dfs(int now, int dist, int prev, vector<int> & vec){
  vec[now] = dist;
  for(auto next: adj[now]){
    if(next == prev){
      continue;
    }
    dfs(next, dist + 1, now, vec);
  }
}
    

int main(){
  cin >> N >> u >> v;
  u--; v--;
  for(int i = 0; i < N - 1; i++){
    int a, b;
    cin >> a >> b;
    adj[a - 1].push_back(b - 1);
    adj[b - 1].push_back(a - 1);
  }

  vector<int> dist_from_u (N, -1), dist_from_v(N, -1);
  dfs(u, 0, -1, dist_from_u);
  dfs(v, 0, -1, dist_from_v);

  int ans = 0;
  for(int i = 0; i < N; i++){
    if(dist_from_u[i] < dist_from_v[i]){
      ans = max(ans, dist_from_v[i] - 1);
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 11648
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
  int d,s,t;
  cin >> d >> t >> s;
  if(s * t >= d) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
	return 0;
}

Measured memory_bytes: 3128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			String a = scanner.nextLine();
			if (a.equals("0"))
				break;
			int sum = 0;
			for (char b : a.toCharArray()) {
				sum += Integer.parseInt(String.valueOf(b));
			}
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 17604
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

//??¨????????????????????????
//n??\????????£??´??°????´???°???????????°???????????????is_prime[]???????´?
void eratos(int n, bool is_prime[]) {
	fill(is_prime, is_prime + n + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i*i <= n; i++) {
		if (is_prime[i]) {
			int j = i + i;
			while (j <= n) {
				is_prime[j] = false;
				j = j + i;
			}
		}
	}
}

static signed char c[1050][1050]; //?´???° or ????????° or ?´???´?????????
static pii dp[1050][1050]; //?´???°?´???´????????° ??????????????????????´???°?´???´????????§??????
static bool a[1050][1050]; //?´???´?????¢?´¢??????????????????
static int num[1050][1050]; //xy??§?¨??????????????????´??°
pii dfs(int x, int y) {
	if (c[x][y] == -1)return pii(0, 0);
	if (a[x][y])return dp[x][y];
	a[x][y] = true;


	pii l = dfs(x - 1, y + 1);
	pii b = dfs(x, y + 1);
	pii r = dfs(x + 1, y + 1);

	//cout << x << " " << y << endl;
	//cout << l << " " << d << " " << r << endl;

	pii ret = max(b, max(l, r));
	int second = (ret.second == 0) ? ((c[x][y] == 1) ? num[x][y] : 0) : ret.second;
	return dp[x][y] = pii(
		ret.first + c[x][y],
		second
	);
}

#define MAX 1000001

int main() {
	static bool is_prime[MAX];
	eratos(MAX, is_prime);
	int O = 505;
	for (int m, n; cin >> m >> n&&m;) {
		memset(c, -1, sizeof(c));
		memset(dp, 0, sizeof(dp));
		memset(a, false, sizeof(a));
		int sx, sy;
		int x = O, y = O;
		int p = 1;
		for (int i = 1; p <= m;) {
			for (int j = 0; j < i; j++) {
				num[x][y] = p;
				if (p == n)sx = x, sy = y;
				c[x++][y] = (p <= m) ? is_prime[p] : -1;
				p++;
			}
			for (int j = 0; j < i; j++) {
				num[x][y] = p;
				if (p == n)sx = x, sy = y;
				c[x][y--] = (p <= m) ? is_prime[p] : -1;
				p++;
			}
			i++;
			for (int j = 0; j < i; j++) {
				num[x][y] = p;
				if (p == n)sx = x, sy = y;
				c[x--][y] = (p <= m) ? is_prime[p] : -1;
				p++;
			}
			for (int j = 0; j < i; j++) {
				num[x][y] = p;
				if (p == n)sx = x, sy = y;
				c[x][y++] = (p <= m) ? is_prime[p] : -1;
				p++;
			}
			i++;
		}

		//for (int y = 490; y < 520; y++) {
		//	for (int x = 490; x < 520; x++) {
		//		cout << b[x][y];
		//	}
		//	cout << endl;
		//}
		pii ans = dfs(sx, sy);
		cout << ans.first << " " << ans.second << endl;;
	}
	return 0;
}

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

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

int main() {
    string s;
    while (cin >> s) {
        if (s == "#") break;
        vector<string> str;
        rep(i, s.size()) {
            if (s[i] == 'n') {
                i += 4;
                str.push_back("north");
            }
            else if (s[i] == 'w') {
                i += 3;
                str.push_back("west");
            }
        }
        reverse(str.begin(), str.end());
        int a = 0, n = 0;
        rep(i, str.size()) {
            if (str[i] == "north") {
                if (i == 0) a = 0;
                else a = a*2-90;
            }
            else {
                if (i == 0) a = 90;
                else a = a*2+90;
            }
        }
        n = pow(2,str.size()-1);
        int tmp = __gcd(a, n);
        if (tmp <= 1 or n/tmp <= 1) {
            cout << a/tmp << endl;
        }
        else {
            cout << a/tmp << "/" << n/tmp << endl;
        }
    }
}



Measured memory_bytes: 3304
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
using namespace std;
#define ll long long
#define INF 1000000007
using P = pair<int, int>;
vector<int> s={357,375,537,573,735,753};
void seiri(){
    for(int i=1;i<s.size();i++){
        if(s[i]==s[i-1]){
            s.erase(s.begin()+i);
            i--;
        }
    }
    return;
}
int main(){
    int n;
    cin>>n;
    int b=0;
    int c;
    for(int i=4;i<10;i++){
        c=(int)s.size();
        for(int j=b;j<c;j++){
            for(int k=0;k<i;k++){
                s.push_back(s[j]/(int)pow(10,k)*pow(10,k+1)+3*pow(10,k)+s[j]%(int)(pow(10,k)));
                s.push_back(s[j]/(int)pow(10,k)*pow(10,k+1)+5*pow(10,k)+s[j]%(int)(pow(10,k)));
                s.push_back(s[j]/(int)pow(10,k)*pow(10,k+1)+7*pow(10,k)+s[j]%(int)(pow(10,k)));
            }
        }
        b=c;
        sort(s.begin(),s.end());
        seiri();
    }
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]<=n)ans++;
    }
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 1276
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;

int n;
bool vis[15];
char s[15];
void dfs(int x){
    if(x == 0){
        for(int i = n; i > 0; i--){
            cout << s[i];
        }
        cout << endl;
        return;
    }
    for(int i = 1; i <= 26; i++){
        if(vis[i]){
            s[x] = 'a' + i - 1;
            dfs(x - 1);
        }else if(vis[i - 1]){
            s[x] = 'a' + i - 1;
            vis[i] = true;
            dfs(x - 1);
            vis[i] = false;
            break;
        }
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i) s[i] = 'a';
    vis[0] = 1;
    dfs(n);
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>
#include <string.h>

int main(void) {
	int i, j;
	int number, lmnumber, lmword, swap, count;
	char str[500][33];
	int sstr[500];
	
	i = j = lmnumber = number = 0;
	while (str[j][i] = getchar()) {
		lmnumber = i > lmnumber ? i : lmnumber;
		if( str[j][i] == ' ') {
			str[j][i] = '\0';
			j++;
			i = -1;
		}
		else if( str[j][i] == '\n') {
			str[j][i] = '\0';
			break;
		}
		i++;
	}
	number = j + 1;
	for (i = 0; i < number; i++)
		sstr[i] = i;
	for (i = number; i > 1; i--)
		for (j = 0; j < i - 1; j++)
			if( strcmp(str[sstr[j]], str[sstr[j+1]]) == 1) {
				swap = sstr[j];
				sstr[j] = sstr[j+1];
				sstr[j+1] = swap;
			}
	for (i = j = count = 0; i < number; i++) {
		if( strlen(str[i]) == lmnumber)
			lmword = i;
		if( strcmp(str[sstr[i]], str[sstr[i+1]]) == 0) {
			if( j == 0)
				j = 2;
			else
				j++;
			count = j > count ? sstr[i] : count;
		}
		else
			j = 0;
	}
	printf("%s %s\n", str[count], str[lmword]);
	return 0;
}

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

int dice(int x, int y){
  int cnt = 0;
  while(x<y){
    x *= 2;
    cnt++;
  }
  return cnt;
} 

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

  vector<int> c(N);
  for(int i=1; i<N+1; i++){
    c[i] = dice(i,K);
    
  }

  double sum;
  for(int i=1; i<N+1; i++){
    sum += (1.0/N)*pow((1.0/2.0),c[i]);
  }

cout << fixed << setprecision(12) << sum << endl;

}

Measured memory_bytes: 640
import sys
from math import atan2, pi

n = int(input())
angles = []
engines = []
pi2 = 2 * pi
for i, line in enumerate(sys.stdin):
    x, y = map(int, line.split())
    angle = atan2(y, x)
    angles.append((angle, i))  # -pi~pi
    angles.append((angle + pi2, i))  # pi~3pi
    engines.append(x + y * 1j)
angles.sort()

r = 0
tmp = 0
total = sum(engines)
ans = 0
for l in range(n):
    angle, i = angles[l]
    limit = angle + pi - 1e-9
    while angles[r][0] < limit:
        tmp += engines[angles[r][1]]
        r += 1
    ans = max(ans, abs(tmp), abs(total - tmp))
    tmp -= engines[i]
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    long long int N,M,X;
    cin>>N>>M>>X;
    vector<long long> costs(N);
    vector<vector<int> > matrix(N,vector<int>(M,0));
    for(int c=0;c<N;c++) {
        cin>>costs[c];
        for(int c2=0;c2<M;c2++) cin>>matrix[c][c2];
    }


    int res = 1e8;

    for(int c=0;c<(1<<N);c++) {
        int nbLibs = 0;
        vector<int> skills(M,0);
        for(int c2=0;c2<N;c2++) {
            if((1<<c2)&c) {
                nbLibs+=costs[c2];
                for(int c3=0;c3<M;c3++) {
                    skills[c3] += matrix[c2][c3];
                }
            }
        }
        bool isOk = true;
        for(int c2=0;c2<M;c2++) {
            if(skills[c2] < X) {
                isOk = false;
                break;
            }
        }
        if(isOk) {
            res = min(res, nbLibs);
        }
    }
    if(res == 1e8) {
        cout<<-1;
    } else {
        cout<<res;
    }

}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int inf=1e9+7;
const ll longinf=1LL<<60;

const int mx=200010;
const ll mod=1e9+7;

int n,k,l;
ll ans[mx];
int v[mx],r[mx];

int find(int x){
  if( v[x] != x){ v[x] = find(v[x]); }
  return v[x];
}
int findr(int x){
  if( r[x] != x){ r[x] = findr(r[x]); }
  return r[x];
}

void merge(int x, int y){
  x = find(x);
  y = find(y);
  v[y] = x;
}
void merger(int x, int y){
  x = findr(x);
  y = findr(y);
  r[y] = x;
}


int main() {
  cin >> n >> k >> l;
  for(int i=0; i<n; i++){v[i]=i;}
  for(int i=0,a,b; i<k; i++){ 
    cin >> a >> b;
    merge(a,b);
  }
  
  for(int i=0; i<n; i++){r[i]=i;}
  for(int i=0,a,b; i<l; i++){ 
    cin >> a >> b;
    merger(a,b);
  }
  

  map<P,int> mp;
  for(int i=1; i<=n; i++){ mp[{find(i),findr(i)}]++; }	//i-city sources. if source same, +1
//  for(int i=1; i<=n; i++){ cout << mp[{find(i),findr(i)}] << " "; }
  for(int i=1; i<=n; i++){ printf("%d ",mp[{find(i),findr(i)}]); }

  cout << endl; 
  return 0;
}  


Measured memory_bytes: 13568
import java.io.*;
import java.util.*;
 
public class Main {
  private static boolean debug = false;
  private static boolean elapsed = false;
 
  private static PrintWriter _err = new PrintWriter(System.err);
 
  private long sum;
 
  private void solve(Scanner sc, PrintWriter out) {
    String s = sc.nextLine();
 
    search(0, s, new boolean[s.length() - 1]);
 
    out.println(sum);
  }
  private void search(int d, String s, boolean[] b) {
    if (d == b.length) {
      calc(s, b);
      return;
    }
    for (int j = 0; j < 2; ++j) {
      b[d] = (j == 0);
      search(d + 1, s, b);
      b[d] = false;
    }
  }
  private void calc(String s, boolean[] b) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      sb.append(s.charAt(i));
      if (i < b.length && b[i]) {
        sum += Long.parseLong(sb.toString());
        sb = new StringBuilder();
      }
    }
    sum += Long.parseLong(sb.toString());
  }
  private long C(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    for (long i = r; i > 1; --i) {
      res /= i;
    }
    return res;
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();
 
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();
 
    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<ll,pll> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
const int DX[8]={-1,0,1,0,-1,-1,1,1},DY[8]={0,-1,0,1,-1,1,-1,1};

const int NPrime=3000000;
bool prime[NPrime+1];
vi EnumeratePrime(){
	fill(prime+2,prime+NPrime+1,true);
	vi a;
	for(int i=2;i<=NPrime;i++) if(prime[i]){
		a.emplace_back(i);
		for(int j=2*i;j<=NPrime;j+=i) prime[j]=0;
	}
	return a;
}
int n;

string s;

int main(){
//	EnumeratePrime();
	while(1){
		cin>>n;
		if(n==0) break;
		vi a(n),b(n);
		for(int i=1;i<n;i++){
			int I,x;
			cin>>I>>x;
			a[i]=a[I]+dx[x];
			b[i]=b[I]+dy[x];
		}
		int mx=inf,MX=-inf,my=inf,MY=-inf;
		for(int i=0;i<n;i++){
			mx=min(mx,a[i]);
			MX=max(MX,a[i]);
			my=min(my,b[i]);
			MY=max(MY,b[i]);
		}
		cout<<MX-mx+1<<' '<<MY-my+1<<endl;
	}
}


Measured memory_bytes: 3012
class Edge
  attr_accessor :dest, :weight
  def initialize dest, weight
    @dest = dest
    @weight = weight
  end
end


class Graph
  def initialize n
    @n = n
    @adjenceList = []
    n.times do |i|
      @adjenceList[i] = []
    end
  end

  def addEdge i, j, weight
    edge1 = Edge.new j, weight
    @adjenceList[i] << edge1

    # edge2 = Edge.new i, weight
    # @adjenceList[j] << edge2
  end

  def printMatrix
    matrix = []
    @n.times do |i|
      matrix[i] = []
      @n.times do |j|
        matrix[i][j] = 0
      end
    end

    @n.times do |i|
      @adjenceList[i].each do |edge|
        matrix[i][edge.dest] = 1
      end
    end

    matrix.each do |row|
      count = 0
      row.each do |i|
        if count == 0
           print i
           count = 1
        else
           print " ", i
        end
      end
      puts ""
    end
  end
end


count = 0
n = 0
edge_data = []
STDIN.each_line {|line|
  if count == 0
    count += 1
    n = line.to_i
    next
  end

  edge_data << line
}

graph = Graph.new n.to_i
edge_data.each do |edge|
  edge_array = edge.split " "
  count = 0
  vertex = 0
  edge_array.each do |input_data|
    if count == 0
      count += 1
      vertex = input_data.to_i
      next
    end

    if count == 1
      count += 1
      next
    end

    dest = input_data.to_i
    graph.addEdge vertex - 1, dest -1, 0
  end
end

graph.printMatrix



Measured memory_bytes: 6980
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long ll;

int main()
{
    FAST;
    
    ll a;
    cin>>a;
    
    ll ans = a+a*a+a*a*a;
    
    cout<<ans<<endl;


    return 0;
}



Measured memory_bytes: 3608
#include <cstdint>
#include <cstdlib>
#include <iostream>


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

  std::uint64_t n;
  std::cin >> n;

  std::uint64_t product = 1;
  constexpr std::uint64_t kMod = 1000000007;
  for (std::uint64_t i = 2; i <= n; i++) {
    product = (product * i) % kMod;
  }
  std::cout << product << std::endl;

  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
w,h,n = map(int,input().split())
w0 = h0 = 0

for i in range(n):
    x,y,a = map(int,input().split())
    if a == 1:
        w0 = max(x,w0)
    elif a == 2:
        w = min(x,w)
    elif a == 3:
        h0 = max(y,h0)
    elif a == 4:
        h = min(y,h)
w = max(0,w-w0)
h = max(0,h-h0)
print(w*h)

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <conio.h>
using namespace std;

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

#define rep(i,n)	for(ll i=0;i<(n);i++)
#define SZ(x) ((ll)x.size())
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define F first
#define S second
#define int ll
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll MOD = INT_MAX;
const double PI = acos(-1);

void openfile(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}


signed main(){
	IOS
	string s;	cin >> s;
	if(s == "AAA" || s == "BBB")	cout << "No\n";
	else	cout << "Yes\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<utility>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n)
#define MAX 100000
#define inf 1000000007
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main() {
    //cin高速化
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    ll s = a.size();
    b.erase(s);
    if(a == b){
        cout << "Yes" <<"\n";
    }else{
        cout << "No" <<"\n";
    }
	return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2147483647
#define lINF 9223372036854775807
#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long int ll;

ll n,W,w[111],v[111],m[111][111111];
ll dp(int i,int j){//番号,重さ
	if(m[i][j]!=-1)return m[i][j];
	if(i==n)return 0;
	
	ll sum=0;
	if(j<w[i]){
		sum=dp(i+1,j);
	}
	else{
		sum=max(dp(i+1,j),dp(i+1,j-w[i])+v[i]);
	}
	
	return m[i][j]=sum;
	
}

int main(){
	
	cin>>n>>W;
	for(int i=0;i<n;i++){
		for(int j=0;j<110000;j++){
			m[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	cout<<dp(0,W)<<endl;
	return 0;

}

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

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

const int maxn=5003;
const ll inf=0x3f3f3f3f3f3f3f3f;


struct data{
	int h,p;
}a[maxn];

bool cmp(data x,data y){
	return x.h+x.p<y.h+y.p;
}

ll dp[maxn][maxn];
int n;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&a[i].h,&a[i].p);
	sort(a+1,a+n+1,cmp);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			if(dp[i-1][j-1]>a[i].h)
				dp[i][j]=dp[i-1][j];
			else dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+a[i].p);
//			printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
		}
	}
	for(int i=n;i>=1;--i)
		if(dp[n][i]<inf){
			printf("%d\n",i);
			return 0;
		}
	return 0;
}



Measured memory_bytes: 195840
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll a,b,c;
  cin >> a >> b >> c;
  cout << a*b/2 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define pb          push_back
#define mp          make_pair
#define mt          make_tuple
#define get0(x)     (get<0>(x))
#define get1(x)     (get<1>(x))
#define get2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       9223372036854775807LL
#define LLMIN       -9223372036854775808LL
#define IMAX        2147483647
#define IMIN        -2147483648
typedef long long LL;
using namespace std;

LL Q,H,S,D,N;

int main(void){
    cin>>Q>>H>>S>>D>>N;
    N*=4;
    vector<tuple<double,LL,LL> > vt;
    vt.pb(mt(Q,1,Q));
    vt.pb(mt(H/2.0,2,H));
    vt.pb(mt(S/4.0,4,S));
    vt.pb(mt(D/8.0,8,D));
    sort(ALL(vt));
    // reverse(ALL(vt));
    LL ans=0;
    REP(i,4){
        // printf("N=%lld cospa=%lf value=%lld volume=%lld\n",N,get0(vt[i]),get2(vt[i]),get1(vt[i]));
        ans+=get2(vt[i])*(N/get1(vt[i]));
        N%=get1(vt[i]);
    }
    cout<<ans<<endl;
     return 0;
}


Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all(C) std::begin(C), std::end(C)

int32_t N;
int32_t x,y,t=0;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	while (N--)
	{
		int32_t x2, y2, t2;
		in >> t2 >> x2 >> y2 ;

		int32_t xd = x2 - x,yd=y2-y,td=t2-t;

		if (((std::abs(xd) + std::abs(yd)) & 1) != (td & 1)) {
			out << "No\n"; return 0;
		}
		if ((std::abs(xd) + std::abs(yd)) > td) {
			out << "No\n"; return 0;
		}

		x = x2; y = y2; t = t2;
	}
	out << "Yes\n";

	return 0;
}
#endif


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)
int g[3][3] , cnt1[3] , cnt2[3];
int main() {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   for(int i = 0 ; i < 3 ; ++i){
      for(int j = 0 ; j < 3 ; ++j){
         cin >> g[i][j];
      }
   }
   int n;
   cin >> n;
   for(int i = 0 ;  i < n ; ++i){
      int x;
      cin >> x;
      for(int j = 0 ; j < 3 ; ++j){
         for(int k = 0 ; k < 3 ; ++k){
            if(g[j][k] == x){
               cnt1[j]++ , cnt2[k]++;
               g[j][k] = -1;
            }
         }
      }
   }

   for(int i = 0 ; i < 3 ; ++i){
      if(cnt1[i] == 3 || cnt2[i] == 3){
         cout << "Yes\n";
         return 0;
      }
   }

   if(g[0][0] == -1 && g[1][1] == -1 && g[2][2] == -1){
      cout << "Yes\n";
      return 0;
   }
   if(g[2][0] == -1 && g[1][1] == -1 && g[0][2] == -1){
      cout << "Yes\n";
      return 0;
   }
   cout << "No\n";
}

Measured memory_bytes: 256
import numpy as np


H, W = map(int, input().split())
h, w = map(int, input().split())
table = np.array([[0 for i in range(W)] for j in range(H)])
ans = 0
for i in range(h):
    table[i] += 1
for i in range(H):
    table[i][:w] += 1
    ans += sum(table[i])
print((H*W)-(ans-(h*w)))


Measured memory_bytes: 12452
#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;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    ll weight;
    edge(int f,int t,ll 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 = __LONG_LONG_MAX__;

constexpr int INF = 1e9+7;

const double PI=3.14159265358979323846;


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 n; cin >> n;
    vector<string> s(n);
    rep(i,0,n) cin >> s[i];
    map<string,int> m;
    rep(i,0,n){
        m[s[i]]++;
    }
    int ans = 0;
    for(auto &x: m){
        ans++;
    }
    cout << ans << endl;
}

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

#define MAX 200000
#define SENTINEL 2000000000

int L[MAX / 2 + 2], R[MAX / 2 + 2];

long long merge(int A[], int n, int left, int mid, int right)
{
  long long cnt = 0;
  int n1 = mid - left;
  int n2 = right - mid;
  for (int i = 0; i < n1; i++)
  {
    L[i] = A[left + i];
  }
  for (int i = 0; i < n2; i++)
  {
    R[i] = A[mid + i];
  }
  L[n1] = R[n2] = SENTINEL;
  int i = 0, j = 0;
  for (int k = left; k < right; k++)
  {
    if (L[i] <= R[j])
    {
      A[k] = L[i++];
    }
    else
    {
      A[k] = R[j++];
      cnt += n1 - i;
    }
  }
  return cnt;
}

long long mergeSort(int A[], int n, int left, int right)
{
  int mid;
  long long v1, v2, v3;
  if (left + 1 < right)
  {
    mid = (left + right) / 2;
    v1 = mergeSort(A, n, left, mid);
    v2 = mergeSort(A, n, mid, right);
    v3 = merge(A, n, left, mid, right);
    return v1 + v2 + v3;
  }
  else
  {
    return 0;
  }
}

int main()
{
  int A[MAX], n;

  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> A[i];
  }

  long long ans = mergeSort(A, n, 0, n);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4676
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<n;(i)++)
#define all(a) (a).begin(),(a).end()
int main(){
  vector<int>a(3,0);
  rep(i,3)cin >> a[i];
  sort(all(a));
  rep(i,3){
    cout << a[i];
  if(i!=2)cout<<" ";
  if(i==2)cout<<endl;
  }
}

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

using namespace std;
int main(void) {
	int n; cin >> n;
	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i].first;
		v[i].second = i+1;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++)printf("%d ", v[i].second);
	return 0;
}



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

double area(int n){
	double r = 10, s = 0, rem = 360;

	for(int i=0;i<n;i++){
		double v;

		if(i == n-1){ v = rem; }
		else{ cin>>v; rem -= v; }

		double rad = M_PI * v / 180;
		s += r * r * sin(rad) / 2;
	}

	return s;
}

int main(void){
	int n,m;

	while(cin>>n && n){
		double s1 = area(n);

		cin>>m;
		double s2 = area(m);

		if(fabs(s1 - s2) < 0.00001) cout<<0<<endl;
		else if(s1 > s2) cout<<1<<endl;
		else cout<<2<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
D = int(input())
C = list(map(int, input().split()))

S = [list(map(int, input().split())) for _ in range(D)]

contest = [0 for _ in range(26)]
ans = 0

for i in range(D):
    t = int(input())
    contest[t-1] = i+1
    ans += S[i][t-1]
    for j, con in enumerate(contest):
        if con:
            ans -= C[j]*(i+1-con)
        else:
            ans -= C[j]*(i+1)
    print(ans)

Measured memory_bytes: 9388
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		while(true) {
		int h = sc.nextInt();
		int w = sc.nextInt();
		if(h == 0 || w == 0) break;
		for(int j = 0; j < w; j++)
			System.out.print("#");
		System.out.println();
		for(int l = 1; l < h-1; l++) {
			System.out.print("#");
			for(int j = 1; j < w-1; j++)
				System.out.print(".");
			System.out.print("#\n");
			}
		for(int j = 0; j < w; j++)
			System.out.print("#");
		System.out.println("\n");
		sc.nextLine();
		}
		sc.close();
	}
}



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

using std::cin;
using std::cout;
using std::vector;

int n, i;
vector<long long> a;
long long v, s, z;
const long long m = 1e9 + 7;

int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  a.reserve(n);
  for (i = 0; i != n; ++i) {
    cin >> v;
    s += v;
    a.push_back(v);
  }
  for (long long v : a) {
    z = (z + v * ((s - v) % m)) % m;
  }
  if (z & 1)
    z = (z + m) / 2 % m;
  else
    z /= 2;
  cout << z;
  return 0;
}


Measured memory_bytes: 4388
#include <climits>
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using PII = pair<int, int>;
int main() {
    // freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    vector<vector<int>> bracket(n, vector<int>(2));
    string s;
    stack<char> st;
    int L = 0, R = 0;
    int i = 0, j = n - 1;
    for(int k=0;k<n;k++) {
        cin >> s;
        // cout << s << endl;
        int l = 0, r = 0;
        for (auto &c : s) {
            if (c == ')' && !st.empty() && st.top() == '(') {
                st.pop();
                l--;
            } else {
                st.push(c);
                (c == '(' ? l : r)++;
            }
        }
        while(!st.empty()) st.pop();
        // cout << r << " " << l << endl;
        bracket[(r < l ? i++ : j--)] = {r, l};
        L += l, R += r;
    }
    if (L != R) {
        cout << "No" << endl;
        return 0;
    }
    // cout << i << " " << j << endl;
    sort(bracket.begin(), bracket.begin() + i,
         [](auto &a, auto &b) { return a[0] < b[0]; });
    sort(bracket.begin() + i, bracket.end(),
         [](auto &a, auto &b) { return a[1] > b[1]; });
    int match = 0;
    for (i = 0; i < n; i++) {
        if (match < bracket[i][0])
            break;
        match -= bracket[i][0];
        match += bracket[i][1];
    }
    cout << (i != n ? "No" : "Yes") << endl;
}

Measured memory_bytes: 57412
#include <bits/stdc++.h>
#define inf 1e15
using namespace std;
typedef long long ll;

struct union_find{
    union_find(int n){
        for(int i=0; i<=n; i++){
            par.push_back(i);
            depth.push_back(0);
            nNode.push_back(1);
        }
    }
    int find(int x){
        if(par[x]==x) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;

        if(depth[x] < depth[y]){
            par[x] = y;
            nNode[y]+= nNode[x];
        }else{
            par[y] = x;
            if(depth[x] == depth[y]) depth[x]++;
            nNode[x]+=nNode[y];
        }
    }
    bool isSame(int x, int y){
        return find(x) == find(y);
    }
    int getnNode(int x){
        return nNode[x];
    }

    private:
        vector<int> par, depth, nNode;
};

int main(){
    ll N, M;
    cin >> N >> M;
    vector<pair<int,int>> brid;
    for(int i=0; i<M; i++){
        int A, B;  cin >> A >> B;
        brid.push_back(make_pair(A, B));
    }
    reverse(brid.begin(), brid.end());

    union_find isl(N);
    vector<ll> ans(M,0);
    ans[0] = N*(N-1)/2;
    for(int i=1; i<M; i++){
        int A = brid[i-1].first;
        int B = brid[i-1].second;
        A = isl.find(A);
        B = isl.find(B);
        if(A==B) ans[i] = ans[i-1];
        else{
            ans[i] = ans[i-1] - isl.getnNode(A)*isl.getnNode(B);
        }
        isl.unite(A,B);
    }
    for(int i=M-1; i>=0; i--){
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 4724
#include<cstdio>
const int N=100+10;
char s[N];
int main()
{
	scanf("%s",s);
	for(int i=0;s[i];i++)
		if((i%2)&&s[i]=='R')
		{
			puts("No");
			return 0;
		}
		else if((i%2==0)&&s[i]=='L')
		{
			puts("No");
			return 0;
		}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mk make_pair
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()

using namespace std;

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

int main(){
	int n;
	cin >> n;
	vector <int> d(n);
	for(int i = 0; i < n; i++)
		cin >> d[i];
		
	int cnt = 0;
	for(int i1 = 0; i1 < n; i1++)
		for(int i2 = i1 + 1; i2 < n; i2++)
			for(int i3 = i2 + 1; i3 < n; i3++)
				if(d[i1] != d[i2] && d[i2] != d[i3] && d[i1] != d[i3])
					if(d[i1] < d[i2] + d[i3] && d[i2] < d[i1] + d[i3] && d[i3] < d[i2] + d[i1])
						cnt++;
	
	cout << cnt << endl;
	
	return 0;
}


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

using namespace std;
using namespace __gnu_pbds;

#define fr(i,j,n)   for(int i=j;i<(n);++i)
#define bk(i,j,n)   for(int i=j;i>=n;--i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl "\n"
#define MOD 1000000007
#define here(s)      cout<<s<<endl;
#define run ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>


typedef long long ll;


int main()
{
    run;
    ll h,a;
    cin>>h>>a;
    if(h%a)
    {
        cout<<h/a+1;
    }else{
    cout<<h/a;
    }




    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0)
    return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1; // 分母
  ll numerator = 1;   // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
private:
  vector<ll> parents;

public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) {
    return root(x) == root(y);
  }

  bool merge(ll x, ll y) {
    if (issame(x, y))
      return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry])
      swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) {
    return -parents[root(x)];
  }

private:
  ll root(ll x) {
    if (parents[x] < 0)
      return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

int main() {
  ll H, N;
  cin >> H >> N;

  vector<ll> A(N);
  vector<ll> B(N);
  for (ll i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }

  // 最初のi種類の魔法を使って、jの体力を削るときの使用MPの最小値
  vector<vector<ll>> dp(N + 1, vector<ll>(H + 1, 1000000000));
  dp[0][0] = 0;
  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j <= H; j++) {
      // 魔法iを使わない
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      // 魔法iを使う
      dp[i + 1][min(j + A[i], H)] = min(dp[i + 1][min(j + A[i], H)], dp[i + 1][j] + B[i]);
    }
  }

  cout << dp[N][H] << endl;
  return 0;
}


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

#define REP(i,n) for(int i=0;i<n;i++)

template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

int a[3][3];

int main(){
  REP(i,3)REP(j,3)cin>>a[i][j];
  int n;cin>>n;
  while(n--){
    int s;cin>>s;
    REP(i,3)REP(j,3)if(a[i][j]==s)a[i][j]=0;
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[i][j];
    if(!c)fin("Yes");
  }
  //コピペを3回していい感じにする
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[j][i];
    if(!c)fin("Yes");
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[j][j];
    if(!c)fin("Yes");
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[2-j][j];
    if(!c)fin("Yes");
  }
  fin("No");
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    long long n,y,i,j,k;
    scanf("%lld%lld",&n,&y);
    for(i=0;i<=n;i++){
        for(j=0;j<=n-i;j++){
            k = n-i-j;
            if(i*10000+j*5000+k*1000==y){
                printf("%lld %lld %lld",i,j,k);
                return 0;
            }
        }
    }
    printf("-1 -1 -1");
}

Measured memory_bytes: 1696
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  string s;
  s="";
  if(n==0){
    cout << 0 << endl;
  }
  else{
  while(n!=0){
    if(n>0){
      s=to_string(n%(-2))+s;
      n/=(-2);
    }
    else{
      s=to_string(-n%(-2))+s;
      n=(n-2+1)/(-2);
    }
  }
  cout << s << endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define repr(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n)
    {
        rep(i, n) par[i] = i;
    }

    int root(int x)
    {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    int same(int x, int y)
    {
        return root(x) == root(y);
    }
};

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

    string s; cin >> s;
    int k; cin >> k;
    vector<string> v;
    rep(i, s.size() - k + 1)
    {
        v.push_back(s.substr(i, k));
    }
    rep(i, k - 1)
    {
        v.push_back(s.substr(s.size() - i - 1));
    }
    sort(all(v));
    int n = min((int)v.size(), k);
    set<string> se;
    rep(i, n)
    {
        rep(j, v[i].size())
        {
            rep(_j, v[i].size() - j)
            {
                se.insert(v[i].substr(j, _j + 1));
            }
        }
    }
    auto itr = se.begin();
    rep(i, k - 1)
    {
        itr++;
    }
    cout << *itr << endl;

    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, L; cin >> N >> L;
  vector<int> A(N); REP(i, N) cin >> A[i];

  REP(i, N-1) {
    if (A[i] + A[i+1] >= L) {
      cout << "Possible" << endl;
      REP(j, i) {
        cout << j+1 << endl;
      }
      for (int j = N-1; j > i+1; j--) {
        cout << j << endl;
      }
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << "Impossible" << endl;

  return 0;
}


Measured memory_bytes: 1280
package main

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

func main() {
	var n int
	fmt.Scan(&n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		sc.Scan()
		x, _ := strconv.Atoi(sc.Text())
		m[x]++
	}

	if m[0] == n {
		fmt.Println("Yes")
		return
	}

	if n%3 != 0 {
		fmt.Println("No")
		return
	}

	switch len(m) {
	case 2:
		if m[0] == n/3 {
			fmt.Println("Yes")
			return
		}
	case 3:
		x := make([]int, 0, 3)
		for k, v := range m {
			if v != n/3 {
				fmt.Println("No")
				return
			}
			x = append(x, k)
		}
		if x[0]^x[1]^x[2] == 0 {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 6912
import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
{
	public static void main (String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int a = in.nextInt();
		int b = in.nextInt();
 
		long ans = 0;
		for(int i = 1; i <= n; ++i) {
			int s = sum(i);
			if(s >= a && s <= b)
				ans += i;
		}
 
		System.out.println(ans);
 	}
 
 	private static int sum(int n) {
 		int ret = 0;
 		while(n > 0) {
 			ret += n % 10;
 			n /= 10;
 		}
 
 		return ret;
 	}
}

Measured memory_bytes: 22608