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

long gcd(long a,long b){
	long v0=a,v1=b,v2=a%b;
	while(v2!=0){
		v0=v1;
		v1=v2;
		v2=v0%v1;
	}
	return v1;
}

int main(){
	int N;
	cin>>N;
	vector<long>A;
	long tmp;
	for(int i=0;i<N;++i){
		cin>>tmp;
		A.push_back(tmp);
	}
	vector<long>L,R;
	for(int i=0;i<N;++i){
		if(i==0){
			L.push_back(A[i]);
			R.push_back(A[N-i-1]);
		}
		else{
			L.push_back(gcd(L[i-1],A[i]));
			R.push_back(gcd(R[i-1],A[N-i-1]));
		}
	}
	int ans=1;
	for(int i=0;i<N;++i){
		if(i==0){
			ans=R[N-(i+1)-1];
		}
		else if(i<N-1){
			if(ans<gcd(L[i-1],R[N-i-2]))ans=gcd(L[i-1],R[N-i-2]);
		}
		else{
			if(ans<L[N-2])ans=L[N-2];
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3444
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<utility>//swapでaとbの値を入れ替える
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
int max(int a, int b) {
	if (a > b)return a;
	return b;
}


int main() {
	int n;
	cin >> n;
	ll ans = 0;
	vector<ll> a(n + 1), b(n);
	rep(i, 0, n + 1)cin >> a[i];
	rep(i, 0, n)cin >> b[i];
	rep(i, 0, n) {
		if (b[i] <= a[i])ans += b[i];
		if (b[i] > a[i]) {
			ans += a[i];
			if (b[i] - a[i] > a[i + 1]) {
				ans += a[i + 1];
				a[i + 1] = 0;
			}
			else {
				a[i + 1] -= b[i] - a[i];
				ans += b[i] - a[i];
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define f(i) for(i=0;i<=9;i++)
int main(){
    int a,b,c,d,n,s,k=0;
    
    while(scanf("%d",&n)!=EOF){
                               k=0;
    f(a)
        f(b)
            f(c)
                f(d){
                if(n==a+b+c+d)
                k++;
                }  
                
                 cout<<k<<endl;                         
    }  
    return 0;
    
}

Measured memory_bytes: 1204
//Author- Vaibhav singh


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_multiset tree<long long , null_type,less_equal<long long >, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set tree<long long , null_type,less<long long >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long int
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define ld     long double 
#define yes cout<<"yes"<<"\n";
#define no cout<<"no"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define f(i,a) for(i=0;i<a;i++)
#define fo(i,a) for(i=1;i<=a;i++)
#define fa(i,a) for(auto i:a)
#define r(i,a) for(auto i=a.rbegin();i!=a.rend();i++)
#define en cout<<"\n";
#define ull unsigned long long int
#define o(x) cout<<x<<"\n";
#define o1(x) cout<<x<<" ";
#define pb push_back
#define F first
#define in insert
#define mp make_pair
#define S second
#define pre(n) cout<<fixed<<setprecision(n);
#define      gcd(a,b)    __gcd(a,b)
#define bs            binary_search
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define test ll t;cin>>t;while(t-->0)
const ll Mod = 998244353;
#define mod 1000000007
#define pi 3.14159265358979323846
#define re return 0;
// *#######################################################################################*
/*
ll prf(ll n)
{
    ll c=0,i;
    while(n%2==0)
    {
        n=n/2;
        c++;
    }
    for(i=3;i*i<=n;i++)
    {
        while(n%i==0)
    }
    
    
    
}
*/

int main()
{
      
   fast 
   ll n;cin>>n;
   ll a[n],i,c=1ll;
   
   f(i,n)
   {
       cin>>a[i];
   }
   f(i,n)
   {
       if(a[i]==0)
       {
           o("0")
           re
       }
   }
    f(i,n)
         {  ll p=(1000000000000000000/c);
           if(a[i]<=p)
           {
               c*=a[i];
           }
           else
           {
               o("-1")
               re
           }
       
       

   }
   
   
   
          o(c)

   
    re
}

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

int main(){
	char s[256];
	int i;
	fgets(s,sizeof(s),stdin);
	for(i=0;i<strlen(s);i++) if(97<=s[i]&&s[i]<=122) s[i]-=32;
	printf("%s",s);
	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(123456789012345678)


int main(void){
  int N;  cin >> N;
  int check = 1;
  vector<int> b, ans, tmp;
  rep(i, N) {
    int n;  cin >> n;
    b.push_back(n);
  }

  int i = N;
  while (b.size()) {
    if (i==b[i-1])  {
      ans.push_back(b[i-1]);
      b.erase(b.begin()+i-1);
      i = b.size();
    } else  {
      i--;
      if (i == 0)  {
        check = 0;
        break;
      }
    }
  }
  // while (b.size())  {
  //   REP(i, b.size()) {
  //     if (i+1==b[i])  {
  //       tmp.push_back(b[i]);
  //       b.erase(b.begin()+i-1);
  //       i = b.size()-1;
  //     }
  //   }
  //   if (tmp.size()==0)  {
  //     check = 0;
  //     break;
  //   }
  //   copy(tmp.begin(), tmp.end(), back_inserter(ans));
  //   tmp.clear();
  // }

  if (check)  {
    REP(i, N) {
      cout << ans[i] << endl;
    }
  } else  {
    cout << -1 << endl;
  }
	return 0;
}


Measured memory_bytes: 256
W = [48, 51, 54, 57, 60, 64, 69, 75, 81, 91]
C = ["light fly", "fly", "bantam", "feather", "light", "light welter", "welter", "light middle", "middle", "light heavy"]

while line = gets
  w, str = line.to_f, "heavy"
  
  W.each_index do |i|
    if w <= W[i]
      str = C[i]
      break
    end
  end
  
  puts str
end

Measured memory_bytes: 6108
DBG = !true
n = gets.to_i
a = gets.split.map{|z| z.to_i}
tol = Array.new(n)
tor = Array.new(n)
tol[0] = 1
gapl = []
1.upto(n-2) { |i|
  tol[i] = 1 + tol[i-1]
  if a[i-1] < a[i]
    ex = 0
    x = a[i-1]
    y = a[i]
    while x < y
      x *= 4
      ex += 2
    end

    prev = i
    dif = 0
    (gapl.size-1).downto(0) { |j|
      pos = gapl[j][0]
      dex = [gapl[j][1], ex].min
      dif += ex * (prev - pos)
      ex -= dex
      gapl[j][1] -= dex
      prev = pos
      if DBG
        puts "== ij #{i},#{j} pos:#{pos} dex #{dex} dif #{dif}"
        puts "   gapl[j][1] #{gapl[j][1]} prev #{prev} ex #{ex}"
      end
      if gapl[j][1] == 0
        gapl.delete_at(j)
      end
    }
    dif += ex * prev
    tol[i] += dif
  elsif a[i-1] >= 4*a[i]
    ex = -2
    y = a[i-1]
    x = a[i]
    while x <= y
      x *= 4
      ex += 2
    end
    gapl << [i, ex]
    puts "[#{i}, #{ex}] added to gapl" if DBG
  end
}
if DBG
  print "tol:"
  print tol
  puts ""
  print "gapl:"
  print gapl
  puts ""
end

tor[n-1] = 0
gapr = []
(n-2).downto(0) { |i|
  tor[i] = tor[i+1]
  if a[i] > a[i+1]
    ex = 0
    x = a[i+1]
    y = a[i]
    while x < y
      x *= 4
      ex += 2
    end

    prev = i
    dif = 0
    (gapr.size-1).downto(0) { |j|
      pos = gapr[j][0]
      dex = [gapr[j][1], ex].min
      dif += ex * (pos - prev)
      puts "dif+ #{dif} ex #{ex} pos #{pos} prev #{prev}" if DBG
      ex -= dex
      gapr[j][1] -= dex
      if gapr[j][1] == 0
        gapr.delete_at(j)
      end
      prev = pos
    }
    dif += ex * (n - prev - 1)
    puts "dif+ #{dif} ex #{ex} n #{n} prev #{prev}" if DBG
    tor[i] += dif
  elsif 4*a[i] <= a[i+1]
    ex = -2
    x = a[i]
    y = a[i+1]
    while x <= y
      x *= 4
      ex += 2
    end
    gapr << [i, ex]
    puts "[#{i}, #{ex}] added to gapr" if DBG
  end
}
if DBG
  print "tor:"
  print tor
  puts ""
  print "gapr:"
  print gapr
  puts ""
end

mn = tor[0]
for i in 1..(n-1)
  s = tol[i-1] + tor[i]
  mn = s if s < mn
end
print mn


Measured memory_bytes: 23076
#include <stdio.h>
 
int print_doc(n){
  if(n % 2 == 0) return n / 2;
  else return n / 2 + 1;
}
 
int main(){
  int a;
  
  scanf("%d", &a);
  
  printf("%d", print_doc(a));
  printf("\n");
  
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
 using namespace std;
 
 const long double PI = (acos(-1));
 
 int main(){
 	int A,B,H,M;
 	long double ans=0;
 	long double rad=0;
 	long double theta_m=0;
 	long double theta_h=0;
 	//入力受け取り
 	cin >> A >> B >> H >> M;
 	//分針、時針を円の割り合になおす
 	theta_m = (long double)M/60.0;
 	theta_h = (long double)H/12.0 + ((long double)M/60.0/12.0);
 	//内角の大きさを求めラジアンになおす
 	rad=(theta_h-theta_m)*2*PI;
 	//第二余弦定理に適用する
 	ans=A*A+B*B-2*A*B*cos(rad);
 	//ansは2乗の状態なのでrootを求める
 	ans=sqrt(ans);
 	cout << fixed << setprecision(20);
 	cout << ans << "\n";
 }

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


int main() {

    int x;
    cin >> x;
    rep(i,x/100+1) {
        if (100 * i <= x && x <= 105 * i) {
            cout << '1' << endl;
            return 0;
        }
    }
    cout << '0' << endl;
    return 0;
}

Measured memory_bytes: 256
a, b, k = map(int, input().split())

ans = set()
k = min(k,b-a+1)
for i in range(a, a+k):
    ans.add(i)

for i in range(b, b - k, -1):
    ans.add(i)

ans=sorted(list(ans))

for i in (ans):
    print(i)


Measured memory_bytes: 9080
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7


int main() {

	int T, C;
	scanf("%d%d", &T, &C);

	printf("%f", ((double)T) / C);




}

Measured memory_bytes: 128
m, d = map(int, input().split())
cnt = 0
for i in range(4, m+1):
    for j in range(1, d+1):
        if j >= 22:
            x = j // 10
            y = j % 10
            if x >= 2 and y >= 2 and (x * y) == i:
                cnt += 1
print(cnt)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

int N;
ull A[100];

bool judge(){
    REP(i,N){
        if(A[i] >= N) return false;
    }
    return true;
}

int main(){
    cin >> N;
    REP(i,N){
        ull a;
        cin >> a;
        A[i] = a;
    }

    ull ans = 0;
    while(!judge()){
        vector<ull> num(N);
        ull sum = 0;
        REP(i,N){
            ll a = A[i];
            if(a < N) continue;
            num[i] = (a+1)/N + ((a+1)%N != 0) - 1;
            sum += num[i];
        }
        REP(i,N){
            A[i] = A[i] - num[i]*N + (sum - num[i]);
        }
        ans += sum;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
List_S = [input() for i in range(N)]
List_S.sort()
List_S.append(-1)

result = []
count_list = []
count = 1
for i in range(N):
    if List_S[i] == List_S[i + 1]:
        count += 1
    else:
        result.append(List_S[i])
        count_list.append(count)
        count = 1

ma = max(count_list)

for i in range(len(result)):
    if count_list[i] == ma:
        print(result[i])


Measured memory_bytes: 22468
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int N, ans;

std::vector<int>divisor(int num)
{
	std::vector<int>res;
	for (int i = 1; i*i <= num; ++i)
	{
		if (num % i == 0)
		{
			res.push_back(i);
			if ((num / i) != i)
			{
				res.push_back(num / i);
			}
		}
	}
	return res;
}

int main()
{
	in >> N;
	for (int i = 1; i <= N; ++i)
	{
		if (i % 2 == 1)
		{
			auto tmp = divisor(i);
			if (tmp.size() == 8) ++ans;
		}
	}
	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i=0;i<n;i++)
#define REP1(i,n) for(long long i=1;i<=n;i++)
#define REP2D(i,j,h,w) for(long long i=0;i<h;i++) for(long long j=0;j<w;j++)
#define REP2D1(i,j,h,w) for(long long i=1;i<=h;i++) for(long long j=1;j<=w;j++)
#define PER(i,n) for(long long i=((n)-1);i>=0;i--)
#define PER1(i,n) for(long long i=(n);i>0;i--)
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define FORE(i,a,b) for(long long i=(a);i<=(b);i++)
#define ITE(arr) for(auto ite=(arr).begin();ite!=(arr).end();++ite)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define YNPRT(b) cout<<((b)?"Yes":"No")<<endl
#define REV(arr) reverse(ALL(arr))
#define PRT(a) cout<<a<<endl;
#define PRTLST(arr,num) REP(_i,num) cout<<_i<<" - "<<arr[_i]<<endl;
#define PRTLST2(arr2,d1,d2) REP(_i,d1) REP(_j,d2) cout<<_i<<","<<_j<<" : "<<arr2[_i][_j]<<endl;
#define PRTLST2D(arr2,d1,d2) do{cout<<"L\t";REP(_i,d2) cout<<_i<<"\t"; cout<<endl; REP(_i,d1){cout<<_i<<"\t";REP(_j,d2){cout<<arr2[_i][_j]<<"\t";}cout<<endl;}}while(0);
#define fst first
#define scd second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;
const int Move[4][2] = {-1,0,1,0,0,1,0,-1};
const int Move_[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};

//---------------------
#define MAXN 200000
//---------------------

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {ITE(v) os << *ite << " ";return os;}

ll n,a[MAXN],b[MAXN];
vector<pll> times; 
int main(){
	cin>>n;
	REP(i,n){
		cin>>a[i]>>b[i];
		times.push_back(pll(b[i],a[i]));
	}
	
	sort(ALL(times));
	ll ftime=0;
	bool ret=true;
	REP(i,times.size()){
	  ftime+=times[i].scd;
	  if(ftime>times[i].fst){
	  	ret=false;
	  	break;
	  }
	}
	YNPRT(ret);
	return 0;
}

Measured memory_bytes: 8304
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()

int main() {
	int a[7] = { 1,3,5,7,8,10,12 }, b[4] = { 4,6,9,11 }, c = 2, x, y,n,m;
	cin >> x >> y;
	REP(i, 7) if (a[i] == x)n = 1;
	REP(i, 4) if (b[i] == x)n = 2;
	if (c == x)n = 3;
	REP(i, 7) if (a[i] == y)m = 1;
	REP(i, 4) if (b[i] == y)m = 2;
	if (c == y)m = 3;
	if (n == m) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=3010;
int n,m,dp[maxn][maxn];
char s[maxn],t[maxn];
char ans[maxn];
struct node { int x,y,z; } lst[maxn][maxn];
void update(int a,int b,int c,int d,int f) {
	if (dp[a][b]+f>dp[c][d]) {
		dp[c][d]=dp[a][b]+f;
		lst[c][d]=(node){a,b,f};
	}
}
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%s",s+1);
	scanf("%s",t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++) {
		update(i-1,j,i,j,0);
		update(i,j-1,i,j,0);
		if (s[i]==t[j]) update(i-1,j-1,i,j,1);
	}
	int i=n,j=m,x,y,tot=0;
	while (i&&j) {
		x=lst[i][j].x,y=lst[i][j].y;
		if (lst[i][j].z) ans[++tot]=s[i];
		i=x,j=y;
	}
	for (int i=tot;i>=1;i--) printf("%c",ans[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 141696
K,A,B=list(map(int,input().split()))
hand=0
if B-A<=2:
    print(K+1)
    exit()
K=K-A+1
if K%2==1:
    hand=1+int((K-1)/2)*(B-A)
else:
    hand=int(K/2)*(B-A)
print(hand+A)

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

int main(){
	int w, h, n;
	cin >> w >> h >> n;
	int x, y, a;
	int space[w][h];
	for(int i = 0; i < w; i++){
		for(int j = 0; j < h; j++){
			space[i][j] = 0;
		}
	}
	
	for(int i = 0; i < n; i++){
		cin >> x >> y >> a;
		if(a == 1){
			for(int j = 0; j < x; j++){
				for(int k = 0; k < h; k++){
					space[j][k] = 1;
				}
			}
		}else if(a == 2){
			for(int j = x; j < w; j++){
				for(int k = 0; k < h; k++){
					space[j][k] = 1;
				}
			}
		}else if(a == 3){
			for(int j = 0; j < w; j++){
				for(int k = 0; k < y; k++){
					space[j][k] = 1;
				}
			}
		}else{
			for(int j = 0; j < w; j++){
				for(int k = y; k < h; k++){
					space[j][k] = 1;
				}
			}
		}
	}
	int count = 0;
	for(int i = 0; i < w; i++){
		for(int j = 0; j < h; j++){
			if(space[i][j] == 0)count++;
		}
	}
	cout << count << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <bitset>

using namespace std;

//#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

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

//static const ll MOD = 1000000007;
//static const ll INF = 100000000;

int main() {
    // input
    ll A, B;
    cin >> A >> B;

    // process
    ll ans = 6 - A - B;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define In_The_Name_Of_Allah_The_Merciful ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define Alhamdulillah return 0;
#define all(v) v.begin(),v.end()
#define debug(n) cerr << "[" << #n << " = " << n << "]" << endl 

void Suhaib_Sawalha (){

    string s , w;
    cin >> s >> w;

    vector <int> st[26];
    vector <int> :: iterator it;

    int n = s.size();
    for (int i = 0 ; i < n ; ++i)
        st[s[i]-'a'].push_back(i+1);

    for (char &c : w){
        if (st[c-'a'].empty()){
            cout << -1;
            return;
        }
    }

    int last = 0;
    ll ans = 0;
    for (char &c : w){
        it = upper_bound(all(st[c-'a']),last);
        if (it == st[c-'a'].end()){
            ++ans;
            it = st[c-'a'].begin();
        }
        last =  *it;
    }

    cout << ans * 1ll * (ll) n + 1ll * last;

}

int main(){
                                In_The_Name_Of_Allah_The_Merciful   /* بسم الله الرحمن الرحيم  */
#ifndef ONLINE_JUDGE
    freopen("SuhaibSawalha1.txt","r",stdin);
#endif
//int _;for(cin>>_;_;--_,cout<<'\n')
        Suhaib_Sawalha();
                                         Alhamdulillah                    /* الحمد لله */
}

Measured memory_bytes: 4148
import fractions
A,B,C,D=map(int,input().split())
E=C*D//fractions.gcd(C,D)
cnt=B-A+1-((B//C)-((A-1)//C))-((B//D)-((A-1)//D))+(((B//E)-((A-1)//E)))
print(cnt)

Measured memory_bytes: 5176
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
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; }
using Graph = vector<vector<int>>;
int fg(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}
signed main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a>=d){
   cout<<d;
  }
  else if(a+b>=d){
   cout<<a;
  }
  else{
    cout<<a-(d-a-b);
  }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1e9+7;

int main(){
    int k,a,b;
    cin >> k >> a >> b;
    bool flag = false;
    for(int i = a; i <= b; i++){
        if(i%k == 0) flag = true;
    }
    if(flag) cout << "OK";
    else cout << "NG";
    cout << endl;
}

Measured memory_bytes: 3676
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <functional>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <string>

using namespace std;

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)

ll const INF = 1000000000000000000;
int const I_MAX = 2147483647;
ll const MOD = 1e9 + 7;
int const POW_MAX = 1e5;

// nCr
ll po[POW_MAX + 2];
ll mod_pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}
ll mod_inv (ll x) {
  return mod_pow(x, MOD - 2) % MOD;
}
ll comb(int n, int r) {
  return (((po[n] * mod_inv(po[r])) % MOD) * mod_inv(po[n - r])) % MOD;
}
// greatest common divisor
ll gcd(ll a, ll b) {
  while (a % b != 0) {
    ll tmp = a;
    a = b;
    b = tmp % b;
  }
  return b;
}

int const H_MAX = 1000;
char const B = '#';

int H, W;
string A[H_MAX + 1];

queue<P> Q;
int values[H_MAX + 1][H_MAX + 1];

int main() {
  scanf("%d %d", &H, &W);
  rep(i, H) {
    cin >> A[i];
  }

  rep(i, H) {
    rep(j, W) {
      char c = A[i][j];
      if (c == B) {
        Q.push(P(j, i));
      } else {
        values[j][i] = I_MAX;
      }
    }
  }

  P ds[4] = { P(-1, 0), P(0, -1), P(1, 0), P(0, 1) };

  int count = 0;
  while (!Q.empty()) {
    P point = Q.front();
    Q.pop();

    int v = values[point.first][point.second] + 1;

    rep(k, 4) {
      P d = ds[k];
      int x = point.first + d.first;
      int y = point.second + d.second;
      if (x < 0 || y < 0 || x >= W || y >= H) continue;

      int n = values[x][y];

      if (v < n) {
        Q.push(P(x, y));
        values[x][y] = v;
        count = max(count, v);
      }
    }
  }
  printf("%d\n", count);
}


Measured memory_bytes: 11536
a = int(input())

b = []

for i in range(a):
	b.append(int(input()))

c = [[0] * 5 for i in range(a+1)]

for i in range(a):
	c[i+1][0] = c[i][0] + b[i]
	c[i+1][1] = min(c[i][0],c[i][1]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][2] = min(c[i][0],c[i][1],c[i][2]) + ((b[i]+1) % 2)
	c[i+1][3] = min(c[i][0],c[i][1],c[i][2],c[i][3]) + (b[i] % 2 if b[i] > 0 else 2)
	c[i+1][4] = min(c[i][0],c[i][1],c[i][2],c[i][3],c[i][4]) + b[i]

print(min(c[-1]))

Measured memory_bytes: 89936
r,d,x = map(int, input().split())
a =[]
s = r*x -d
for i in range(1,11):
  a.append(i)
  for j in range(len(a)):
    a[0] = s
    a[j] = r*a[j-1] -d
for e in a:
  print(e)

Measured memory_bytes: 3060
N = int(input())
A = [int(input()) for i in range(N)]

G = [1]
for i in range(N):
    G.append(A[G[-1]-1])
    
ans = 0
for i in range(N+1):
    if G[i]==2:
        break
    ans += 1
else:
    ans = -1
    
print(ans)

Measured memory_bytes: 13916
import sys


class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        if self.is_same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    uft = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(int, input().split())
        uft.unite(x, y)

    root = set()
    for i in range(1, N+1):
        root.add(uft.find(i))

    return len(root)


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 16784
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);

#define dbg1(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

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

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin() ) os << ", ";
		os << *it;
	}
	return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin()) os << ", ";
		os << *it;
	}
	return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
		if ( it != v.begin() ) os << ", ";
		os << it -> first << " = " << it -> second ;
	}
	return os << "]";
}

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)

clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)

void faltu () { cerr << endl; }

template <typename T>
void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
}

template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
// Program showing a policy-based data structure.
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less 
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
// GNU link : https://goo.gl/WVDL6g
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        new_data_set;

/**___________________________________________________**/



int main()
{
	FASTIO
	/*
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
#endif
//*/
	int T;
	//scanf("%d", &T);
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
		int n;
		cin >> n;
		int cnt = 0;
		map<int, bool> mp;
		while (n) {
			cnt++;
			if (mp[n])break;
			mp[n] = true;
			if (n & 1) n = 3 * n + 1;
			else n /= 2;
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 384
n = int(input())
ans = sum([(i + 1) * (n - i) for i in range(n)])
for i in range(n - 1):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    ans -= x * (n + 1 - y)
print(ans)


Measured memory_bytes: 80628
N, M = map(int, input().split())
G = [[] for _ in range(N)]
seen = [False] * N
for i in range(M):
    a, b = map(lambda x: int(x) - 1 ,input().split())
    G[a].append(b)
    G[b].append(a)

def dfs(x, G, seen):
    seen[x] = True
    flag = True
    for i in seen:
        if i == False:
            flag = False
    if flag:
        return 1
    res = 0
    for i in G[x]:
        if seen[i]:
            continue
        res += dfs(i, G, seen)
        seen[i] = False
    return res

print(dfs(0, G, seen))

Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;
	long long W, weight[110], v[110];
	cin >> W;
	for (int i = 0; i < N; ++i) {
		cin >> weight[i] >> v[i];
	}

	long long dp[110][100100] = { 0 };

	for (int i = 0; i < N; ++i) {
		for (long long j = 0; j <= W; ++j) {
			if (j < weight[i]) {
				dp[i + 1][j] = dp[i][j];
			}
			else {
				dp[i + 1][j] = max(dp[i][j], dp[i][j - weight[i]] + v[i]);
			}
		}
	}
	cout << dp[N][W] << endl;
}

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

#define rep(i,N) for(int i=0;i<(int)(N);++i)
#define rrep(i,N) for(int i=(int)(N)-1;i>=0;--i)
#define debug(x) cout<<#x<<"="<<x<<endl;
constexpr ll MOD=1000000007;
constexpr ll INF=1LL<<60;
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> void fail(T v){cout << v << endl;exit(0);}
//template end
int calc(int x,int y){
    return x*(100+y)/100;
}
void solve(){
    while(1){
        int x,y,s;
        cin>>x>>y>>s;
        if(!(x|y|s))break;
        int res=0;
        for(int i=1;i<s;i++)
            for(int j=1;j<s;j++){
                if(calc(i,x)+calc(j,x)!=s)continue;
                chmax(res,calc(i,y)+calc(j,y));
            }
        cout<<res<<endl;
            
            
    }
}

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


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

int main(void)
{
    int A, B, C, D;

    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;

    if (A + B > C + D){
        cout << "Left" << endl;
        return (0);
    }
    else if (A + B < C + D){
        cout << "Right" << endl;
        return(0);
    }
    else {
        cout << "Balanced" << endl;
        return(0);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#define min(x, y) (x > y ? y : x)
using namespace std;

int main(){
    int N;
    int T, A;
    int H[1000];
    int TEMP[1000];
    cin >> N;
    cin >> T >> A;
    
    for(int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        H[i] = tmp;
    }
    //calc temp*1000
    
    int tempdifmin = 10000000;
    int ans = 1001;
    for(int i = 0; i < N; i++)
    {
        TEMP[i] = T*1000 - 6*H[i];
        int tempdif = abs(TEMP[i] - A*1000);
        if (tempdifmin > tempdif){
            ans = i + 1;
            tempdifmin = tempdif;
        }
    }

    cout << ans << endl;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};

const int mod = 1000000007;
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 {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=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 {
    mint res(*this);
    return res/=a;
  }
};


int main(){
	int n;
	cin >> n;
	int zero = 0;
	map<Pll, P> mp;
	for(int i = 0; i < n; i++) {
		ll x, y;
		cin >> x >> y;
		if (x == 0 && y == 0) {
			zero++;
			continue;
		}
		if (y < 0) {
			x = -x;
			y = -y;
		}
		if(y == 0 && x < 0) {
			x = -x;
		}
		ll g = gcd(x, y);
		x /= g;
		y /= g;
		bool rot = (x <= 0);
		if(rot) {
			swap(x, y);
			y = -y;
		}
		if(rot) {
			mp[{x, y}].second++;
		} else {
			mp[{x, y}].first++;
		}
	}

	mint ans = 1;
	for(auto& e: mp) {
		int s = e.second.first;
		int t = e.second.second;
		mint now = 1;
		now += mint(2).pow(s)-1;
		now += mint(2).pow(t)-1;
		ans *= now;
	}
	ans-=1;
	ans += zero;
	cout << ans.x << endl;
}

Measured memory_bytes: 16104
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
import Data.Array
-- import Data.Array.Unboxed
import Control.Monad.ST
import Data.Array.ST

main :: IO ()
main = do
  n <- readLn :: IO Int
  s <- getLine :: IO String
  putStrLn $ solve n s

solve n s = map (proceed n) s
  where
    proceed i c = head . (drop i) . dropWhile (/=c) $ alphabet

alphabet = cycle ['A'..'Z']


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

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

   cout << n - i + 1 << endl;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll mod = 1000000007;


int main()
{
    char a[3][3];
    for(int i = 0; i < 3; i++)for(int j = 0; j < 3; j++)cin >> a[i][j];
    cout << a[0][0] << a[1][1] << a[2][2] << endl;
}

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

int h;
int w;

char buf[120];

int cnt[26];

int col[120][120];


int main(){
	cin >> h >> w;
	for (int i = 0; i < h; i++){
		scanf("%s", buf);
		for (int j = 0; j < w; j++){
			cnt[buf[j] - 'a']++;
		}
	}
	int odd = 0;
	int m2 = 0;
	int m4 = 0;
	for (int i = 0; i < 26; i++){
		if (cnt[i] == 0)continue;
		if (cnt[i] % 2){
			odd++;
			cnt[i]--;
		}
		if (cnt[i] % 4 == 0){
			m4+=4;
		}
		else{
			m2+=2;
		}
	}
	int H = -1;
	int W=-1;
	if (h % 2){
		H = h / 2;
	}
	if (w % 2){
		W = w / 2;
	}
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			if (i == H&&j == W){
				odd--;
				continue;
			}
			if (i == H||j==W){
				if (m2 == 0){
					m2 += 4;
					m4-=4;
				}
				m2--;
			}
		}
	}
	if (odd < 0){
		puts("No");
		return 0;
	}
	if (m2>0 || odd>0){
		puts("No");
	}
	else{
		puts("Yes");
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

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")
}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;

fn func(x:i32)->i32{
    if x/10==0 {return x;}
    x%10+func(x/10)
}

fn main() {
    let n:i32 = read();

    let mut mn:i32 = 100000;
    for i in 1..n {
        let a:i32 = i as i32;
        let b:i32 = n - i as i32;
        //debug!(i,func(a),func(b));
        mn = min(mn, func(a)+func(b));
    }

    println!("{}", mn);

}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  // Tenka1 Programmer Beginner Contest 2019 D - Three Colors
  // 三角形が作れる:総和をSとすると一辺の最大値がS/2未満でなければならない
  // 三角形が成立しない条件は逆:一辺の長さがS/2以上
  // R, G, B : Rを最大値として固定
  // dp[i][j]:各要素をRGBに塗り分けて、その色をi個目まで決めた時に、
  // Rを塗った要素の合計がjであるような場合の数
  // 状態遷移
  // i+1番目の要素をRに塗るとdp[i+1][j+a(i+1)] それ以外dp[i+1][j]
  // j>=S/2の和が成り立たない場合の数になる
  // GとBの場合を考えて3倍して、全事象3^Nから引く
  // 三角形が成立しないケースを重複して引いている（引き過ぎている）ので、そのケースを戻す
  // 例えばR=S/2, G=S/2, B=0
  // dp2[i][j]:各要素を2色で塗り分けて、i番目まで決めたときにRを塗った要素の合計が
  // jであるような場合の数。　dp2[N][S/2]
  // RG,GB,RBの3パターンあるので、3倍して足す
  int N; cin >> N;
  ll total = 0, mod = 998244353;
  vector<ll> a(N);
  REP(i, N){
    cin >> a[i]; total += a[i];
  }
  
  vector<vector<ll> > dp(301, vector<ll>(90001, 0));
  dp[0][0] = 1;
  REP(i, N){
    REP(j, total-a[i]+1){
      dp[i+1][j+a[i]] = dp[i][j];
      dp[i+1][j] = (dp[i+1][j] + (dp[i][j] * 2) % mod) % mod;
      // dp[i][j]からの遷移は他2色あるので*2
    }
  }
  
  vector<vector<ll> > dp2(301, vector<ll>(90001, 0));
  dp2[0][0] = 1;
  REP(i, N){
    REP(j, total-a[i]+1){
      dp2[i+1][j+a[i]] = dp2[i][j];
      dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % mod;
    }
  }
  
  ll ans = 1;
  REP(i, N) ans = (ans * 3) % mod; // 全事象の計算
  // オーバーフローしないように3をかけたらすぐにmodを取る
  
  for(int i = (total+1)/2; i < total+1; i++){
    ans = (ans + mod - (dp[N][i] * 3) % mod) % mod;
  }
  
  if(total%2 == 0){
    ans = (ans + dp2[N][total/2] * 3) % mod;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 424512
#include <bits/stdc++.h>
	#include <iostream>
	#include <string>
	#include <map>
	#include <math.h>
	#include <vector>
	using namespace std;
	map<int, int> ct;
	map<int, int> ct2;
	typedef vector<int> vi;
	typedef vector<vector<int> > vvi;
	typedef vector<pair<int, int> > vpii;
	typedef pair<int, int> pii;
	typedef long long ll;
	typedef long double ld;
	typedef pair<ll, ll> pll;
	typedef pair<double, double> pdd;
	typedef vector<ll> vll;
	#define INF 0x3f3f3f3f
	#define MOD 998244353LL
	#define EPS 0.00001
	#define f first
	#define s second
	#define pb push_back
	#define mp make_pair

	#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
	#define AFOR(i, a) for (int i=0; i<(signed)(a); i++)
	#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

	#define MN 100005
	int n, m, l;
	int a, b, c;
	string s[MN];
	string str;
	string ans;
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };

	/*
	int N;
	cin >> N;
	vi vect(N);
	FOR(i,N) cin >> vec.at(i);*/
	//sort(vec.begin(),vec.end());
	//vvi data(N,vi(4));

	
/*	int bfs(int x, int y,vvi &A,vvi flag) {
		queue<pii> que;
		que.push(pii(x, y));
		while (que.size()) {
			pii p = que.front(); que.pop();
			AFOR(i, 4) {
				int nx = p.first + dx[i]; int ny = p.second + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (A.at(p.first).at(p.second) + flag.at(p.first).at(p.second) < A.at(nx).at(ny)) {
						A.at(nx).at(ny) = A.at(p.first).at(p.second) + flag.at(p.first).at(p.second);
						que.push(pii(nx, ny));
					}
				}
			}
		}
		return 0;
	}
	*/

	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(0);
		long long sum = 0;
		int N;
		cin >> N;
		vi P(N * N);
		vvi A(N, vector<int>(N));
		vvi flag(N, vector<int>(N));

		AFOR(i, N) {
			AFOR(j, N) {
				flag.at(i).at(j) = 1;
			}
		}
	
		if (N % 2 == 0) {
			AFOR(i, N / 2) {
				AFOR(j, N / 2) {
					A.at(i).at(j) = min(i, j);
					A.at(N - i - 1).at(j) = min(i, j);
					A.at(N - i - 1).at(N - j - 1) = min(i, j);
					A.at(i).at(N - j - 1) = min(i, j);

				}
			}
		}
		else {
			AFOR(i, N / 2) {
				A.at(N / 2).at(i) = i;
				A.at(i).at(N / 2) = i;
				A.at(N-i-1).at(N /2) = i;
				A.at(N / 2).at(N - i - 1) = i;
				AFOR(j, N / 2) {
					A.at(i).at(j) = min(i, j);
					A.at(N - i - 1).at(j) = min(i, j);
					A.at(N - i - 1).at(N - j - 1) = min(i, j);
					A.at(i).at(N - j - 1) = min(i, j);

				}
			}
			A.at(N / 2).at(N / 2) = N / 2;

		}

		AFOR(i, N * N) {
			int x, y;
			cin >> P.at(i);
			x = P.at(i) / N;
			y = P.at(i) % N - 1;
			if (y == -1) {
				x = x - 1; y = y + N;
			}
			sum += A.at(x).at(y);
			flag.at(x).at(y) = 0;
			queue<pii> que;
			que.push(pii(x, y));
			while (que.size()) {
				pii p = que.front(); que.pop();
				AFOR(i, 4) {
					int nx = p.first + dx[i]; int ny = p.second + dy[i];
					if (0 <= nx && nx < N && 0 <= ny && ny < N) {
						if (A.at(p.first).at(p.second) + flag.at(p.first).at(p.second) < A.at(nx).at(ny)) {
							A.at(nx).at(ny) = A.at(p.first).at(p.second) + flag.at(p.first).at(p.second);
							que.push(pii(nx, ny));
						}
					}
				}
			}



		//	bfs(x, y, A,flag);
			//	cout << sum << endl;
		}


		cout << sum << endl;
		return 0;
	}

Measured memory_bytes: 9248
# スタック

a = input().split(" ")
stack = []

for x in a:
    if x == "+":
        a1 = stack.pop()
        a2 = stack.pop()
        a3 = a2 + a1
        stack.append(a3)
    elif x == "-":
        a1 = stack.pop()
        a2 = stack.pop()
        a3 = a2 - a1
        stack.append(a3)
    elif x == "*":
        a1 = stack.pop()
        a2 = stack.pop()
        a3 = a2 * a1
        stack.append(a3)
    elif x == "/":
        a1 = stack.pop()
        a2 = stack.pop()
        a3 = a2 / a1
        stack.append(a3)
    else:
        stack.append(int(x))

print(stack[0])



Measured memory_bytes: 5600
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

const int L_MAP = 50 + 2;
bool field[L_MAP][L_MAP];

const bool LAND = true;
const bool SEA = false;

void dfs(int x, int y){
    if(field[y][x] == SEA)
        return;

    field[y][x] = SEA;
    FOR(dy, -1, 1 + 1){
        FOR(dx, -1, 1 + 1){
            dfs(x+ dx, y + dy);
        }
    }
}

int main() {
    int w, h;
    while(cin >> w >> h, w|h){
        fill_n((bool *)field, L_MAP * L_MAP, SEA);
        REP(y, h){
            REP(x, w) {
                cin >> field[y + 1][x + 1];
            }
        }

        int cnt = 0;
        REP(y, h) {
            REP(x, w) {
                if (field[y + 1][x + 1] == LAND) {
                    dfs(x + 1, y + 1);
                    cnt ++;
                }
            }
        }

        cout << cnt << endl;
    }

}

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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int i=(first);i<(last);++i){cout<<#a<<"["<<i<<"] = "<<(a)[i]<<endl;}
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

using namespace std;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int c[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    REP(i, M) cin >> A[i];
    sort(all(A), greater<int>());

    set<int> s;
    REP(i, M) {
        s.insert(c[A[i]]);
    }

    vector<int> dp(N + 1, -1);
    dp[0] = 0;
    FOR(i, 1, N + 1) {
        for (int x: s) {
            int j = i - x;
            if (j >= 0 && dp[j] >= 0) {
                amax(dp[i], dp[j] + 1);
            }
        }
    }

    while (N > 0) {
        int index;
        int dp_max = -1;
        REP(i, M) {
            int N_next = N - c[A[i]];
            if (N_next >= 0 && dp_max < dp[N_next]) {
                dp_max = dp[N_next];
                index = i;
            }
        }
        cout << A[index];
        N -= c[A[index]];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
main = do
    s <- getLine
    let y = ans s
    print y
    
countzero :: String -> Int
countzero [] = 0
countzero (x:xs)
    | x == '0' = (countzero xs) + 1
    | otherwise = countzero xs
    
countone :: String -> Int
countone [] = 0
countone (x:xs)
    | x == '1' = (countone xs) + 1
    | otherwise = countone xs

ans :: String -> Int 
ans s = 2 * ( min (countzero s) (countone s) )


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

int main() {
    int n, k, s;
    cin >> n >> k >> s;
    vector<int > a;
    rep(i,k) a.push_back(s);
    if(k < n) {
        if(s==1e9) rep(i,n-k) {
            a.push_back(1);
        }
        else{
            rep(i,n-k) a.push_back(s+1);
        }
    }
    rep(i,a.size()) cout << a[i] << " ";
    cout << endl;
    return 0;
}

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

using vll = std::vector<long long>;
constexpr long long mod{1000000007};

int n;
bool edge[21][21]{};
std::vector<vll> mf;

long long rc(int, int);

int main()
{
	scanf("%d", &n);
	for (int i{}; i < n; i++)
		for (int j{}; j < n; j++)
		{
			int a;
			scanf("%d", &a);
			edge[i][j] = a == 1;
		}
	
	mf.resize(n + 1, vll(1 << n, -1));
	mf[n][(1 << n) - 1] = 1;
	for (int i{}; i + 1 < 1 << n; i++)
		mf[n][i] = 0;
	printf("%lld\n", rc(0, 0));

	return 0;
}

long long rc(int male, int set)
{
	long long& combi{mf[male][set]};
	if (combi >= 0) return combi;
	combi = 0;
	for (int female{}; female < n; female++)
	{
		if (!edge[male][female] || ((1 << female) & set)) continue;
		combi += rc(male + 1, set | (1 << female));
		combi %= mod;
	}
	return combi;
}

Measured memory_bytes: 377216