akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;

public class CSharp{
    public static void Main(){
        Kyopuro chokudai = new Kyopuro();
	    chokudai.AtCoder();
	}
}

public class Kyopuro{

	string s;
	int k;
	
    public void AtCoder(){
		int p = 998244353;
        string[] input;
		input = Console.ReadLine().Split(' ');
		s = input[0];
		k = int.Parse(input[1]);
		
		int l = s.Length;
		List<int> a = new List<int>();
		int c = 0;
		a.Add(0);
		for (int i=l-1; i>-1; i--) {
			if (s[i] == '0') {
				a.Add(c);
				c = 0;
			} else {
				c++;
			}
		}
		int n = a.Count;
		a.Add(c);
		int m = 302;
		if (m > k) m = k;
		m++;

		long[][][] dp = new long[n+1][][];
		long[][][] cum2 = new long[n+1][][];
		long[][][] cum3 = new long[n+1][][];
		for (int i=0; i<=n; i++) {
			dp[i] = new long[m][];
			cum2[i] = new long[m][];
			cum3[i] = new long[m][];
			for (int j=0; j<m; j++) {
				dp[i][j] = new long[m];
				cum2[i][j] = new long[m];
				cum3[i][j] = new long[m];
			}
		}
		dp[0][0][0] = 1;
		cum2[0][0][0] = 1;
		cum3[0][0][0] = 1;

		for (int i=1; i<=n; i++) {
			for (int j=0; j<m; j++) {
				cum2[i-1][0][j] = dp[i-1][0][j];
				cum3[i-1][j][0] = dp[i-1][j][0];
				for (int h=1; h<m; h++) {
					cum2[i-1][h][j] = cum2[i-1][h-1][j] + dp[i-1][h][j];
					cum3[i-1][j][h] = cum3[i-1][j][h-1] + dp[i-1][j][h];
					cum2[i-1][h][j] %= p;
					cum3[i-1][j][h] %= p;
				}
			}
			for (int j=0; j<m; j++) {
				for (int h=0; h<m; h++) {
					if (h > j) continue;
					dp[i][j][h] += cum2[i-1][j][h];
					if (j - a[i] > 0) {
						dp[i][j][h] += p;
						dp[i][j][h] -= cum2[i-1][j-a[i]-1][h];
					}
					//dp[i][j][h] += cum3[i-1][j][j];
					if (h > 0) {
						//dp[i][j][h] += p;
						//dp[i][j][h] -= cum3[i-1][j][h-1];
						dp[i][j][h] += cum3[i-1][j][h-1];
					}
					dp[i][j][h] %= p;
				}
			}
		}

		long ans = 0;
		for (int i=0; i<m; i++) {
			ans += dp[n][i][i];
			ans %= p;
		}
		
		Console.WriteLine(ans);
    }
    public static void DebugWL(object x){ System.Diagnostics.Debug.WriteLine(x); }
}


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

int main() {
  int n; cin >> n;
  vector<int> p(n), q(n);
  for (int i = 0; i < n; i++) cin >> p[i];
  for(int i = 0; i < n; i++) q[i] = i+1;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (p[i] != q[i]) cnt++;
    if (cnt == 3) break;
  }
  if(cnt == 3) cout << "NO" << endl;
  else cout << "YES" << endl;
  return 0;
}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define chmax(s, t) s=max(s,t);
#define chmin(s, t) s=min(s,t); 

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

/*組み合わせ(Combination)*/
const ll CMAX = 1010000;
const ll CMOD = 1e9+7;
ll fac[CMAX], finv[CMAX], inv[CMAX];
// テーブルを作る前処理
void combinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (ll i = 2; i < CMAX; i++) {
		fac[i] = fac[i - 1] * i % CMOD;
		inv[i] = CMOD - inv[CMOD%i] * (CMOD / i) % CMOD;
		finv[i] = finv[i - 1] * inv[i] % CMOD;
	}
}
// 二項係数計算
ll comb(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % CMOD) % CMOD;
}

/*階乗*/
ll factorial(ll n){
    const ll FMOD = 1e9+7;
    ll ret = n;
    for(ll i=n-1;i>0;i--){
        ret*=i;
        ret%=FMOD;
    }
    return (ret?ret:1);
}


