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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define ppi pair<int, int>
#define endl "\n"
#define nl cout << "\n"
#define deb(x) cout << #x << " " << x << endl;

const int N = 1010;
const int mod = 1e9 + 7;
int H, W;
char grid[N][N];

// dp[i][j] = #Ways to reach from (i, j) to (H, W)
int dp[N][N];

int Top_Down(int x = 1, int y = 1) {
    // Base Case
    if(x == H && y == W) return (dp[x][y] = 1);
    // Choice
    if(dp[x][y] != -1) return dp[x][y];
    int ways = 0;
    if(x <= H && grid[x+1][y] == '.') ways += Top_Down(x+1, y)%(mod);
    if(y <= W && grid[x][y+1] == '.') ways += Top_Down(x, y+1)%(mod);
    return (dp[x][y]=ways%(mod));
}

int32_t main() {
    IOS;
    memset(dp, -1, sizeof(dp));
    cin >> H >> W;
    for(int i = 1; i <= H; ++i) 
        for(int j = 1; j <= W; ++j) {
            cin >> grid[i][j];
        }
    //
    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j)
            if((i == H and j == W) and grid[i][j]=='.') dp[i][j] = 1;
    }
    cout << Top_Down()%(mod) << endl;
    // for(int i = 1; i <= H; ++i){
    //     for(int j = 1; j <= W; ++j) cout << dp[i][j] << " ";
    //     cout << endl;
    // }
}

Measured memory_bytes: 9344
"use strict";
function Main(input) {
    let A = input.split("\n").map((v) => v - 0);
    let B = new Array(5);
    for (let n = 0; n < 5; n++) {
        let r = A[n] % 10;
        B[n] = [A[n], (r) ? 10 - r : 0];
    }
    B.sort((a, b) => a[1] - b[1]);
    let ans = 0;
    for (let n = 0; n < 5; n++) {
        ans += B[n][0] + ((n < 4) ? B[n][1] : 0);
    }
    console.log(ans);
}
if (typeof window === 'undefined') Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 2147483647;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 2000005;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[SIZE], finv[SIZE], inv[SIZE];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

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

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

double len(int a, int b, int c, int d) {
	return (double)sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

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

	queue<ll>cars;
	vector<queue<ll>>nums(N);
	for (int i = 0; i < M; ++i) {
		ll f, a;
		cin >> f >> a; --a;
		if (f == 0) {
			cout << nums[a].front() + 1 << std::endl;
			nums[a].pop();
		}
		else {
			ll minN = 114514810, minI;
			for (int j = 0; j < N; ++j) {
				if (minN > nums[j].size()) {
					minN = nums[j].size();
					minI = j;
				}
			}
			nums[minI].push(a);
		}
	}
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF             1e14
#define dd              double
#define MOD             1000000007
#define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) 
#define nl              cout<<endl
#define fill(a,val)     memset(a,val,sizeof(a))
#define mp              make_pair
#define endl            "\n"
#define pb              push_back
#define ff              first    
#define ss              second
#define SIZE            200005
#define all(v)          v.begin(),v.end()
#define s(ar,n)         sort(ar,ar+n)
#define rs(ar,n)        sort(ar, ar+n, greater<ll>()) 
#define oa(a,n)         for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n)         for(ll i=0;i<n;i++)cin>>a[i];
#define maxa(ar,N)      *max_element(ar,ar+N)
#define mina(ar,N)      *min_element(ar,ar+N)
#define fastio()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define printclock      cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
ll power(ll x, ll y){
    ll res=1;x=x;
    while(y>0){
        if(y&1)
            res = (res*x);
        y = y>>1;
        x = (x*x);
    }
    return res;
}  
ll logtwo(ll n){
    if(n==1)
        return 0;
    return logtwo(n/2)+1;
}
signed main()
{
    fastio();   
    int t=1;
    //cin>>t;
    while(t--)
    {
        ll r;
        cin>>r;
        cout<<fixed<<setprecision(5)<<2*3.1415*r<<endl;
    }
}

Measured memory_bytes: 3808
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}



vector< int > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  vi res;
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }

  rep(i,n+1){
    if(prime[i]) res.PB(i);
  }
  return res;
}




bool is_square(int n){
  ll l=0,r=110000;
  while(r-l>1){
    ll m=(r+l)/2;
    if(m*m>n) r=m;
    else l=m;
  }


  return (l*l==n);
}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n;
  map<int,int> mp;
  vi prime=prime_table(2500);
  vi a,b;
  cin>>n;
  rep(i,n){
    int s;
    cin>>s;
    int t=1,u=1;

    for(int p:prime){
      int c=0;
      while(s%p==0){
        c++;
        s/=p;
      }
      
      c%=3;
      if(c==0) continue;
      if(c==1){
        t*=p;
        u*=p*p;
      }
      else{
        t*=p*p;
        u*=p;
      }
    }
    if(is_square(s)){      
      t*=s;
      u*=sqrt(s);
    }else{
      t*=s;
      u*=s*s;
    }

    //cout<<t<<' '<<u<<endl;
      
    a.PB(t);
    b.PB(u);
    mp[t]++;
  }

  int ans=0;

  rep(i,n){
    if(a[i]==1) continue;
    //cout<<a[i]<<' '<<b[i]<<endl;
    ans+=max(mp[a[i]],mp[b[i]]);
    //cout<<ans<<endl;
    mp[a[i]]=0;
    mp[b[i]]=0;
  }

  cout<<ans+!!mp[1]<<endl;
}

