akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long ll;
typedef unsigned uint;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int main(){
    cin.sync_with_stdio(false);cin.tie(0);
	int a,b;
	cin>>a>>b;
	cout<<(b+a-3)/(a-1)<<endl;
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

	s := next()
	ss := strings.Split(s, "/")
	ymd := make([]int, 3)
	for i := 0; i < 3; i++ {
		x, _ := strconv.Atoi(ss[i])
		ymd[i] = x
	}
	if ymd[0] < 2019 || (ymd[0] == 2019 && ymd[1] <= 4) {
		fmt.Println("Heisei")
	} else {
		fmt.Println("TBD")
	}
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pqueg = priority_queue<int, vector<int>, greater<int>>;
using pquel = priority_queue<int, vector<int>, less<int>>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
int lcm(int a, int b){
  return a / __gcd(a, b) * b;
}
int r_int(int a, int b){
  return rand() % b + a;
}
const lint mod=1e9+7;



int main()
{
  int n, m;
  cin >> n >> m;

  cout << (n==m ? "Yes" : "No") << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
 
 
int main() {
    int D, N;
    scanf("%d%d", &D, &N);
    if (N == 100) {
        printf("101");
        for (int i = 1; i <= D; ++i) printf("00");
    }
    else {
        printf("%d", N);
        for (int i = 1; i <= D; ++i) printf("00");
    }
    return 0;
}

Measured memory_bytes: 256
m,n=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(n)]
l=[]
for x in range(1,m+1):
    c=0
    for y in a:
        if y[0]==x:c+=1
        if y[1]==x:c+=1
    l.append(c)
for x in l:
    print(x)

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

int main()
{
	int n, k;
	cin >> n >> k;
	std::vector<int> l(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> l.at(i);
	}
	sort(l.begin(), l.end(), greater<int>());
	int ans = 0;
	for (int i = 0; i < k; ++i)
	{
		ans += l.at(i);
	}
	cout << ans << endl;	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;

ll gcd(ll a, ll b)
{
    if (a < b) {
    swap(a, b);
    }
    
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}



int main(){
  ll N;
  cin>>N;
  ll K;
  cin>>K;
  ll a[N];
  ll ma = 0;
  bool p = 0;
  for(ll i = 0;i<N;i++){
    cin>>a[i];
    ma = max(ma,a[i]);
    if(K == a[i]){
      p = 1;
    }
  }
  ll llcm = gcd(a[0],a[1]);
  for(ll i = 2;i<N;i++){
    llcm = gcd(llcm,a[i]);
  }
  
  
  if(p == 1){
    cout << "POSSIBLE" << endl;
  }
  else if(ma<K){
    cout << "IMPOSSIBLE" << endl;
  }
  else if(llcm == 1){
    cout << "POSSIBLE" << endl;
  }
  else if(K%llcm == 0){
    cout << "POSSIBLE" << endl;
  }
  else{
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main{
    public static void main(String[] args){
	Scanner kbd = new Scanner(System.in);
	int a = kbd.nextInt();
	int b = kbd.nextInt();
	if(a<b)
	    System.out.println("a < b");
	else if(a>b)
	    System.out.println("a > b");
	else if(a==b)
	    System.out.println("a == b");
    }
}

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

struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) (v).rbegin(), (v).rend()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) REPS(i, 0, n)
#define REP1(i,n) for (ll i = 1; i <= (ll)(n); ++i)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}

signed main() 
{
  string s; cin>>s;
  cout<<s.substr(0,4)<<" "<<s.substr(4,8)<<endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;
 
class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long x = (long)Math.sqrt(a);
        for(long i = x; i > 0; i--){
            if(a % i == 0){
                System.out.println(i + (a / i) - 2);
                 break;
            }
        }
    }
}

Measured memory_bytes: 22996
#include <set>
#include <stdio.h>
using namespace std;
int main(){
    set<int> a,b;
    int n,temp,ans=0;
    scanf("%d",&n);
    scanf("%d",&n);
    while(n--){
        scanf("%d",&temp);
        a.insert(temp);
    }
    scanf("%d",&n);
    while(n--){
        scanf("%d",&temp);
        b.insert(temp);
    }
    scanf("%d",&n);
    while(n--){
        scanf("%d",&temp);
        if(b.find(temp)!=b.end())ans++;
        else if(a.find(temp)==a.end())ans++;
    }
    
    printf("%d\n",ans);
}


Measured memory_bytes: 2800
while line = gets
  n,s = line.split.map(&:to_i)
  break if n == 0 && s == 0
  counter = 0
  combi = (0..9).to_a.combination(n)
  combi.collect {|arr|  counter += 1 if (arr.inject {|mem, sum|  sum += mem} == s) }
  p counter
end

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

int main(){
    int n,a,b,c,d;
    cin >> n >> a >> b >> c >> d;
    int xset=(n+a-1)/a*b;
    int yset=(n+c-1)/c*d;
    if(xset<yset) cout << xset << endl;
    else cout << yset << endl;
    return 0;
}



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


int main(void){
	long long n,m;
	cin >> n >> m;
	long long res=0;
	if(m<n*2){
		res = m/2;
	}else if(m==n*2){
		res = n;
	}else{
		m-=n*2;
		res = n + (m)/4;
	}
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=3000+10,mo=1000000007;
int f[maxn][maxn][2],g[maxn][maxn][2][2];
int i,j,k,l,t,n,m,ans;
int main(){
	scanf("%d%d",&n,&m);
	f[0][0][1]=1;
	fo(i,1,n) f[0][i][0]=1;
	fo(i,0,m-1)
		fo(j,0,n)
			fo(k,0,1){
				if (j) (f[i+1][j-1][k|(j-1==0)]+=f[i][j][k])%=mo;
				if (j) (f[i+1][j][k|(j==1)]+=f[i][j][k])%=mo;
				if (n-j) (f[i+1][j][k]+=f[i][j][k])%=mo;
				if (n-j) (f[i+1][j+1][k]+=f[i][j][k])%=mo;
			}
	fo(i,0,n) (ans+=f[m][i][1])%=mo;
	printf("%d\n",ans);
}

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  string s;
  while (cin >> s) {
    int mn = 1 << 29;
    int mx = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'Z') setmax(mx, i);
      if (s[i] == 'A') setmin(mn, i);
    }
    cout << mx - mn + 1 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 720
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
k,n = map(int,input().split())
al = input().split()
al2 = [int(i) for i in al]
distance = []
for i in range(len(al)-1):
    distance.append(al2[i+1]-al2[i])
distance.append(((al2[0])+(k-al2[-1])))
distance.remove(max(distance))
print(sum(distance))

Measured memory_bytes: 27956
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 1e5 + 9;
int n, a[Maxn], b[Maxn], c[Maxn];
int dp[Maxn][3];

void init() {
	n = read();

	rep (i, 1, n) 
		a[i] = read(), b[i] = read(), c[i] = read();
}

void solve() {
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	rep (i, 1, n) {	
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
		dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + c[i];
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;
}

int main() {
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int MOD = 1e9 + 7;
const int INF = 2147483647;
// const ll INF = 1000000000000000000LL;

vector<ll> fact_inv, inv, Com;

/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int n, int SIZE) {
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
    Com.resize(SIZE + 5);
    Com[0] = 1;
    for (int i = 1; i < SIZE + 5; i++) {
        Com[i] = Com[i - 1] * ((n - i + 1) * inv[i] % MOD) % MOD;
    }
}

 ll modpow(ll x, ll n) {
     ll res = 1;
     while (n > 0) {
         if (n & 1) {  // nが奇数のとき
             res *= x;
             res %= MOD;
         }
         x *= x;
         x %= MOD;
         n >>= 1;
     }
     return res;
 }

/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
ll nCk(int k) {
    assert(!(k < 0));
    return Com[k];
}

int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll all = modpow(2,n);
  init_nCk(n,2e5+10);
  ll com_a,com_b;
  com_a = nCk(a);
  com_b = nCk(b);
  ll ans = all - com_a - com_b - 1;
  while(ans<0){
      ans+=MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 7960
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 10005
#define LL long long
#define INF 0x3f3f3f3f
#define mset(p,v) memset(p,v,sizeof(p))
using namespace std;
int n;
int main()
{
    while(~scanf("%d",&n))
    {
        int num1=n/500;
        int num2=(n-num1*500)/5;
        printf("%lld\n",(LL)num1*1000+(LL)num2*5);
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  string s;
  cin>>s;
  ll sum=0;
  ll n=(ll)s.length();
  for(ll i=0;i<n;i++)
  {
    sum+=s[i]-'0';
  }
  if(sum%9==0)
    cout<<"Yes\n";
  else
    cout<<"No\n";
}

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

long long n,x,a[2050];
long long mn[2050][2050];

main()
{
	scanf("%lld %lld",&n,&x);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		mn[0][i]=a[i];
		ans+=mn[0][i];
	}
	for(int i=1;i<n;i++)
	{
		long long sum=0;
		for(int j=0;j<n;j++)
		{
			int chk=j-i;
			if(chk<0)
				chk=n+chk;
			mn[i][j]=min(mn[i-1][j],a[chk]);
			sum+=mn[i][j];
		}
		ans=min(ans,sum+i*x);
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 33024
//mangesh2102000

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long int 
#define ld long double
#define pb push_back
#define tr(c,it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define F first
#define S second
#define mod 1000000000

int n,W;
int w[105];
int v[105];
int dp[105][100005];

void solve(int t)
{
	cin >> n >> W;
	for(int i=0;i<n;i++)
	{
		cin >> w[i] >> v[i];
	}

	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=W;j++)
		{
			if(i==0 || w==0)
			{
				dp[i][j] = 0;
			}
			else if(j-w[i-1]>=0)
			{
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
			}
			else
			{
				dp[i][j] = dp[i-1][j];
			}
		}
	}

	cout << dp[n][W];

    //cout << "Case #" << t << ": " << ;
}   


int32_t main()
{
    IOS;
    int t;
    t=1;
    for(int i=1;i<=t;i++)
    {
        solve(i);
    }

    return 0;
}

Measured memory_bytes: 80128
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;
int sq[555555],d1,d2,xx,yy,p[555555],cnt,n,col[555555],msk[555555],pos,sum[5],id;
int cnt1,cnt2,cpt,pa[555555],val[555555];
pair<int,int> v1[1111],v2[1111];
int root(int x)
{
	if (pa[x]==x) return x;
	int rt=root(pa[x]);
	val[x]^=val[pa[x]];
	return pa[x]=rt;
}
void Union(int x,int y)
{
	int rx=root(x),ry=root(y);
	if (rx==ry) return;
	pa[rx]=ry;val[rx]=(1^val[x]^val[y]);
}
void Init()
{
	memset(sq,-1,sizeof(sq));
	for (int i=0;i<=500;i++) sq[i*i]=i;
}
int get(int x,int y)
{
	return (x-1)*n+y;
}
bool In(int x,int y)
{
	return (x>=1 && x<=n && y>=1 && y<=n);
}
void addedge(int x,int y)
{
	Union(x,y);
}
int main()
{
	scanf("%d%d%d",&n,&d1,&d2);
	Init();n<<=1;
	for (int k=0;k<=n;k++)
	{
		if (d1-k*k>=0 && ~sq[d1-k*k]) 
		{
			v1[++cnt1]=make_pair(k,sq[d1-k*k]);
		}
		if (d2-k*k>=0 && ~sq[d2-k*k]) 
		{
			v2[++cnt2]=make_pair(k,sq[d2-k*k]);
		}
	}
	for (int i=1;i<=n*n;i++)
	{
		pa[i]=i;
		val[i]=0;
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			id=get(i,j);
			for (int k=1;k<=cnt1;k++)
			{
				xx=i+v1[k].first;yy=j+v1[k].second;
				if (In(xx,yy)) addedge(id,get(xx,yy));
				xx=i-v1[k].first;yy=j+v1[k].second;
				if (In(xx,yy)) addedge(id,get(xx,yy));
			}
		}
	}
	for (int i=1;i<=n*n;i++)
	{
		root(i);
		col[i]=val[i];
	}
	for (int i=1;i<=n*n;i++) msk[i]=col[i];
	for (int i=1;i<=n*n;i++)
	{
		pa[i]=i;
		val[i]=0;
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			id=get(i,j);
			for (int k=1;k<=cnt2;k++)
			{
				xx=i+v2[k].first;yy=j+v2[k].second;
				if (In(xx,yy)) addedge(id,get(xx,yy));
				xx=i-v2[k].first;yy=j+v2[k].second;
				if (In(xx,yy)) addedge(id,get(xx,yy));
			}
		}
	}
	for (int i=1;i<=n*n;i++)
	{
		root(i);
		col[i]=val[i];
	}
	for (int i=1;i<=n*n;i++) msk[i]|=(col[i]<<1);
	for (int i=1;i<=n*n;i++) sum[msk[i]]++;
	for (int i=0;i<4;i++)
	{
		if (sum[i]>=n*n/4) 
		{
			pos=i;
			break;
		}
	}
	for (int i=1;i<=n*n;i++)
	{
		if (cnt==n*n/4) break;
		if (msk[i]==pos) 
		{
			printf("%d %d\n",(i-1)/n,(i-1)%n);
			cnt++;
		}
	}
	return 0;
}

Measured memory_bytes: 13312
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
int h, w;
char str[1000];
char field[100][100];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

void Move(int &px, int &py, int dir) {
  int nx = px + dx[dir];
  int ny = py + dy[dir];
  if (nx < 0 || nx >= w || ny < 0 || ny >= h || field[ny][nx] != '.') { return; }
  px = nx;
  py = ny;
}

void Shoot(int x, int y, int dir) {
  while (true) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx < 0 || nx >= w || ny < 0 || ny >= h || field[ny][nx] == '#') { break; }
    if (field[ny][nx] == '*') {
      field[ny][nx] = '.';
      break;
    }
    x = nx;
    y = ny;
  }
}