int main(){

    ll n; cin >> n;
    ld ans = 0;
    ll in;
    rep(i, n){
        cin >> in;
        ans += 1.0/(ld)in;
    }
    ans = 1.0/ans;

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

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

int cnt = 0;
vector<string> ret;
queue<string> backret;
void dfs(int i,vector<char>& v,map<char,int>& st,string& ans,const string& s) {
  if (i == s.size()){
    cnt++;
    backret.push(ans);
    while(backret.size() > 5){
      backret.pop();
    }
    if(ret.size() < 10)ret.push_back(ans);
    return;
  }
    
  string oldans = ans;
  char c = s[i];
  char nextc;

  nextc = c;
  if(st[nextc] > 0 || nextc == 'a'){
    st[nextc]++;v.push_back(nextc);
    ans += nextc;
    dfs(i+1,v,st,ans,s);
    ans = oldans;
    st[nextc]--;v.pop_back();
  }

  // ????????????????????????????????£??? 'a' <- 'b'
  nextc = c + 1;
  if(c != 'z' && st[nextc] == 0){
      st[nextc]++;v.push_back(nextc);
      ans += nextc;
      dfs(i+1,v,st,ans,s);
      ans = oldans;
      st[nextc]--;v.pop_back();
  }
}

bool solve(){
  string s;
  cin >> s;
  if(s == "#")return false;
  vector<char> v;
  map<char,int> st;
  string ans;
  cnt = 0;
  backret = queue<string>();
  ret = vector<string>();
  dfs(0,v,st,ans,s);
  cout << cnt << endl;
  if(cnt <= 10){
    for(int i=0;i<ret.size();i++){
      cout << ret[i] << endl;
    }
  }else{
    for(int i=0;i<5;i++){
      cout << ret[i] << endl;
    }
    while(!backret.empty()){
      cout << backret.front() << endl;
      backret.pop();
    }
  }
  return true;
}

int main(void) {
  while(solve()){}

  return 0;
}

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

using namespace std;
#define rep(j,n) for(int j=0;j<(n);j++)

using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
const int INF = 1001001001;

int main(int, char**)
{
    int k;
    cin >> k;

    string str;
    cin >> str;
    int s = str.size();
    int n = k + s;

    vector<mint> pw25(n+1);
    vector<mint> pw26(n+1);
    pw25[0] = pw26[0] = 1;
    rep(i, n) {
        pw25[i+1] = pw25[i] * 25;
        pw26[i+1] = pw26[i] * 26;
    }

    combination cmb(n+1);

    mint ans = 0;
    rep(i,n) {
        ll rm = n-i-1;
        if (rm > k) continue;
        ans += cmb(i,s-1) * pw25[k-rm] * pw26[rm];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 66732
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a;
    map<int,int> mp;
    set<int> st;
    for(int i=0;i<n;i++){
        cin>>a;
        if(mp.find(a)==mp.end())mp[a]=1;
        else mp[a]++;
        st.insert(a);
    }
    int ans=0;
    for(auto s=st.begin();s!=st.end();s++){
        //cout<<i<<endl;
        if(mp[*s]>*s)ans+=mp[*s]-*s;
        if(mp[*s]<*s)ans+=mp[*s];
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {

	int N, K;
	cin >> N >> K;

	int h;
	long long high[100000], dis;
	long long  ans = 1000000000;

	for (int i = 0; i < N; i++) {
		cin >> h;
		high[i] = h;
	}

	sort(high, high + N);

	//for (int i = 0; i < N; i++) {
	//	cout << high[i] << endl;
	//}
	
	for (int i = 0; i < N - K + 1; i++) {
		dis = high[i + K - 1] - high[i];
		//cout << dis << endl;
		ans = min(ans, dis);
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    while(a>=0 && c>=0){
        c -= b;
        if(c <= 0){
            printf("Yes\n");
            return 0;
        }
        a -= d;
        if(a <= 0){
            printf("No\n");
            return 0;
        }
    }
}


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

using namespace std;

int main() {

	string r,g,b;
	cin >> r >> g >> b;

	long n;
	n = (stol(r) * 100 + stol(g) * 10 + stol(b)) % 4;

	cout <<  (n==0? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
//ダイクストラ法:スタートから任意の地点での最短距離を求める
//計算量:(頂点+辺)log(頂点) 
//始点,終点,隣接リスト(pathlist[edge.A]=(edgeB,legth))-->距離(notfound:INFLL);
vector<long long> Dikstra(int start,vector<vector<pair<int,long long>>>&pathlist){
	int edge=pathlist.size();
	pair<long long, int> cerching;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; //start to distance,[ditance ,islandNo.]
	vector<long long> D(edge,INFLL); //distance (ans)
	vector<bool>had(edge,false);
	D[start] = 0;
	q.emplace(0LL, start);

	while (!q.empty()){
		cerching = q.top();
		q.pop();
		if (had[cerching.S] == false){
			had[cerching.S] = true;


			for (auto i = pathlist[cerching.S].begin(); i != pathlist[cerching.S].end(); i++){
				if (had[i->F] == false){
					chmin(D[i->F], (cerching.F) + (i->S));
					q.emplace(D[i->F], i->F);
				}
			}
		}
	}


return D;
}
int main(){
	int v,e,r;
	cin >>v>>e>>r;
	vector<vector<pair<int,ll>>>path(v);
	int s,t;
	ll d;
	rep(i,e){
		cin>>s>>t>>d;
		path[s].emplace_back(t,d);
	}
	vector<ll> ans=Dikstra(r,path);
	rep(i,v){
		if(ans[i]==INFLL){
			cout<<"INF"<<endl;
		}else{
			cout<<ans[i]<<endl;
		}
	}
}


Measured memory_bytes: 19392
import java.util.Scanner;

class Main{
 public static void main(String args[]){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int[] A = new int[N];
   boolean flag=true;
   
   for(int i=0;i<N;i++){
     A[i] = sc.nextInt();
     if(A[i]%2==0&&!(A[i]%3==0||A[i]%5==0)){
     	flag=false;
     }
   }
      
      
   if(flag){
     System.out.println("APPROVED");
   }else{
     System.out.println("DENIED");
   }
 
 }
}


Measured memory_bytes: 21844
#include<math.h>
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ll long long int
#define py printf("Yes\n")
#define pn printf("No\n")
#define in cin>>
using namespace std;
const int INF = 1001001001;

int main()
{
    int n;
    string ans="No";
    in n;
    int tmp=0,flag=n;
    while(flag>0)
    {
        tmp+=flag%10;
        flag/=10;
    }
    if(n%tmp==0)ans="Yes";
    cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int x;
    cin >> x;
    int ans = 0;
    ans += 1000 * (x / 500);
    x %= 500;
    ans += 5 * (x / 5);
    cout << ans << endl;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if((a==b && c==d)||(a==c && b==d)||(a==d && b==c)){
		printf("yes\n");
	}
	else{
		printf("no\n");
	}
	return 0;
}


Measured memory_bytes: 2140
#include <iostream>

using namespace std;

int main( void )
{
	int data = 0;
	cin >> data;
	while(data--) {
		int x1, y1, x2, y2, n;
		cin >> x1 >> y1 >> x2 >> y2 >> n;
		x2 += x1;
		y2 += y1;
		int count = 0;
		for(int i=0; i < n; ++i) {
			int xx, yy;
			cin >> xx >> yy;
			if(x1 <= xx && xx <= x2 &&
				y1 <= yy && yy <= y2)
			{
				++count;
			}
		}
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
using namespace std;
int main(){
    int N; cin >> N;
    vector<int> a(N+1);
    for(int i = 1; i <= N; i++) cin >> a[i];
    vector<int> b(N+1);
    for(int i = 1; i <= N; i++) cin >> b[i];
    vector<int> c(N);
    for(int i = 1; i <= N-1; i++) cin >> c[i];

    int ans = 0;

    for(int i = 1; i <= N; i++){
        ans += b[a[i]];
        if(i>=2){
            if(a[i] == a[i-1] + 1){
                ans += c[a[i-1]];
            }
        }
    }

    cout << ans <<endl;
}


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

int bubbleSort(int A[],int N){
  int sw=0;
  bool flag=1;
  for(int i=0;flag;i++){
    flag=0;
    for(int j=N-1;j>=i+1;j--){
      if(A[j]<A[j-1]){
        swap(A[j],A[j-1]);
        flag=1;
        sw++;
      }
    }
  }
  return sw;
}

int main(){
  int A[100],N,sw;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[i];
  }

  sw=bubbleSort(A,N);

  for(int i=0;i<N;i++){
    if(i)cout<<" ";
    cout<<A[i];
  }

  cout<<endl;
  cout<<sw<<endl;

  return 0;
}

Measured memory_bytes: 3084
#include<stdio.h>

int n,a;

int main(){
	scanf("%d",&n);
	while(n!=0){
		a=0;
		while(n!=1){
			if(n%2==0)n=n/2;
			else n=n*3+1;
			a++;
		}
		printf("%d\n",a);
		scanf("%d",&n);
	}
	
	return 0;
}

Measured memory_bytes: 0
from decimal import Decimal

def main():
 
    a, b, c = map(int, input().split())
    seki = a * b
    if c - (a + b + 2 * (Decimal(str(seki))**Decimal("0.5"))) > 0:
        print("Yes")
 
    else:
        print("No")
 
    return
 
if __name__ == '__main__':
    main()   
    

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> s(H + 2, vector<char>(W + 2, '.'));
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      cin >> s.at(i).at(j);
    }
  }
  
  string ans = "Yes";
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (s.at(i).at(j) == '#' &&
          s.at(i - 1).at(j) == '.' && s.at(i).at(j - 1) == '.' &&
          s.at(i).at(j + 1) == '.' && s.at(i + 1).at(j) == '.' ) {
        ans = "No";
        break;
      }
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
/**
 * Created by hiramekun at 20:47 on 2019-11-24.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll n;
    string s;
    cin >> n >> s;
    ll m = s.size();
    rep(i, m) {
        s[i] += n;
        if (s[i] > 'Z') s[i] -= 26;
    }
    cout << s << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
def t_check(a,b,c):
    if a + b > c:
        if b + c > a:
            if a + c > b: return True
    return False

def f_check(a_, b_, c_):
    tmp = []
    tmp.append(a_)
    tmp.append(b_)
    tmp.append(c_)
    sqrts = []
    for i in range(3):
        sqrts.append(tmp[i]**2)
    m = max(sqrts)
    s = sum(sqrts)

    if m == (s - m): return(0)
    if m > (s - m): return(2)
    if m < (s - m): return(1)
    
counter=[0,0,0]
    
while(1):
    input_f = input()

    t = input_f.split()
    fn, sn, tn = int(t[0]),int(t[1]),int(t[2])
    if t_check(fn,sn,tn):
        counter[f_check(fn,sn,tn)] += 1
    else: break
    
print(sum(counter),counter[0], counter[1], counter[2])


Measured memory_bytes: 5612
n = int(input())
s = input()

arr = []
R = len(list(filter(lambda x:x == 'R', s)))
G = len(list(filter(lambda x:x == 'G', s)))
B = len(list(filter(lambda x:x == 'B', s)))
tot = R*G*B

for i in range(n):
  for j in range(i+1, n):
    k = 2*j-i
    if k >= n:
      continue
    if (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
      tot -= 1

print(tot)


Measured memory_bytes: 9128
#include <iostream>
 
using namespace std;
 
int main()
{
    int n,W;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> W;
    long long F[n+1][W+1], v[n+1], w[n+1];
    for (int i=1; i<=n; i++)
    {
        cin >> w[i] >> v[i];
    }
    for (long long i=0; i<=n; i++) F[i][0]=0;
    for (long long j=0; j<=W; j++) F[0][j]=0;
    for (long long i=1; i<=n; i++)
    {
        for (long long j=1; j<=W; j++)
        {
            if (w[i]>j) F[i][j]=F[i-1][j];
            else F[i][j]=max(F[i-1][j], F[i-1][j-w[i]]+v[i]);
        }
    }
    cout << F[n][W];
    return 0;
}


Measured memory_bytes: 79232
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

#define rep(i,n)  for(int i = 0; i < (int)(n);    i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int A, B; std::cin >> A >> B;
  std::cout << A*B << std::endl;
  return 0;
}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int n;
int dp[100010];
int main() {
    cin >> n;
    dp[0] = 0;
    for(int i = 1; i <= 100000; ++i) dp[i] = 1e9+7;
    for(int i = 1; i <= n; ++i) {
        dp[i] = i;
        int j = 1;
        while(i-j >= 0) {
            dp[i] = min(dp[i], dp[i-j]+1);
            j*=6;
        }
        int k = 1;
        while(i-k >= 0) {
            dp[i] = min(dp[i], dp[i-k]+1);
            k*=9;
        }
    }

    cout << dp[n] << endl;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(){
    int n,s[100]={0};
	int max,min,max1,min1;
	int sum,i;

scanf("%d",&n);

do{
	max=0;
	min=100000;
	sum=0;
	sum=0;
    max1=0;
    min1=0;
	for (i=0;i<n;i++){
		scanf("%d",&s[i]);
		if(s[i]>max){
            max=s[i];
			max1=i;
		}
		if(s[i]<min){
			min=s[i];
            min1=i;
		}
	}
	for(i=0;i<n;i++){
		if(i!=max1&&i!=min1){
			sum+=s[i];
		}
	}
	printf("%d\n",sum/(n-2));
	scanf("%d",&n);
}while (n!=0);
return 0;
}

Measured memory_bytes: 1028
#include<stdio.h>
#include<stdlib.h>
#define N 10000
#define M -1

int n,Parent[N],Right[N],Left[N],D[N],H[N];

int GetDepth(int);
void SetDepth(int,int);
int Height(int);
int Sibling(int);
void Print(int);

int main(){
  int i,v,d,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    Parent[i]=Right[i]=Left[i]=M;
  }
  for(i=0;i<n;i++){
    scanf("%d",&v);
    scanf("%d",&l);
    scanf("%d",&d);
    Left[v]=l;
    Right[v]=d;
    if(l!=M){
      Parent[l]=v;
    }
    if(d!=M){
      Parent[d]=v;
    }
  }
  for(i=0;i<n;i++){
    if(Parent[i]==M){
      r=i;
    }
  }
  SetDepth(r,0);
  Height(r);
  for(i=0;i<n;i++){
    Print(i);
  }
  return 0;
}

int GetDepth(int u){
  int d=0;
  while(Parent[u]!=M){
    u=Parent[u];
    d++;
  }
  return d;
}

void SetDepth(int u,int p){
  D[u]=p;
  if(Right[u]!=M){
    SetDepth(Right[u],p+1);
  }
  if(Left[u]!=M){
    SetDepth(Left[u],p+1);
  }
}

int Height(int u){
  int a=0,b=0;
  if(Right[u]!=M){
    a=Height(Right[u])+1;
  }
  if(Left[u]!=M){
    b=Height(Left[u])+1;
  }
  return H[u]=(a>b?a:b);
}

int Sibling(int u){
  if(Parent[u]==M){
    return M;
  }
  if(Left[Parent[u]]!=u && Left[Parent[u]]!=M){
    return Left[Parent[u]];
  }
  if(Right[Parent[u]]!=u && Right[Parent[u]]!=M){
    return Right[Parent[u]];
  }
  return M;
}

void Print(int u){
  int i,de=0,c;
  printf("node %d: ",u);
  printf("parent = %d, ",Parent[u]);
  printf("sibling = %d, ",Sibling(u));
  if(Left[u]!=M){
    de++;
  }
  if(Right[u]!=M){
    de++;
  }
  printf("degree = %d, ",de);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);
  if(Parent[u]==M){
    printf("root\n");
  }
  else if(Left[u]==M && Right[u]==M){
    printf("leaf\n");
  }
  else{
    printf("internal node\n");
  }
}



Measured memory_bytes: 2104
#include <array>
#include <cassert>
#include <cstdio>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

bool solve(int h, int w, array<int, 26> cnt) {
    int r1 = (h % 2) * (w % 2);
    int r2 = (h % 2) * (w / 2) + (w % 2) * (h / 2);
    assert  ((h * w - 2 * r2 - r1) % 4 == 0);
    int r4 = (h * w - 2 * r2 - r1) / 4;
    for (int c = 0; r4 --; ) {
        while (c < 26 and cnt[c] < 4) ++ c;
        if (c == 26) return false;
        cnt[c] -= 4;
    }
    for (int c = 0; r2 --; ) {
        while (c < 26 and cnt[c] < 2) ++ c;
        if (c == 26) return false;
        cnt[c] -= 2;
    }
    return true;
}

int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    array<int, 26> cnt = {};
    repeat (y, h) repeat (x, w) {
        char c; scanf(" %c", &c);
        cnt[c - 'a'] += 1;
    }
    // solve
    bool result = solve(h, w, cnt);
    // output
    printf("%s\n", result ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 1640
//
// Created by yamunaku on 2019/11/26.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    vector<string> v ={"SUN","MON","TUE","WED","THU","FRI","SAT"};
    string s;
    cin >> s;
    rep(i,7) if(s==v[i]){
            cout << 7-i << endl;
            return 0;
        }
    return 0;
}

Measured memory_bytes: 256
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;


int A,B;

signed main(){

    in(A,B);

    auto f = [](int n){
        int res=(n+1)/2%2;
        return (n%2==0)?res^n:res;
    };
    out(f(B)^f(A-1));

    return 0;
}


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

int main()
{
    int a, b, c;
    std::cin >> a >> b >> c;
    if (a + b + c >= 22) { std::cout << "bust" << std::endl; }
    else
    {
        std::cout << "win" << std::endl;
    }

    

    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, x, y int
	fmt.Scan(&n, &x, &y)

	k := make([]int, 10000000)
	for i := 1; i < n; i++ {
		for j := i + 1; j <= n; j++ {
			d := dist(i, x) + dist(j, y) + 1
			k[min(d, j-i)]++
		}
	}

	for i := 1; i < n; i++ {
		fmt.Println(k[i])
	}
}

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

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


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
Int dp[301][301][301];
const Int INF = 1e18;
template <class T> void chmin(T& x, T y) { if (x > y) x = y; }
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector<int> H(N); for (auto &h : H) cin >> h;
    H.insert(begin(H), 0);
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            for (int k = 0; k <= K; k++) {
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= min(i, K); j++) {
            for (int k = 0; k <= j; k++) {
                chmin(dp[i + 1][j + 1][k + 1], dp[i][j][k]);
                chmin(dp[i + 1][j][0], dp[i][j][k] + max(0, H[i + 1] - H[i + 1 - k - 1])); 
            }
        }
    }
    Int ans = INF;
    for (int i = 0; i <= K; i++) chmin(ans, dp[N][K][i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 213376
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1LL<<60;
long double pi=3.14159265358979323846L;
double eps=1e-12;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    int a[n+1];rep(i,1,n+1)cin>>a[i];
    int b[n+1];
    fill(b,b+n+1,0);
    vector<int> v;
    rrep(i,n,1){
        b[i]%=2;
        if(b[i]!=a[i]){
            b[i]=1;
            v.push_back(i);
        }
        else b[i]=0;
        if(i==1)break;
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                b[j]+=b[i];
                if(j*j<i&&j>1)b[i/j]+=b[i];
            }
        }
    }
    
    cout<<v.size()<<endl;
    rep(i,0,v.size())cout<<v[i]<<" ";
    cout<<endl;
}


Measured memory_bytes: 3192
from collections import Counter
from operator import itemgetter

N = int(input())
A = list(map(int, input().split()))

B = list(Counter(A).items())
B.sort(key=itemgetter(0))

c = 0
even = False
for k, v in B:
    if v % 2 == 1:
        c += 1
    else:
        if even == True:
            c += 2
            even = False
        else:
            even = True
print(c)

Measured memory_bytes: 21460
#include <bits/stdc++.h>    //super header :標準ライブラリ,STLを全てインクルード
using namespace std;

int main(){
    string s;cin >> s;

    int cnt = 0;
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i]=='0') cnt++;
    }
    int tmp = s.size() - cnt;
    cout << min(cnt,tmp) * 2<< endl;
}


Measured memory_bytes: 512
from itertools import *

N = int(input())

A = ["3", "5", "7"]

ans = 0

length = len(str(N))

for i in range(3, length+1) :
    for prod in product(A, repeat=i) :
        if prod.count("3") == 0 or prod.count("5") == 0 or prod.count("7") == 0 :
            continue
        
        num = int("".join(prod))
        if num > N :
            break
        
        ans += 1
        
print(ans)


Measured memory_bytes: 3316
from numpy.fft import rfft, irfft
import numpy as np
from bisect import bisect_left, bisect_right

N, M = map(int, input().split())
A = list(map(int, input().split()))

a = np.zeros(2 ** 18)
for Ai in A:
    a[Ai] += 1

fa = rfft(a)
a2 = irfft(fa ** 2)
a2 = np.round(a2).astype(np.int)

cum_a2 = np.cumsum(a2)

index = bisect_left(cum_a2, N ** 2 - M)
eli = cum_a2[index] - (N ** 2 - M)

a2[index] -= eli

ans = sum(A) * 2 * N - (a2[: index + 1] * np.arange(index + 1)).sum()
print(ans)


Measured memory_bytes: 33376
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j]+1
    else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i+1][j+1])
ans=''
while n*m:
  if s[n-1]==t[m-1]:
    ans+=s[n-1]
    n-=1
    m-=1
  else:
    if dp[n-1][m]>dp[n][m-1]:n-=1
    else:m-=1
print(ans[::-1])

Measured memory_bytes: 153008
/**
 * Hierarchical Democracy
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {

			Tree tree = new Tree();
			Deque<Node> stack = new ArrayDeque<Node>();
			String num = "";

			line = br.readLine();
			for (char c : line.toCharArray()) {
				switch (c) {
					case '[':
						Node node = new Node();
						if (!stack.isEmpty()) {
							node.parent = stack.peek();
							stack.peek().children.add(node);
						}
						stack.push(node);
						break;
					case ']':
						if (num.length() > 0) {
							stack.peek().nums.add(parseInt(num));
							num = "";
						}
						if (stack.size() != 1) {
							stack.pop();
						} else {
							tree.root = stack.pop();
						}
						break;
					default:
						num += c;
						break;
				}
			}
			System.out.println(tree.solve());
		}
	} //end main
}

class Tree {
	Node root;

	int solve() {
		Deque<Node> stack = new ArrayDeque<Node>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node node = stack.pop();
			if (node.children.isEmpty()) {
				node.min = node.nums.get(0) / 2 + 1;
				continue;
			}
			//
			if (node.min == Node.NIL) {
				node.min = 0;
				stack.push(node);
				for (Node child : node.children) {
					stack.push(child);
				}
			} else {
				for (Node child : node.children) {
					node.nums.add(child.min);
				}
				Collections.sort(node.nums);
				for (int i = 0; i < node.nums.size() / 2 + 1; i++) {
					node.min += node.nums.get(i);
				}
			}
		}
		return root.min;
	}
}

class Node {
	static final int NIL = -1;
	Node parent;
	List<Node> children = new ArrayList<Node>();
	List<Integer> nums = new ArrayList<Integer>();
	int min = NIL;
}

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

typedef long long ll;

int neighbour( string* a ,int i , int j , int h, int w)
{
    int ans =0;
    if( i-1>=0 && a[i-1][j] == '#')
            ans++;
    if( i+1<h && a[i+1][j] == '#')
        ans++;
    if( j-1>=0 && a[i][j-1] == '#')
        ans++;
    if( j+1<w && a[i][j+1] == '#')
        ans++;
    return ans;
}
int main()
{
    ll h ,w;
    cin>>h>>w;
    string* a = new string[h];
    for(int i=0;i<h;i++)
    {
        cin>>a[i];
    }
    bool ans = true;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if( a[i][j] =='#')
            {
                int n = neighbour( a,i,j,h,w);
                if( n==0 )
                    ans = false;
            }
        }
    }
    if( ans)
        cout<<"Yes";
    else
        cout<<"No";
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	int n;
	cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];
	ll ans = 0LL, b = 0LL;
	rep(i, n) {
		if(b) a[i]++, b--;
		ans += a[i]/2;
		b = a[i]%2;
		if(a[i]/2 == 0) b = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
#define INF 1e10
using namespace std;
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
template<typename T> void cmax(T &a, T b) { a = max(a, b); }

signed main() {
  int n, k;
  string s;
  cin >> n >> s >> k;
  char tar = s[k - 1];
  rep(i, s.size()) {
    if (s[i] != tar) {
      cout << '*';
    } else {
      cout << s[i];
    }
  }
  cout << endl;
  return 0;
}


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

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define mod 1000000007;

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

// Print fn to print array


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

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

int main() {
    int n, m;
    cin >> n >> m;
    char a[n][n], b[m][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            cin >> b[i][j];
        }
    }

    bool ans = false;
    for (int i = 0; i < n - m + 1; i++) {
        for (int j = 0; j < n - m + 1; j++) {
            bool match = true;
            for (int y = 0; y < m; y++) {
                for (int x = 0; x < m; x++) {
                    if (a[i + y][j + x] != b[y][x])
                        match = false;
                }
            }
            if (match) ans = true;
        }
    }
    if (ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
} 

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let m = read::<i64>();
    let s = read::<String>().chars().collect::<Vec<char>>();
    let mut l = n as i64 - 1;
    let mut r = n as i64;
    let mut anss = vec![];
    while r > 0 {
        let mut next = None;
        while l >= 0 && l >= r - m {
            if s[l as usize] == '0' {
                next = Some(l);
            }
            l -= 1;
        }
        if let Some(nr) = next {
            anss.push(r - nr);
            r = nr;
        } else {
            println!("-1");
            return;
        }
    }
    anss.reverse();
    let mut first = true;
    for &ans in anss.iter() {
        if !first {
            print!(" ");
        }
        print!("{}", ans);
        first = false;
    }
    println!("");
}


Measured memory_bytes: 3340
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<string> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    vector<string> red(n, string(m, '.'));
    vector<string> blue(n, string(m, '.'));
    for (int i = 0; i < m; ++i) {
        red[0][i] = '#';
        blue[n - 1][i] = '#';
    }
    for (int j = 1; j < m - 1; ++j) {
        vector<string>& a = (j & 1) ? red: blue;
        for (int i = 1; i < n - 1; ++i) {
            a[i][j] = '#';
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (A[i][j] == '#') {
                red[i][j] = blue[i][j] = '#';
            }
        }
    }
    for (const vector<string>& mat: {red, blue}) {
        for (const string& p: mat) {
            cout << p << '\n';
        }
        cout << '\n';
    }
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    set<int> s(a.begin(), a.end());
    const int N = 1'000'000;
    vector<int> sieve(N + 1), counter(N + 1);
    for(int x : s) {
        for(int y = 2 * x; y <= N; y += x) {
            sieve[y] = true;
        }
    }
    for(int x : a) {
        counter[x]++;
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans += not sieve[a[i]] and counter[a[i]] == 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 20996
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[]A = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		sc.close();
		int[]dA = new int[N - 1];
		for(int i = 0; i < N - 1; i++) {
			dA[i] = Math.abs(A[i] - A[i + 1]);
		}
		int sum = 0;
		for(int i = 0; i < N - 1; i++) {
			sum += dA[i];
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++) {
			int t;
			if(i == 0) {
				t = Math.abs(A[1]);
			}else {
				t = Math.abs(A[0]);
			}
			if(i != N - 1) {
				t += Math.abs(A[N - 1]);
			}else {
				t += Math.abs(A[N - 2]);
			}
			if(i == 0) {
				t += sum - dA[0];
			}else if(i == N - 1){
				t += sum - dA[N - 2];
			}else {
				t += sum + Math.abs(A[i - 1] - A[i + 1])- dA[i] - dA[i - 1];
			}
			sb.append(t).append("\n");
		}
		System.out.print(sb.toString());
	}
}

Measured memory_bytes: 55296
#include<stdio.h>

int main(){
    int H, W, h, w;
    scanf("%d %d", &H, &W);
    h=0;
    w=0;
    while(H != 0 && W != 0){
        while(h<H){
            while(w<W){
                printf("#");
                w++;
            }
            printf("\n");
            h++;
            w=0;
        }
    printf("\n");
    scanf("%d %d", &H, &W);
    h=0;
    }
}


Measured memory_bytes: 2036
import sys
sys.setrecursionlimit(10 ** 7)

n, z, w = map(int, input().split())
a = list(map(int, input().split()))

cache = {}

def f(idx, turn, x, y):
    if idx == n:
        return abs(x - y)
    
    key = (idx, turn)
    if key in cache:
        return cache[key]

    if turn == 0:
        ans = -float('inf')
        for i in range(idx, n):
            ans = max(ans, f(i + 1, 1 - turn, a[i], y))
    else:
        ans = float('inf')
        for i in range(idx, n):
            ans = min(ans, f(i + 1, 1 - turn, x, a[i]))

    cache[key] = ans
    return cache[key]

print(f(0, 0, z, w))

Measured memory_bytes: 48856
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,t,i,j;
  cin>>n;
  vector<int> c(n-1),s(n-1),f(n-1);
  for(i=0;i<n-1;i++) cin>>c.at(i)>>s.at(i)>>f.at(i);
  for(i=0;i<n;i++){
    if(i==n-1) cout<<0<<endl;
    else{
      t=0;
      for(j=i;j<n-1;j++){
        t=(max(t,s.at(j))+f.at(j)-1)/f.at(j)*f.at(j)+c.at(j);
      }
      cout<<t<<endl;
    }
  }
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9
#define f first
#define s second

typedef long long ll;

using namespace std;

const int N = 2e5;

int a[N+1];

int main()

{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m = -1;

    cin >> n;

    int arr[n];

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

        cin >> arr[i];
        a[arr[i]]++;
        m = max(m, arr[i]);
    }

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

        for (int j = m; j >= 0; j--) {

            if (a[j] > 1 || (arr[i] != j && a[j])) {

                cout << j;
                break;
            }
        }

        cout << "\n";
    }

    return 0;
}


Measured memory_bytes: 3072
#include "iostream"
#include "algorithm"
using namespace std;
int main() {
	int n;
	int a[100];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	cout << (a[n - 1] - a[0]) << endl;
	return 0;
}

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

using namespace std;


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

  long long n, x;
  cin >> n >> x;
  vector<int> A(n);
  for (auto &a : A) cin >> a;

  long long tot = 0, res = 0;
  for (int i = 1; i < n; ++i) {
    int &a = A[i-1];
    int &b = A[i];
    tot = a + b;
    if (tot > x) {
      res += tot-x;
      a -= (b < tot-x ? tot-x-b : 0);
      b -= (b < tot-x ? b : tot-x);
    }
  }
  cout << res << endl;

  return 0;
}



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

using namespace std;

int main()
{
	int r, c;
	cin >> r >> c;
	vector< vector<int> > table(r + 1, vector<int>(c + 1, 0));
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> table[i][j];
			table[i][c] += table[i][j];
			table[r][j] += table[i][j];
		}
		table[r][c] += table[i][c];
	}
	for (int i = 0; i <= r; i++)
	{
		for (int j = 0; j <= c; j++)
		{
			cout << table[i][j];
			if (j == c)
			{
				cout << endl;
			}
			else
			{
				cout << " ";
			}
		}
	}
    return 0;
}


Measured memory_bytes: 3204