Measured memory_bytes: 14312
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,s;
long long f(long long x,long long y)
{
	long long re=0;
	while(x!=0)
	{
		re+=x%y;
		x/=y;
	}
	return re;
}
int main()
{
	scanf("%lld %lld",&n,&s);
	long long e=n-s;
	if(n==s)
	{
		printf("%lld",n+1);
		return 0;
	}
	if(e<0)
	{
		printf("-1\n");
		return 0;
	}
	long long jans=9223372036854775807ll;
	for(long long i=1;i*i<=e;i++)
	{
		if(e%i==0)
		{
			long long ans=i+1;
			if(f(n,ans)==s)
			{
				jans=min(jans,ans);
			}
			ans=e/i+1;
			if(f(n,ans)==s)
			{
				jans=min(jans,ans);
			}
		}
	}
	if(jans!=9223372036854775807ll)
		printf("%lld\n",jans);
	else
	{
		printf("-1\n");
	}
}

Measured memory_bytes: 256
import Control.Monad
import qualified Data.Vector.Unboxed as UV
import Data.List
import qualified Data.ByteString.Char8 as B

r3 [a,b,c]=(a,b,c)
main = do
    n<-readLn::IO Int
    xs<-UV.replicateM n $ r3.unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine
    print $ f n xs
f n xs = (\(a,b,c)->maximum [a,b,c]) $ UV.foldl' p (0,0,0) xs where
    p (u,v,w) (a,b,c) = (max y z, max x z, max x y)
        where (x,y,z)=(u+a,v+b,w+c)

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

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

void erat(int m,vector<bool>&v,vector<ll>&p){
    v.clear(),p.clear();
    v.resize(m);
    v[0]=v[1]=true;
    for(int i=2;i*i<m;++i) if(!v[i]) for(int j=i*i;j<m;j+=i) v[j]=true;
    fr(i,m) if(!v[i]) p.emplace_back(i);
}

int_fast64_t issq(int_fast64_t n){
    int_fast64_t m=(sqrt(n)-.5);
    if(m*m==n) return m;
    ++m;
    if(m*m==n) return m;
    return -1;
}

class DAnticube {
public:
    void solve(istream& in, ostream& out) {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        int n;
        in>>n;
        vector<bool> v;
        vector<ll> p,q,r;
        erat(100001,v,p);
        for(auto i:p){
            if(i>2154) break;
            q.emplace_back(i);
            r.emplace_back(i*i*i);
        }
        ll s;
        bool f=false;
        unordered_set<ll> st;
        unordered_map<ll,int> mp;
        fr(_,n){
            in>>s;
            for(auto i:r) while(s%i==0) s/=i;
            if(s==1){
                f=true;
                continue;
            }
            st.insert(s);
            ++mp[s];
        }
        ll ans=f,b,A;
        int c,cnt;
        for(auto a:st){
            c=mp[a];b=1;
            if(c==0) continue;
            for(auto i:q){
                cnt=0;
                while(a%i==0) a/=i,++cnt;
                if(cnt) b*=i;
                if(cnt==1) b*=i;
                if(b>10000000000) break;
            }
            if(b>10000000000){
                ans+=c;
                continue;
            }
            if(a>1){
                if(a<100001&&!v[a]){
                    b*=a;
                    if(b>10000000000){
                        ans+=c;
                        continue;
                    }
                    b*=a;
                    if(b>10000000000){
                        ans+=c;
                        continue;
                    }
                }
                else{
                    A=issq(a);
                    if(A<0){
                        ans+=c;
                        continue;
                    }
                    b*=A;
                    if(b>10000000000){
                        ans+=c;
                        continue;
                    }
                }
            }
            ans+=max(c,mp[b]);
            mp[b]=0;
        }
        out<<ans<<endl;
    }
};

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


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

int main() 
{
    string num;

    while( cin >> num )
    {
        int sum = 0;

        if( num.size() == 1 && num[0] == '0' )        //文字配列の大きさが1かつ値が0なら終了. 0が文字であることに注意
            break;

        for( int i = 0; i < num.size(); i++ )
        {
            int x = num[i] - '0';                   //文字としての数字を、整数型としての数字に変換
            sum += x;   
        }

        cout << sum << endl;
    }

    return 0;
}


Measured memory_bytes: 3228
#include <iostream>

int main () {

  int i, j, x, answer;
  int num_of_ary0, num_of_ary1;
  int ary0[10010];

  answer = 0;

  std::cin >> num_of_ary0;
  for (i = 0; i <= num_of_ary0 - 1; i++) std::cin >> ary0[i];

  std::cin >> num_of_ary1;
  for (i = 0; i <= num_of_ary1 - 1; i++) {

    std::cin >> x;

    for (j = 0; j <= num_of_ary0 - 1; j++) {

      if (x == ary0[j]) {

        answer ++;
        break;
      }
    }
  }

  std::cout << answer << std::endl;
  return 0;
}