int main() {
  int test;
  scanf("%d", &test);
  while (test--) {
    scanf("%d %d", &h, &w);
    int dir = 0xdeadbeaf;
    int px = -1;
    int py= -1;
    REP(y, h) {
      scanf("%s", field[y]);
      REP(x, w) {
        char c = field[y][x];
        if (c == '>') { px = x; py = y; dir = 0; }
        if (c == 'v') { px = x; py = y; dir = 1; }
        if (c == '<') { px = x; py = y; dir = 2; }
        if (c == '^') { px = x; py = y; dir = 3; }
      }
    }
    scanf("%d %s", &n, str);
    REP(i, n) {
      field[py][px] = '.';
      if (str[i] == 'R') { dir = 0; Move(px, py, dir); }
      if (str[i] == 'D') { dir = 1; Move(px, py, dir); }
      if (str[i] == 'L') { dir = 2; Move(px, py, dir); }
      if (str[i] == 'U') { dir = 3; Move(px, py, dir); }
      if (str[i] == 'S') { Shoot(px, py, dir); }
      if (dir == 0) { field[py][px] = '>'; }
      if (dir == 1) { field[py][px] = 'v'; }
      if (dir == 2) { field[py][px] = '<'; }
      if (dir == 3) { field[py][px] = '^'; }
    }
    REP(y, h) {
      printf("%s\n", field[y]);
    }
    if (test != 0) { puts(""); }
  }
}