Measured memory_bytes: 3140
s = int(input())
m = int(s**0.5)

l = s - m*m
if l<0:
    m = m-1
    l = s - m*m



if l < 1000000000 and m < 1000000000:
    print(0,1,m,0,l,m+1)
    #print(m*m + l)
elif m == 1000000000:
    print(0,0,m,0,0,m)
else:
    l = (m+1)*(m+1)-s
    if l < 1000000000:
        print(0,0,m+1,1,l,m+1)
    else:
        for i in range(2,int(l**0.5) +1):
            if l%i == 0:
                t =i
                break
        print(0,0,m+1,t,l//t,m+1)


Measured memory_bytes: 38384
import java.util.Scanner;

/**
 * Favorite Sound
 *
 */
public class Main {
  private static final String DELIMITER = " ";

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String[] lines = scanner.nextLine().split(DELIMITER);
    // 1回a円、b円持っている、c回聞くと満足
    int a = Integer.valueOf(lines[0]);
    int b = Integer.valueOf(lines[1]);
    int c = Integer.valueOf(lines[2]);

    int balance = b;
    int count = 0;
    for (int i = 0;i < c; i ++) {
      if (balance > 0 && balance >= a) {
        count += 1;
        balance -= a;
      } else {
        break;
      }
    }

    System.out.println(count);
  }
}

Measured memory_bytes: 23380
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)


Measured memory_bytes: 61648
n = int(input())
A = list(map(int, input().split()))
sumA = 0
A_ = [0] + A + [0]
for i in range(1, n+2):
    sumA += abs(A_[i]-A_[i-1])
for i in range(1, n+1):
    if (A_[i] - A_[i-1])*(A_[i+1]-A_[i])<0:
        print(sumA-abs(A_[i] - A_[i-1])-abs(A_[i+1]-A_[i])+abs(A_[i+1]-A_[i-1]))
    else:
        print(sumA)

Measured memory_bytes: 14048
from collections import deque
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    x=deque([])
    y=deque([])
    for i in range(n):
        if i%2==1:
            y.appendleft(a[i])
        else:
            x.append(a[i])
    z=[]
    for u in y:
        z.append(u)
    for u in x:
        z.append(u)
    print(*z)
else:
    x=deque([])
    y=deque([])
    for i in range(n):
        if i%2==0:
            y.appendleft(a[i])
        else:
            x.append(a[i])
    z=[]
    for u in y:
        z.append(u)
    for u in x:
        z.append(u)
    print(*z)

Measured memory_bytes: 25540
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}
int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}


int main(){
  string s,p;
  cin>>s>>p;
  cout<<"A"<<p[0]<<"C"<<endl;
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 256
N=int(input())
a=len(str(N))#aの桁数
if a==1:
    print(N)
    exit()
else:
    ans=9*(a-1)#Nより1桁少ない値での最大値


    
    for i in range(a):
        y=0
        if i==0:
            for j in range(a):
                y+=int(str(N)[j])
            #print(N)
        else:
            x=str(int(str(N)[:a-i])-1)+"9"*i
            if len(x)!=a:
                x="0"*(a-len(x))+x
            for j in range(a):
                y+=int(x[j])
           # print(x,y)
        if ans<y:
            ans=y
print(ans)

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

int main(){
    lint x, y;
    cin >> x >> y;
    lint l = 0, r = 1, d = 1, u = 1; // [l, r), [d, u)
    rep(i, 1000000){
        lint l2, r2, u2, d2;
        if(i % 2 == 0){
            l2 = l;
            r2 = r;
            if(i % 4 == 0){ // 下
                u2 = d;
                d2 = u2 - (r - l);
            }else{ // 上
                d2 = u;
                u2 = d2 + (r - l);
            }
        }else{
            d2 = d;
            u2 = u;
            if(i % 4 == 1){ // 右
                l2 = r;
                r2 = l2 + (u - d);
            }else{ // 左
                r2 = l;
                l2 = r2 - (u - d);
            }
        }
        if(l2 <= x && x < r2 && d2 <= y && y < u2){
            cout << i % 3 + 1 << endl;
            return 0;
        }
        //cout << l2 << " " << r2 << " " << d2 << " " << u2 << endl;
        l = min(l, l2);
        r = max(r, r2);
        d = min(d, d2);
        u = max(u, u2);
    }
}





Measured memory_bytes: 3092
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		int result = 0;
		for (int i = 0; i < 2; i++) {
			if (a == b || a > b) {
				result += a;
				a--;
			} else if (a < b) {
				result += b;
				b--;
			}
		}
		System.out.println(result);
	}
}

Measured memory_bytes: 22484
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    class ClassMain {

        public static void Main(String[] args) {
            string line;

            while ((line = Console.ReadLine()) != null) {
                string[] strs = line.Split(' ');
                string className = strs[0];
                int gozen = int.Parse(strs[1]);
                int gogo = int.Parse(strs[2]);
                Console.WriteLine(className+" "+(gozen+gogo)+" "+(gozen*200+gogo*300));

            }
        }
    }

}

Measured memory_bytes: 5612
int main()
{
    char c[2][3];
    int i,j;
    int flag;
    for(i=0;i<2;i++)
    {
        for(j=0;j<3;j++)
        {
            scanf("%c",&c[i][j]);
        }
        getchar();
    }
    for(j=0;j<3;j++)
    {
        if(c[0][j]!=c[1][2-j])
        {
            flag=1;
            break;
        }
        else {flag=0;
        continue;}
    }
    if(flag==0)
    printf("YES");
    else printf("NO");
    
}

Measured memory_bytes: 128
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <map>
#include <cmath>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int keta;
    keta = log10(n)+1;

    int num[10] = {0};
    
    for (int i=1; i<=keta; i++) {
        int a = 1,b = 1;
        for (int j=0; j<i; j++) {
            a *= 10; b *= 10;
        }
        b*=10;

        int c;
        c = n % b;
        c = c / a;
        num[c]++;
    }

    bool ans = false;
    for (int i=0; i<10; i++) {
        if (num[i] >= 3) {
            ans = true;
        }
    }

    if (ans) {
        printf("Yes \n");
    } else {
        printf("No \n");
    }

    return 0;
}

Measured memory_bytes: 512
n,t=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
ab.sort()
dp=[6007*[0]for _ in range(n)]
for i in range(n):
  a,b=ab[i]
  for j in range(6007):
    if i==0:
      if j>=a and j<t:dp[i][j]=b
    elif j>=a and j-a<t:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(max(dp[-1]))

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

int main() {
  int N, K, X ,Y;
  cin >> N >> K >> X >> Y;
  if (K > N){
    cout << N * X << endl;
  }
  else{
  cout << X * K + (N - K) * Y << endl;
  }
}


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

int count(vector<char>& x, int ii) {
	set<char> s1;
	set<char> s2;

	for (int i = 0; i <= ii; ++i) {
		s1.insert(x[i]);
	}	

	for (int i = ii + 1; i < x.size(); ++i) {
		s2.insert(x[i]);
	}

	set<char>::iterator it;
	int ret = 0;

	for (it = s1.begin(); it != s1.end(); ++it) {
		if (s2.find(*it) != s2.end()) {
			ret++;
		}
	}

	return ret;
}

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

	vector<char> s(n);
	for (int i = 0; i < n; ++i) {
		char tmp;
		cin >> tmp;
		s[i] = tmp;
	}

	int ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		ans = max(ans, count(s, i));
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        sx: i32,
        sy: i32,
        tx: i32,
        ty: i32,
    }
    let tx = tx - sx;
    let ty = ty - sy;
    let mut v = Vec::<char>::new();
    for _ in 0..ty { v.push('U'); }
    for _ in 0..tx { v.push('R'); }
    for _ in 0..ty { v.push('D'); }
    for _ in 0..tx+1 { v.push('L'); }
    for _ in 0..ty+1 { v.push('U'); }
    for _ in 0..tx+1 { v.push('R'); }
    v.push('D');
    v.push('R');
    for _ in 0..ty+1 { v.push('D'); }
    for _ in 0..tx+1 { v.push('L'); }
    v.push('U');
    println!("{}",
        v.into_iter().collect::<String>());
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define PI 3.1415926535
const long long int MOD = 1000000007;
#define pb push_back
#define mp make_pair
#define fill(a)  memset(a, 0, sizeof (a))
#define SORT(v)  sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define MAX(v) *max_element(v.begin(), v.end())
#define MIN(v) *min_element(v.begin(), v.end())
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define watch(x) cout << (#x) << " is " << (x) << endl;
const long long int MAXX = 1e5+5;
const long long int MINN = 2e6 + 5;
const long long int inf = 1e7;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector< iii > viii;

ll lcm(ll a, ll b) {
   return a / __gcd(a, b) * b;
}
int XOR(int x, int y){
  return (x | y) & (~x | ~y);
}
bool cmp(const pair<int,int> &a,const pair<int,int> &b) {
    return (a.second < b.second);
}
// bool isl = binary_search(x.begin(), x.end(), 5);
// __builtin_popcount(x)  - Returns the number of set bits in x
const long long int N = 5e5+5;
const int MAXN = 105;
int binsearch(int lo, int hi){
    while(lo<hi){
        int mid=(lo+hi)/2;
        if((mid))   // check(mid)
            hi=mid;
        else
            lo=mid+1;
    }
    return lo;
}
int power(int x,int y){
    int res=1;
    while(y>0){
      if(y&1) res=((res*x));

      y/=2;
      x=((x*x));
    }
    return res;
}

ll a,b,c,d;
int main(){
    FAST    
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        if(s=="AC") a++;
        else if(s=="WA") b++;
        else if(s=="TLE") c++;
        else d++;
    }
    cout<<"AC x "<<a<<"\n";
        cout<<"WA x "<<b<<"\n";

    cout<<"TLE x "<<c<<"\n";

    cout<<"RE x "<<d<<"\n";


    return 0;
}



Measured memory_bytes: 3656
A,B,C,D=map(int,input().split())
if C>D:
  c=D
  d=C