Measured memory_bytes: 0
str = ''
count = {}
for c in [chr(i) for i in range(97, 123)]:
  count[c] = 0

while True:
  try:
    tmp = input()
    str += tmp
  except:
    break

for char in str:
  for c in count:
    if char.upper() == c.upper():
      count[c] += 1

for c, n in count.items():
  print(c, ':', n)


Measured memory_bytes: 5572
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);

		String s = sc.next();

		Set<Character> c = new HashSet<>();
		c.add(s.charAt(0));
		c.add(s.charAt(1));
		c.add(s.charAt(2));

		if(c.size() == 3) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}


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

constexpr int inf = 1e9;
constexpr ll linf = 5e18;

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

    int n, K; cin >> n >> K;
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    ll ans = linf;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    ll L = min({x[i], x[j], x[k], x[l]});
                    ll R = max({x[i], x[j], x[k], x[l]});
                    ll D = min({y[i], y[j], y[k], y[l]});
                    ll U = max({y[i], y[j], y[k], y[l]});
                    int cnt = 0;
                    for (int m = 0; m < n; m++) {
                        if (L <= x[m] && x[m] <= R && D <= y[m] && y[m] <= U) cnt++;
                    }
                    if (cnt >= K) ans = min(ans, (R - L) * (U - D));
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/
/*
int dfs(int foo, int timer)
{
    //foo is node number
    if (finds[foo].first != -1)
        return timer;
    finds[foo].first = ++timer;
    int result = timer;
    if (data[foo].size() != 0)
    {
        rep(i, data[foo].size())
        {
            result = dfs(data[foo][i], result);
        }
    }
    finds[foo].second = ++result;
    return result;
}
*/
int main()
{
    int a;
  cin>>a;
  cout<<48-a<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define MAX 500000
#define s 1000000000
void merge(int*,int, int, int);
void mergeSort(int*,int ,int); 
int count;

int main(){
  int i,j;
  int n,S[MAX];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  mergeSort(S,0,n);

  for(j=0;j<n;j++){
     printf("%d",S[j]);
     if(j!=n-1)printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  return 0;
  
}  

void merge(int *A,int left,int mid,int right){
  int n1,n2,i,j,k;
  int L[MAX],R[MAX];
  n1 = mid - left;
  n2 = right - mid;
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }

  for(i=0;i<=n2-1;i++){
    R[i]=A[mid+i];
  }
  
  L[n1]=s;
  R[n2]=s;
  i=0;
  j=0;

  for(k=left;k<=right-1;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i=i+1;
    count++;  
    }else{
      A[k]=R[j];
      j=j+1;
      count++;
    }
  }
}