else:
  c=C
  d=D
  
f=B//d
g=(A-1)//d
h=B//c
i=(A-1)//c
  
while c:
  c,d=d%c,c
j=C*D//d
k=B//j
l=(A-1)//j
print(B-A+1-(f-g+h-i-k+l))




Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using pil = pair<int, long>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

struct Node{
  int now;
  //int sub;
  long rec;
};

bool operator<(const Node &a, const Node &b){
  if(a.rec != b.rec){
    return a.rec < b.rec;
  }else{
    return a.now < b.now;
  }
}
bool operator>(const Node &a, const Node &b){return (b < a);}
bool operator<=(const Node &a, const Node &b){return !(b < a);}
bool operator>=(const Node &a, const Node &b){return !(a < b);}

//vector<vector<pair<int,long>>> Graph : from -> pair<int,long> to, cost

vector<long> Dijkstra(vector<vector<pair<int,long>>> &Graph, int s){
  priority_queue<Node, vector<Node>, greater<Node>> que;
  vector<long> dist(Graph.size(), 1e16);

  dist.at(s) = 0;
  que.push(Node{s, 0});

  while(que.size()){
    Node node = que.top();
    que.pop();
    if(node.rec > dist.at(node.now)) continue;

    for(pair<int,long> nP : Graph.at(node.now)){
      int next = nP.first;
      long cost = nP.second;
      if(dist.at(next) > dist.at(node.now) + cost){
        dist.at(next) = dist.at(node.now) + cost;
        que.push(Node{next, dist.at(next)});
      }
    }
  }
  
  return dist;
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<vector<pair<int,long>>> Graph(3*n);
  rep(i,m){
    int u,v;
    cin >> u >> v;
    u--;v--;
    rep(j,3){
      Graph.at(u*3+j).push_back(pil(v*3+(j+1)%3, 1));
    }
  }
  int s,t;
  cin >> s >> t;
  s--;t--;
  vector<long> dist = Dijkstra(Graph, 3*s);
  if(dist.at(3*t) == 1e16) cout << -1 << endl;
  else cout << dist.at(3*t)/3 << endl;
}

Measured memory_bytes: 18944
#include<bits/stdc++.h>
using namespace std;
//#define int long long

//ask the right questions.  

// dp[i][j] means maximum subsequence length when we have seen upto ith index in s and jth index in t.    

int dp[3001][3001];
int choices[3001][3001];

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int m = t.length();

    //trivial case;
    for(int i=0;i<n;i++)
        dp[i][0]=0;
    for(int i=0;i<m;i++)
        dp[0][i]=0;


    //iteratin gover items (not indexes in dp equation)
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //not equal: cannot include
            if(s[i-1]!=t[j-1]){
                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                if(dp[i-1][j]>=dp[i][j-1])
                    choices[i][j]=1;
                else
                    choices[i][j]=2;
            }
            else{//equal: choice is to include or not
                //not-include to initialize dp[i][j]
                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                if(dp[i-1][j]>=dp[i][j-1])
                    choices[i][j]=1;
                else
                    choices[i][j]=2;
                //now see whetther inclusion maximises over non inclusion
                dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
                if(dp[i][j]<=dp[i-1][j-1]+1)
                    choices[i][j]=3;
            }
        }
    }

    // dp matrix

    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=m;j++){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    // choice matrix

    // cout << endl; 
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=m;j++){
    //         cout << choices[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    //cout << dp[n][m] <<endl;                //max length of common subsequence
    int i = n; int j = m;
    string ans="";
    while(i>0 && j>0)
    {
        if(choices[i][j]==1)
        {
            //cout << "choice 1" <<endl;
            //cout << i << " " <<j <<endl;
            i--;
        }
        else if (choices[i][j]==2)
        {
            //cout << "choice 2" <<endl;
            //cout << i << " " <<j <<endl;
            j--;
        }
        else
        {
            ans+=s[i-1];
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans <<endl;

    return 0;
}



Measured memory_bytes: 73932
N=int(input())
if N<=111:
	print(111)
elif 111<N<=222:
	print(222)
elif 222<N<=333:
	print(333)
elif 333<N<=444:
	print(444)
elif 444<N<=555:
	print(555)
elif 555<N<=666:
	print(666)
elif 666<N<=777:
	print(777)
elif 777<N<=888:
	print(888)
elif 888<N<=999:
	print(999)

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

int print_stderr_permutation(vector<int> &v);

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

	vector<int> a(m);
	vector<int> b(m);
	for (int i=0;i<m;++i)
	{
		cin >> a.at(i) >> b.at(i);
	}

	vector<int> p(n);
	for (int i=0;i<n;++i)
	{
		p.at(i)=i+1;
	}

	int count=0;
	do
	{
		//print_stderr_permutation(p);

		if (p[0]!=1)
		{
			continue;
		}

		int i,j;
		for (i=0;i<n-1;++i)
		{
			int aa=p[i];
			int bb=p[i+1];
			for (j=0;j<m;++j)
			{
				if ( ((a[j]==aa)&&(b[j]==bb)) || ((a[j]==bb)&&(b[j]==aa)) )
				{
					break;
				}
			}
			if (j>=m)
			{
				break;
			}
		}
		if (i>=n-1)
		{
			//fprintf(stderr," -> meets condition\n");
			++count;
		}

	}
	while (next_permutation(p.begin(),p.end()));

	cout << count << endl;

}


int print_stderr_permutation(vector<int> &v)
{
	int size=v.size();
	fprintf(stderr,"trying ");
	for (int i=0;i<size;++i)
	{
		fprintf(stderr,"%d ",v[i]);
	}
	fprintf(stderr,"\n");
	return 0;
}



Measured memory_bytes: 256
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define l long
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<int,int>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
    
    ll a,b,k;
    cin>>a>>b>>k;
    ll ha = min(a,k);
    a -= ha;
    k -= ha;
    if(k) b -= min(b,k);
    cout<<a<<" "<<b;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

    int n;
    cin >> n;
    double d[n*2+2];
    double p[n];
    double last=0;
    double temp;

    for(int i=0;i<n;i++)
        cin >> p[i];

    for(int i=0;i<n*2+2;i++)
        d[i]=0;

    d[n]=p[0];
    d[n+1]=1-p[0];

    for(int i=1;i<n;i+=2)
    {
        double head=p[i]*p[i+1];
        double tile=(1-p[i])*(1-p[i+1]);
        double same=1-head-tile;

        for(int j=n-i;j<=n+1+i;j++)
        {
            temp=last*tile+d[j]*same+d[j+1]*head;
            last=d[j];
            d[j]=temp;
        }
    }

    double sum=0;
    for(int i=1;i<=n;i++)sum+=d[i];
    cout << sum << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  string s;
  cin >> s;
  map<char, ll> mp;
  rep(i, s.size()) mp[s[i]]++;
  bool ans = true;
  for(auto v : mp)
    if(v.second % 2) ans = false;
  cout << (ans ? "Yes" : "No") << endl;
}

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