void mergeSort(int *A,int left,int right){
  int mid;  
  if(left+1<right){
    mid = (left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}

  



Measured memory_bytes: 5616
#include <iostream>
#include<bits/stdc++.h>
#define ll long long int
#define lld long double
#define F first
#define S second
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
#define mp make_pair
#define pb push_back
#define mh make_heap
#define ph push_heap
#define pq priority_queue
#define bits(x) __builtin_popcountll(x)
#define op(x) cout<<"Case #"<<x<<": "
#define op1(x) cout<<"Scenario #"<<x<<": "
#define endl "\n"
using namespace std;
const ll mod = 1000000007;
const ll INF = 1e18;
const int N = 20;
map<ll, ll> fr;

void solve(int t)
{
	ll n;
	cin >> n;
	map<ll, ll> m;

	for (int i = 1; i <= 100; i++)
	{
		for (int j = 1; j <= 100; j++)
		{
			for (int k = 1; k <= 100; k++)
			{
				ll d = i * i + j * j + k * k + i * j + j * k + k * i;
				if (d <= n)
					m[d]++;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << m[i] << endl;
	}
}

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



	int t = 1;
	//cin >> t;

	for (int i = 1; i <= t; i++)
	{
		solve(i);

	}
}

Measured memory_bytes: 4204
#include<iostream>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long int ll;

const ll mod=1e9+7; 

ll N,K;
ll v[200005];

int main(){
    cin>>N>>K;
    for(int i=1;i<=N;++i)v[i]=v[i-1]+i;
    ll ans=0LL;
    for(int i=K;i<=N+1;++i){
        ll ma,mi;
        if(i==N+1)ma=v[N];
        else ma=v[N]-v[N-i];
        mi=v[i-1];
        ans+=(ma-mi+1)%mod;
        ans%=mod;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5076
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
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;
}

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

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &&i : A) {
        cin >> i;
    }
    int cnt = 0;

    for (int i = 0; i < N; i++) {
        int minj = i;
        for (int j = i; j < N; j++) {
            if (A[j] < A[minj]) {
                minj = j;
            }
        }
        if (A[i] != A[minj])
            cnt++;
        swap(A[i], A[minj]);
    }

    for (int i = 0; i < N; i++) {
        cout << A[i];
        i == N - 1 ? cout << '\n' : cout << ' ';
    }
    std::cout << cnt << '\n';

    return 0;
}


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

using namespace std;

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

void solve() {
  int n;
  cin >> n;
  vector<int> v;
  v.resize(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  int ret = 0;
  for(int i = 0; i < n;) {
    ret++;
    int j = i+1;
    bool inc = true;
    bool dec = true;
    while(j < n && (inc || dec)) {
      if(v[j] > v[j-1]) dec = false;
      if(v[j] < v[j-1]) inc = false;
      if(!inc && !dec) break;
      j++;
    }
    i = j;
  }
  cout << ret << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}


Measured memory_bytes: 640
#include <stdio.h>

int main()
{
    int a[3];
    int n5, n7;
    int i = 0;
    while(~scanf("%d%d%d", &a[0], &a[1], &a[2])){
        n5 = 0;
        n7 = 0;
        for(i = 0; i < 3; i++){
            if(a[i] == 5)
                n5++;
            if(a[i] == 7)
                n7++;
        }
        if(n5 == 2 && n7 == 1)
            printf("YES");
        else
            printf("NO");
    }
    return 0;
}

Measured memory_bytes: 128
A,B,C = map(int,input().split())
D = 0
E = 0
F = 0
c = 0
flag = True
if (A%2 == 0 and A == B == C):
  print(-1)
else:
  while flag:
    if (A%2 == B%2 == C%2 == 0):
      D = A
      E = B 
      F = C
      A = int((E+F)/2)
      B = int((D+F)/2)
      C = int((D+E)/2)
      c += 1
    else:
      flag = False
  print(c)

Measured memory_bytes: 3064
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	string S;
	ll z = 0;
	cin >> S;
	rep(i, S.size()) {
		if (S.at(i) == '0') {
			z++;
		}
		
	}
	cout << 2 * min(z, ll(S.size()) - z) << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define uptil(a, b, i) for(int i = (a), b_ = (b); i < b_; ++i)
#define upto(a, b, i) for(int i = (a), b_ = (b); i <= b_; ++i)
#define downtil(a, b, i) for(int i = (a), b_ = (b); i > b_; --i)
#define downto(a, b, i) for(int i = (a), b_ = (b); i >= b_; --i)
#define times(n, i) uptil(0, n, i)
#define rtimes(n, i) downto((n)-1, 0, i)

#define sp <<" "
#define ln <<"\n"
#define size(v) ((int)(v).size())
template<class T> using vec=vector<T>;
template<class T> using vvec=vec<vector<T>>;

void solve() {
  int n, a, b; cin >> n >> a >> b;
  int ans = 0;
  times(n-2, i) {
    int c; cin >> c;
    ans += a <= b && b <= c || a >= b && b >= c;
    a = b; b = c;
  }
  cout << ans ln;
}

signed main() {
  // cin.tie(0);
  cout << fixed << setprecision(20);
  cerr << fixed << setprecision(10);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int data_lim;
	cin >> data_lim;
	for(int cnt=0;cnt<data_lim;cnt++) {
		int a,b,c;
		cin >> a >> b >> c;
		
		bool flg = false;
		// ピタゴラスの定理を適用
		if(a*a == b*b+c*c)
			flg = true;
		else if(b*b == a*a+c*c)
			flg = true;
		else if(c*c == a*a+b*b)
			flg = true;
		
		if(flg == true)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 1152
local DBG = false
local function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end

local function dbgpr_t(tbl, use_pairs)
    if DBG then
        local enum = ipairs
        if use_pairs then
            enum = pairs
        end
        dbgpr(tbl)
        io.write("[dbg]")
        for i,v in enum(tbl) do
            io.write(i)
            io.write(":")
            io.write(tostring(v))
            io.write(" ")
        end
        print("")
    end
end

-- SegTree
-- 参考にしました: http://tsutaj.hatenablog.com/entry/2017/03/29/204841
local SegTree = {}
function SegTree.new(func, ident, vec)
    -- func: binary function
    -- ident: identity element
    -- vec: table
    local self = setmetatable({}, {__index = SegTree})
    self.func = func
    self.ident = ident
    local a = {}
    self.a = a
    local n = 1
    while n < #vec do
        n = n << 1
    end
    -- n is smallest power of 2 that is greater than or equal to #vec
    self.n = n
    local size = 2*n - 1
    for i=1, size do
        a[i] = ident
    end
    for i=1, #vec do
        a[i+n-1] = vec[i]
    end
    for i=n-1,1,-1 do
        a[i] = func(a[2*i], a[2*i+1])
    end
    return self
end

function SegTree:update(idx, val)
    local a = self.a
    local func = self.func
    idx = idx + self.n - 1
    a[idx] = val
    while true do
        idx = idx // 2
        a[idx] = func(a[idx*2], a[idx*2 + 1])
        if idx == 1 then
            break
        end
    end
end

function SegTree:query(left, right)
    -- query to [left, right)
    -- **be careful about right half open interval**
    local func = self.func
    local ident = self.ident
    local a = self.a
    local function q(k, l, r)
        if r <= left or l >= right then
            return ident
        end
        if l >= left and r <= right then
            return a[k]
        end
        local vl = q(2*k  , l, (l+r)//2)
        local vr = q(2*k+1, (l+r)//2, r)
        return func(vl, vr)
    end
    return q(1, 1, self.n + 1)
end
------
local function gcd(a,b)
    if b == 0 then
        return a
    else
        return gcd(b, a % b)
    end
end
----

local N = io.read("n")
local A = {}
for i=1,N do
    A[i] = io.read("n")
end
local st = SegTree.new(gcd, 0, A)
--[[
-- for verification
for i=1, #st.a do
    st.a[i] = 0
end
for i=1, N do
    st:update(i, A[i])
end
]]
dbgpr_t(st.a)
local maxval = 0
for i=1, N do
    local left = st:query(1, i)
    local right = st:query(i+1, N+1)
    local g = gcd(left, right)
    dbgpr(i, left, right, g)
    maxval = math.max(maxval, g)
end
print(maxval)


Measured memory_bytes: 53368
from collections import Counter

S = input()
C = Counter(S)
C.setdefault('a',0)
C.setdefault('b',0)
C.setdefault('c',0)
C = C.values()
if max(C) - min(C) == 0 or max(C) - min(C) == 1:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3444
#include <stdio.h>
#include <math.h>

typedef struct point {
	double x;
	double y;
} POINT;

void calc_circum_circle(POINT *p0, POINT *pa, POINT *pb, POINT *c, double *r);

int main()
{
	int n;
	POINT p0, pa, pb, c;
	double r;
	scanf("%d", &n);
	for (; n > 0; n--) {
		scanf("%lf %lf %lf %lf %lf %lf",
				&p0.x, &p0.y, &pa.x, &pa.y, &pb.x, &pb.y);
		calc_circum_circle(&p0, &pa, &pb, &c, &r);
		printf("%.3lf %.3lf %.3lf\n", c.x, c.y, r);
	}
	return 0;
}


void calc_circum_circle(POINT *p0, POINT *pa, POINT *pb, POINT *c, double *r)
{
	double ax, ay, bx, by, a2, b2, ab, s, t, r2;
	/* a = pa - p0, b = pb - p0 */
	ax = pa->x - p0->x;
	ay = pa->y - p0->y;
	bx = pb->x - p0->x;
	by = pb->y - p0->y;
	a2 = ax * ax + ay * ay;
	b2 = bx * bx + by * by;
	ab = ax * bx + ay * by;
	/* c = p0 + (sa + tb) */
	s = (a2 * b2 - ab * b2) / (2.0 * (a2 * b2 - ab * ab));
	t = (a2 * b2 - ab * a2) / (2.0 * (a2 * b2 - ab * ab));
	c->x = p0->x + s * ax + t * bx;
	c->y = p0->y + s * ay + t * by;
	/* r2 = (sa + sb)^2 */
	r2 = (s*ax + t*bx)*(s*ax + t*bx) + (s*ay + t*by)*(s*ay + t*by);
	*r = sqrt(r2);
}

Measured memory_bytes: 664
#include<iostream>
#include<stack>
using namespace std;
int main() {
	static int N, A[200000];
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> A[i];
	int ans = 0, max = N, mid, halfDiff, tmp;
	while(halfDiff = max - ans >> 1) { // 二分探索
		bool check = false;
		mid = ans + halfDiff;
		stack<pair<int, int> > stk;
		for (int j = 1;j < N;++ j) { // シミュレーション
			if (A[j - 1] >= A[j]) { // 文字数が減るパターン
				while (!stk.empty() && stk.top().first > A[j]) stk.pop();
				if (stk.empty() || stk.top().first < A[j]) stk.push(make_pair(A[j], 1));
				while (++ stk.top().second > mid) {
					tmp = mid == 1 ? 1 : stk.top().first;
					if (tmp == 1) goto break_label;
					stk.pop();
					if (stk.empty() || stk.top().first != tmp - 1) stk.push(make_pair(tmp - 1, 1));
				}
			}
		}
		check = true;
		break_label:;
		(check ? max : ans) = mid;
	}
	cout << max;
	return 0;
}


Measured memory_bytes: 1024
import itertools

N = int(input())
P = tuple(input().split())
Q = tuple(input().split())

L = [str(i+1) for i in range(N)]

L_list = list(itertools.permutations(L))

a = L_list.index(P)
b = L_list.index(Q)
print(abs(a-b))

Measured memory_bytes: 8052
// Do you knOW what it feels like?

		// To be TorTured by your own MinD?
	
	// I don't wanna feel the PAIN.

// I BeG you to KILL me, pleASE...

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,x,a[maxn],mnn[maxn];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>x;
	for(int i=0;i<n;i++) cin>>a[i], mnn[i]=inf;
	ll ans=inf;
	for(int ca=0;ca<n;ca++){
		for(int i=0;i<n;i++) mnn[i]=min(mnn[i],a[(i-ca+n)%n]);
		ll nans=x*ca;
		for(int i=0;i<n;i++) nans+=mnn[i];
		ans=min(ans,nans);
	}
	cout<<ans<<endl;

	return 0;
}








Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int i,j,n;
  int temp,A[100],ch=0;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    scanf("%d",&A[i]);
  }
  
  for(i = n-1 ; i > 0 ; i--){
    for(j = n-1 ; j > 0 ; j--){
      if(A[j] < A[j-1]){
	temp = A[j];
	A[j] = A[j-1];
	A[j-1] = temp;
	ch++;
      }
    }
  }
  
  for(j = 0 ; j < n ; j++){
    if(j != n-1){
      printf("%d ",A[j]);
    }
    else if(j == n-1){
      printf("%d\n",A[j]);
    }
  }
  printf("%d\n",ch);
  
  return 0;
}



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

using namespace std;

int N;
using ll = long long;
const ll inf = 1e18;
const int maxn = 402;

ll dp[maxn][maxn];
ll psum[maxn];
ll nums[maxn];

ll getsum(int st, int se) {
	return psum[se] - psum[st-1];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
		psum[i] = psum[i-1] + nums[i];
		fill(dp[i], dp[i]+maxn, inf);
	}

	for (int le = 1; le <= N; le++) {
		for (int cs = 1; cs <= N; cs++) {
			int ce = cs + le-1;
			if (ce > N) break;

			if (cs == ce) {
				dp[cs][ce] = 0;
				continue;
			}

			for (int sp = cs; sp < ce; sp++) {
				dp[cs][ce] = min(dp[cs][ce], 
					dp[cs][sp] + dp[sp+1][ce] + getsum(cs, ce));
			}
		}
	}

	cout << dp[1][N] << endl;
}

Measured memory_bytes: 1536
s=input().split(" ")
t_p=int(s[0])
t_a=int(s[1])
a_p=int(s[2])
a_a=int(s[3])
i=0
while i<=0:
    a_p-=t_a
    if a_p <= 0:
        print("Yes")
        break
    t_p-=a_a
    if t_p <= 0:
        print("No")
        break

Measured memory_bytes: 9192
N=int(input())

if N%4==0:
    print(3*N//4,3*N//4,3*N//4)
else:
    f=False
    a=(N+3)//4
    while a<=3*N//4:
        if f:
            break
        b=a
        while b<=2*N*a//(4*a-N):
            num=N*a*b
            den=4*a*b-N*(a+b)
            if den<=0:
                b+=1
                continue
            if num%den==0:
                c=num//den
                print(a,b,c)
                f=True
                break
            b+=1
        a+=1

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

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

vector<int> bfs(vvi L,int S){
  vector<int> v(L.size(),-1);
  v[S]=0;
  queue<int> q;
  q.push(S);
  while(!q.empty()){
    int a=q.front();
    q.pop();
    for(int x:L[a]){
      if (v[x]==-1){
        v[x]=v[a]+1;
        q.push(x);
      }
    }
  }
  return v;
}

void initialize(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
/////////////////////////////////////////

int main(){
  initialize();
  ll N,A,B;
  cin >> N >> A >> B;
  if(N==1){
    cout << (A==B?"1":"0") << endl;
  }
  if(N==2){
    cout << (A>B?"0":"1") << endl;
  }
  if(N>3){
    if(A>B) cout << "0" << endl;
    else cout << (B*(N-1)+A)-(A*(N-1)+B)+1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <typeinfo>
#include <climits>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
using namespace std;

int main(){
    int n,sum=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        sum+=i;
    }
    cout << sum;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <map>
#include <queue>
#include <deque>
#include <set>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define FOR(i,a,b) for (ll i = (a) ; i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
//#define repitr(itr, st) for(auto itr = st.begin(); itr != st.end(); ++itr)
#define P_B push_back
#define PO_B pop_back
#define E_B emplace_back
#define M_P make_pair
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl
//#define print(x) printf("%d\n", x)

using namespace std;
using ll = long long;
using Pii = pair<int,int>;
using Pll = pair<ll,ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<vector<int> >;
using VVL = vector<vector<ll> >;
//int dx[4] = {1, 0, -1, 0};
//int dy[4] = {0, 1, 0, -1};
//const ll LINF = (ll)1e18 - 1;
//const int INF = 1e9 - 1;
//int:±2*10^9くらい　ll:±9*10^18くらい


void Main(){
	ll N, M, ans=0;
	cin >> N;
	VL a(N);
	rep(i, N) cin >> a[i];

	sort(all(a));
	reverse(all(a));

	M = N/2;
	rep(i, M){
		ans += 2*a[i];
	}
	ans -= a[0];
	if(N%2 == 1){
		ans += a[M];
	}

	cout << ans << endl;




}

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

  return 0;
}


Measured memory_bytes: 4780
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    int n1,n2,n3,n4;
    n1 = n/1000;
    n2 = (n%1000)/100;
    n3 = (n%100)/10;
    n4 = n%10;
    if(n1==n2 && n2==n3){
        cout << "Yes" << endl;
    }else if(n2==n3 && n3==n4){
        cout << "Yes" << endl;
    }else if(n1==n2 && n2==n3 && n3==n4){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) (1e9 + 7);
//const ll MOD = 998244353;
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << setiosflags(ios::fixed);
    ll S;
    cin >> S;
    ll x1, y1, x2, y2, x3, y3;
    x3 = y3 = 0;
    x1 = (ll) (1e9);
    y2 = CEIL(S, x1);
    y1 = 1;
    x2 = x1 * y2 - S;
    printf("%d %d %d %d %d %d\n", x1, y1, x2, y2, x3, y3);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  
  double instance_t, instance_x;
  
  cin >> instance_t >> instance_x;
  
  double make_count = instance_t / instance_x;
  
  
  cout << fixed << setprecision(10) << make_count;
  
  return 0;
}

Measured memory_bytes: 256
# Treap
class Node():
    def __init__(self, k, p):
        self.k = k
        self.p = p
        self.left = None
        self.right = None

def rightRotate(t):
    s = t.left
    t.left = s.right
    s.right = t
    return s

def leftRotate(t):
    s = t.right
    t.right = s.left
    s.left = t
    return s

def insert(t, key, pri):
    if t == None:
        return Node(key, pri)
    if key == t.k:
        return t

    if key < t.k:
        t.left = insert(t.left, key, pri)
        if t.p < t.left.p:
            t = rightRotate(t)
    else:
        t.right = insert(t.right, key, pri)
        if t.p < t.right.p:
            t = leftRotate(t)
    return t

def erase(t, key):
    if t == None:
        return None

    if key == t.k:
        if t.left == None and t.right == None:
            return None
        elif t.left == None:
            t = leftRotate(t)
        elif t.right == None:
            t = rightRotate(t)
        else:
            if t.left.p > t.right.p:
                t = rightRotate(t)
            else:
                t = leftRotate(t)
        return erase(t, key)

    if key < t.k:
        t.left = erase(t.left, key)
    else:
        t.right = erase(t.right, key)
    return t

def find(t, k):
    if t == None:
        return -1
    if t.k == k:
        return 1
    if k < t.k:
        return find(t.left, k)
    else:
        return find(t.right, k)

def inorder(t):
    if t == None:
        return 
    inorder(t.left)
    print(" " + str(t.k), end="")
    inorder(t.right)

def preorder(t):
    if t == None:
        return
    print(" " + str(t.k), end="")
    preorder(t.left)
    preorder(t.right)

def output(t):
    inorder(t)
    print()
    preorder(t)
    print()


t = None
data = []
m = int(input())
for i in range(m):
    data.append(list(input().split()))

for i in range(m):
    if data[i][0] == "insert":
        t = insert(t, int(data[i][1]), int(data[i][2]))
    elif data[i][0] == "print":
        output(t)
    elif data[i][0] == "find":
        result = find(t, int(data[i][1]))
        if result == 1:
            print("yes")
        else:
            print("no")
    else:
        t = erase(t, int(data[i][1]))


Measured memory_bytes: 112116
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>

using namespace std;

#define mod 1000000007

int n;
vector<vector<int> > graph(100001);
vector<bool> ischecked(100001, false);
vector<long long int> stonenum(100001);

int cansolve(int node)
{
	if(graph[node].size() == 1) return stonenum[node];
	ischecked[node] = true;
	int ans = 2 * stonenum[node];
	for(int i = 0; i < graph[node].size(); i++){
		int child = graph[node][i];
		if(ischecked[child]) continue;
		int tmp = cansolve(child);
		ans -= tmp;
		if(tmp == -1 || tmp > stonenum[node] || ans < 0) return -1;
	}
	if(ans > stonenum[node]) return -1;
	return ans;
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> stonenum[i];
	}
	int a, b;
	for(int i = 0; i < n - 1; i++){
		cin >> a >> b;
		a--;
		b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	if(n == 2){
		if(stonenum[0] == stonenum[1]) cout << "YES" << endl;
		else cout << "NO" << endl;
		return 0;
	}
	int root = 0;
	while(root < n && graph[root].size() == 1) root++;
	if(cansolve(root)) cout << "NO" << endl;
	else cout << "YES" << endl;
	// cout << stonenum[0] << endl;
	return 0;
}

Measured memory_bytes: 11904