int main() {
  ll N,h,a,b;
  cin >> N;
  r(n,3500){
    r(w,3500){
      if(4*n*w-N*w-N*n>0){
      h=N*n*w/(4*n*w-N*w-N*n);
      a=4*h*n*w; b=N*(h*w+n*w+n*h);
      if(a==b&&h>0){
        cout << n << " "<< h << " " << w<<endl;
        return 0;
      }
      }
    }
  }
}


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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

const int INF = 1e9;
int V, E;
int dist[15][15];
int dp[1 << 15][15];

int rec(int S, int v) {
  if (0 <= dp[S][v]) {
    return dp[S][v];
  }
  if (S == (1 << V) - 1 && v == 0) {
    return dp[S][v] = 0;
  }
  int res = INF;
  REP(u, V) {
    if (!(S >> u & 1)) {
      res = min(res, rec(S | 1 << u, u) + dist[v][u]);
    }
  }
  return dp[S][v] = res;
}

int main() {
  cin >> V >> E;
  REP(i, V) REP(j, V) {
    dist[i][j] = INF;
    if (i == j) dist[i][j] = 0;
  }
  REP(i, E) {
    int s, t, d;
    cin >> s >> t >> d;
    dist[s][t] = d;
  }
  REP(i, 1 << V) REP(j, V) dp[i][j] = -1;
  int ans = rec(0, 0);
  cout << (ans == INF ? -1 : ans) << endl;
  return 0;
}


Measured memory_bytes: 4924
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  int a,b;
  cin>>a>>b;
  REP(i,max(a,b))cout<<min(a,b);
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
import sys
from functools import reduce

def gcd(a, b): return gcd(b, a % b) if b else abs(a)
def lcm(a, b): return abs(a // gcd(a, b) * b)

n, m, *a = map(int, sys.stdin.read().split())

def main():
  for i in range(n):
    a[i] //= 2

  b = set()
  for x in a:
    cnt = 0
    while x % 2 == 0:
      x //= 2
      cnt += 1
    b.add(cnt)
  if len(b) == 2: print(0); return

  l = reduce(lcm, a, 1)
  res = (m // l + 1) // 2
  print(res)

if __name__ == '__main__':
  main()

Measured memory_bytes: 14588
#include<bits/stdc++.h>
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define pb push_back
#define sevensins ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define mod  1000000007
#define vect vector<long long int>
#define bins binary_search
#define vecti vector<int>::iterator
#define bitout __builtin_popcount
int main() 
{sevensins
    ll i,j,k,l,n;
    string s,t;
    cin>>s>>t;
    ll flag=1;
    for(i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
        {
            flag=0;
            break;
        }
    }
    
    if(flag)
    cout<<"Yes\n";
    else
    cout<<"No\n";
    
    
return 0;
}

Measured memory_bytes: 3636
def dfs(now,flags):
    global graph
 
    if len(flags) == len(graph)-1:
        return 1

    flags.add(now)
    ans = 0
    for vis in graph[now]:
        if not vis in flags:
            #print(vis,flags)
            ans += dfs(vis,flags)
    flags.remove(now)
    return ans



ans = 0
nums = [int(x) for x in input().split()]
N, M = nums[0], nums[1]
graph = {i:[] for i in range(1,N+1)}

for i in range(M):
    nums = [int(x) for x in input().split()]
    graph[nums[0]].append(nums[1])
    graph[nums[1]].append(nums[0])

print(dfs(1,set()))

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

int main(){
  int N,K;
  cin >> N >> K;
  string S;
  cin >> S;
  
  S.at(K-1)=tolower(S.at(K-1));
  
  cout << S << endl;
}

Measured memory_bytes: 384
def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

if __name__=='__main__':
  main()

Measured memory_bytes: 206020
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
#include<unordered_map>
#include<sstream>
#include<numeric>
#include<stack>
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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やllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------

int main(){
  string S;
  cin >> S;
  int cnt_odd=0,cnt_even=0;
  for(int i=0; i<S.size(); i++){
    if(i%2){
      if(S[i] != '0') cnt_odd++;
      else cnt_even++;
    }else{
      if(S[i] != '1') cnt_odd++;
      else cnt_even++;
    }
  }
  cout << min(cnt_odd,cnt_even) << endl;
  return 0;
}


Measured memory_bytes: 512
package main

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

var scanner = bufio.NewScanner(os.Stdin)

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

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

func newGraph(nNodes int) *Graph {
	g := Graph{}
	g.nodes = make([]*GraphNode, nNodes)
	for iNode := 0; iNode < len(g.nodes); iNode++ {
		g.nodes[iNode] = &GraphNode{}
		g.nodes[iNode].key = GraphNodeKey(iNode)
	}
	return &g
}

var infty = 1000000000

type GraphNodeKey int

// GraphNode is a node for undirected graph
type GraphNode struct {
	key       GraphNodeKey
	adjacents []*GraphNode
	visited   bool
	d, f      int
	parent    *GraphNode
	cc        int

	low             int // 22-2 c.
	is_articulation bool
}

func (g *Graph) setAdjacent(l, r GraphNodeKey) {
	g.nodes[l].adjacents = append(g.nodes[l].adjacents, g.nodes[r])
}

// Graph is a undirected graph
type Graph struct {
	nodes []*GraphNode
}

func (g *Graph) initialize() {
	for iNode := 0; iNode < len(g.nodes); iNode++ {
		g.nodes[iNode].visited = false
		g.nodes[iNode].d = infty
		g.nodes[iNode].f = infty
		g.nodes[iNode].parent = nil
		g.nodes[iNode].cc = -1 // 22.3-12
	}
}

var time = 0
var visitedNodes = []*GraphNode{}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func dfsVisit(g *Graph, u *GraphNode, cc int) {
	time++
	u.d = time
	u.cc = cc

	u.visited = true
	for _, v := range u.adjacents {
		if !v.visited {
			v.parent = u
			dfsVisit(g, v, cc)
		}
	}
	time++
	u.f = time
	visitedNodes = append(visitedNodes, u)
}

func runDFS(g *Graph) {
	g.initialize()
	time = 0
	cc := 0

	for _, u := range g.nodes {
		if !u.visited {
			dfsVisit(g, u, cc)
			cc++
		}
	}
}

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

	nNodes := nextInt()
	nEdges := nextInt()
	graph := newGraph(nNodes)
	for iEdge := 0; iEdge < nEdges; iEdge++ {
		l := GraphNodeKey(nextInt())
		r := GraphNodeKey(nextInt())
		graph.setAdjacent(l, r)
		graph.setAdjacent(r, l)
	}

	runDFS(graph)

	for _, node := range visitedNodes {
		node.low = node.d
		node.is_articulation = false

		for _, adjacent := range node.adjacents {
			if adjacent.parent == node { // G_\pi上で node -> adjacent
				node.low = min(node.low, adjacent.low)
				node.is_articulation = node.is_articulation || (node.parent != nil && adjacent.low >= node.d)
			} else if adjacent != node.parent { // G上では繋がっているが、G_\pi上では繋がっていない
				node.low = min(node.low, adjacent.d)
			}
		}

		nChildren := 0
		for _, adjacent := range node.adjacents {
			if adjacent.parent == node {
				nChildren++
			}
		}
		node.is_articulation = node.is_articulation || (node.parent == nil && nChildren >= 2)
	}

	for _, node := range graph.nodes {
		// fmt.Println(node.key, node.d, node.low, node.is_articulation)

		if node.is_articulation {
			fmt.Println(node.key)
		}
	}
}



Measured memory_bytes: 8864
import math
A = list(map(int, input().split()))
H = A[0]
W = A[1]

first = math.ceil(H/2)
second = math.floor(H/2)
if H>= 2 and W>=2:
  ans = math.ceil(W/2)*first + math.floor(W/2)*second
elif W==1:
  ans = 1
elif H==1:
  ans = 1
  
print(ans)

Measured memory_bytes: 9084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e15;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// __uint128_t
const ll MOD = 1e9+7;

int main(){
    ll R, C, K; cin >> R >> C >> K;
    vector<vector<ll>> V(R, vector<ll>(C));
    for(int i = 0; i < K; i++){
        ll r, c, v; cin >> r >> c >> v; r--; c--;
        V[r][c] = v;
    } 
    vector<vector<vector<ll>>> DP(R, vector<vector<ll>>(C, vector<ll>(4)));
    DP[0][0][1] = DP[0][0][2] = DP[0][0][3] = V[0][0];
    for(int r = 0; r < R; r++){
        for(int c = 0; c < C; c++){
            if(r == 0 && c == 0) continue;
            for(int k = 0; k < 4; k++){
                ll U = 0, L = 0;
                
                if(k == 0){
                    if(r-1 >= 0) DP[r][c][k] = max(DP[r-1][c][3], DP[r][c][k]);
                    if(c-1 >= 0) DP[r][c][k] = max(DP[r][c-1][0], DP[r][c][k]);
                }
                else {
                    if(r-1 >= 0) U = DP[r-1][c][3] + V[r][c];
                    if(c-1 >= 0) L = max(DP[r][c-1][max(k-1, 0)]+V[r][c], DP[r][c-1][k]);
                    DP[r][c][k] = max(max(U, L), DP[r][c][k]);
                }                
            }
        }
    }
    cout << DP[R-1][C-1][3] << endl;
    

}

Measured memory_bytes: 706676
#include <iostream>
#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;

#define SIZE_MAX 20
#define N_MAX 11
#define INF 99999999

int W, H;
char M[SIZE_MAX][SIZE_MAX];
int N;
int D[N_MAX][N_MAX];

struct A {
  int x, y, cost;
  A(int x, int y, int cost) : x(x), y(y), cost(cost) {}
};

void bfs(int n, int sx, int sy) {
  const int dx[4] = {1,0,-1,0};
  const int dy[4] = {0,1,0,-1};
  bool vsted[SIZE_MAX][SIZE_MAX];
  queue<A> que;
  A a(sx, sy, 0);

  que.push(a);
  for(int i = 0; i < H; ++i) {
    fill(vsted[i], vsted[i] + W, false);
  }
  vsted[sy][sx] = true;

  while(!que.empty()) {
    a = que.front(); que.pop();

    if(isupper(M[a.y][a.x])) {
      int t = M[a.y][a.x] - 'A';
      if(D[n][t] == INF) {
	D[n][t] = D[t][n] = a.cost;
      }
    }

    for(int i = 0; i < 4; ++i) {
      int nx = a.x + dx[i];
      int ny = a.y + dy[i];
      if(nx < 0 || nx >= W) continue;
      if(ny < 0 || ny >= H) continue;
      if(M[ny][nx] == 'x') continue;
      if(vsted[ny][nx]) continue;
      vsted[ny][nx] = true;
      que.push(A(nx, ny, a.cost + 1));
    }
  }
}

void show() {
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
      if(D[i][j] == INF) cout << "IF" << "  ";
      else       cout << D[i][j] << "  ";
    }
    cout << endl;
  }
}

void makeD(int rx, int ry) {
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
      D[i][j] = i == j ? 0 : INF;
    }
  }

  bfs(0, rx, ry);
  for(int y = 0; y < H; ++y) {
    for(int x = 0; x < W; ++x) {
      if(isupper(M[y][x])) bfs(M[y][x]-'A', x, y);
    }
  }
}

void solve(int rx, int ry) {
  makeD(rx, ry);
  int dp[1 << N_MAX][N_MAX];
  for(int i = 0; i < 1<<N_MAX; ++i) {
    fill(dp[i], dp[i] + N_MAX, INF);
  }
  dp[1 << 0][0] = 0;
  for(int s = 1 << 0 + 1; s < (1 << N); ++s) {

  }
}

int calcCost(int v[]) {
  int now = 0;
  int cost = 0;
  for(int i = 0; i < N-1; ++i) {
    cost += D[now][v[i]];
    now = v[i];
  }
  return cost;
}

void solve2(int rx, int ry) {
  makeD(rx, ry);
  int v[N_MAX];
  for(int i = 1; i < N; ++i) {
    v[i-1] = i;
  }
  int ans = INF;
  do {
    ans = min(ans, calcCost(v));
  } while(next_permutation(v, v + (N-1)));
  if(ans == INF) ans = -1;
  cout << ans << endl;
}

main() {
  while((cin >> W >> H) && (W || H)) {
    N = 1;
    int rx, ry;
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
	cin >> M[i][j];
	if(M[i][j] == 'o') { rx = j; ry = i; }
	if(M[i][j] == '*') M[i][j] = 'A' + N++;
      }
    }
    solve2(rx, ry);
  }
}

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

#define MAX_W 100010
#define MAX 110

long long dp[MAX][MAX_W];
long long weight[MAX],	value[MAX];

int main(){
	for(int i=0;i<MAX;i++){
		for(int j=0;j<MAX_W; j++){
			dp[i][j]=0;
		}
	}
	int n,w;	cin>>n>>w;
	for(int i=0;i<n;i++){
		cin>>weight[i]>>value[i];
	}

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

			dp[i+1][W]=max(dp[i+1][W],	dp[i][W]);
		}
	}

	//for(int i=0;i<=n;i++){
	//	for(int j=0;j<=w;j++)printf("%3d ",dp[i][j]);
	//	cout<<endl;
	//}

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





	return 0;
}


Measured memory_bytes: 86144