akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
    // Your code here!
    int A,B,H,M;
    double jishin[2], funshin[2];
    scanf("%d %d %d %d",&A, &B, &H, &M);
    
    double jiangle = 2*M_PI/12 * H + 2*M_PI/12/60 * M;
    jishin[0] = A * cos(jiangle);
    jishin[1] = A * sin(jiangle);
    
    double funangle = 2*M_PI/60 * M;
    funshin[0] = B * cos(funangle);
    funshin[1] = B * sin(funangle);
    
    printf("%.10lf\n", sqrt((jishin[0]-funshin[0])*(jishin[0]-funshin[0]) + (jishin[1]-funshin[1])*(jishin[1]-funshin[1])) );
}


Measured memory_bytes: 4164
from pprint import pprint as pp
def GI(): return int(raw_input())
def GIS(): return map(int, raw_input().split())

from math import sqrt
from itertools import izip

N = 10 ** 5

def main():
  primes = get_primes()
  n_p1_2 = [primes[(i+1)/2] for i in xrange(1, N+1)]
  n_p1_2[2] = 0

  s = 0
  c = []
  for p, n in izip(primes, n_p1_2):
    s += (p and n)
    c.append(s)

  #for i in xrange(0, 54):
  #  print i, ' - ', c[i], primes[i], n_p1_2[i]

  for _ in xrange(GI()):
    l, r = GIS()
    print c[r] - c[l-1]

def get_primes():
  a = [1] * (N + 1)
  a[0] = a[1] = 0

  for i in xrange(2, int(sqrt(N))):
    if not a[i]:
      continue
    for j in xrange(i ** 2, N+1, i):
      a[j] = 0

  return a

main()

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


vector<long long> a(51);

vector<long long> p(51);


long long f(long long x, long long y){

          if( x == 0 ) return 1;

          else if( y == 1 ) return 0;

          else if( y <= 1 + a.at(x - 1) ) return f( x - 1, y - 1 );

          else if( y == 2 + a.at(x - 1) ) return p.at(x - 1) + 1;

          else if( y <= 2 + 2 * a.at(x - 1) ) return 1 + p.at(x - 1) + f( x - 1, y - 2 - a.at(x - 1) );

          else if( y == 3 + 2 * a.at(x - 1) ) return 2 * p.at(x - 1) + 1;

          }


int main(){


    long long n, x, i, k;


    cin >> n >> x;


    a.at(0) = 1;

    p.at(0) = 1;


    for( i = 1 ; i <= n ; i = i + 1 ){

         a.at(i) = 3 + 2 * a.at(i - 1);

         p.at(i) = 1 + 2 * p.at(i - 1);

         }


    k = f(n, x);


    cout << k << endl;

    
    return 0;


    }


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

int main() {
	long long N, K, H[310], INF = 1000000000000000;
	static long long DP[310][310][310] = {};
	H[0] = 0;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> H[i];
	H[N + 1] = 0;
	for (int i = 0; i <= N + 1; i++) {
		for (int j = 0; j <= N + 1; j++) {
			for (int k = 0; k <= N + 1; k++) DP[i][j][k] = INF;
		}
	}
	DP[0][0][0] = 0;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= N; k++) {
				if (i != N) {
					DP[i + 1][j][k] = min(DP[i + 1][j][k], DP[i][j][k]);
				}
				DP[i + 1][j + 1][i + 1] = min(DP[i + 1][j + 1][i + 1], DP[i][j][k] + max(0LL, H[k] - H[i + 1]));
			}
		}
	}
	cout << DP[N + 1][N + 1 - K][N + 1] << endl;
}

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

using namespace std;

int gcd(int a,int b)
{
    return b==0? a:gcd(b,a%b);
}
int main()
{
    int k;
    cin>>k;
    int i,j,l;
    long long sum=0;
    for(i=1;i<=k;i++)
      for(j=1;j<=k;j++)
      {
          int r=gcd(i,j);
          for(l=1;l<=k;l++)
            sum+=gcd(r,l);
      }
      cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int h, w;
vector<string> g;

int bfs() {
	queue<pair<int, int>> que;
	que.emplace(0, 0);
	vector<vector<int>> dist(h, vector<int>(w));
	g[0][0] = '#';
	while (!que.empty()) {
		int x = que.front().second;
		int y = que.front().first;
		que.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || w <= nx || ny < 0 || h <= ny) {
				continue;
			} else if (g[ny][nx] == '#') {
				continue;
			} else if (nx == w - 1 && ny == h - 1) {
				dist[ny][nx] = dist[y][x] + 1;
				que.emplace(ny, nx);
				return dist[h - 1][w - 1];
			}
			dist[ny][nx] = dist[y][x] + 1;
			g[ny][nx] = '#';
			que.emplace(ny, nx);
		}
	}

	return dist[h - 1][w - 1];
}

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

	cin >> h >> w;

	g.resize(h);
	for (int i = 0; i < h; i++) {
		cin >> g[i];
	}

	int safe = 0;
	for (auto &s : g) {
		for (auto &c : s) {
			safe += c == '.';
		}
	}

	int cnt = bfs();
	cout << (cnt == 0 ? -1 : (safe - 1) - cnt) << endl;
	return 0;
}


Measured memory_bytes: 256
H,W=map(int,input().split())
if H>2 and W>2 and (H*W)%2==0:
    B=int((H*W)/2)
    print (B)
elif H>2 and W>2 and (H*W)%2==1:
    C=int((H*W+1)/2)
    print (C)
else:
    print (1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pb push_back
#define mp make_pair
 #define mod 1000000007
 const int N=100005;
 const int inf=1e18;
int pow(int a,int b){
    int res=1;
    while(b>0){
        if(b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
int fhash(string s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    int n=s.length();
    sort(s.begin(),s.end());
    cout<<s<<" ";
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n;
    cin>>n;
    string s[n];
    int h[n];
    for(int x=0;x<n;x++){
        cin>>s[x];
       sort(s[x].begin(),s[x].end());
    }
    sort(s,s+n);
   
    int ans=0;
    for(int x=0;x<n-1;x++){
        int c=1;
        while(s[x+1]==s[x]){
            c++;
            x++;
            if(x==n-1){
                break;
            }
        }
        ans+=(c*(c-1))/2;
    }
    cout<<ans;

	
	








	
return 0;
}


Measured memory_bytes: 5760
c = [[],[],[]]
c[0] = [int(x) for x in input().split()]
c[1] = [int(x) for x in input().split()]
c[2] = [int(x) for x in input().split()]

ans = "Yes"
for i in range(3):
    for j in range(3):
        if c[(i+1)%3][(j+1)%3] + c[(i+2)%3][(j+2)%3] != c[(i+2)%3][(j+1)%3] + c[(i+1)%3][(j+2)%3]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)

Measured memory_bytes: 38448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define Would
#define you
#define please

int main() {


	string S;
	cin >> S;

	int a = 0;
	int b = 0;
	int c = 0;
	rep(i, 3) {
		if (S[i] == 'a') a = 1;
		if (S[i] == 'b') b = 1;
		if (S[i] == 'c') c = 1;
	}

	if (a == 1 && b == 1 && c == 1)	co("Yes");
	else co("No");

	Would you please return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef long double ld;
ll A[100000];



int main() {
	ll x,y;
	cin >> x>>y;
	
	cout << x*y<<" "<<2*x+2*y << endl;
	return 0;
}





Measured memory_bytes: 3092
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
    double x,y=100;
    int count=0;
    cin>>x;
    while(y<x){
        ++count;
        y=floor(y*1.01);
    }
    cout<<count<<endl;
    return 0;}


Measured memory_bytes: 3724
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
r,s,p = LI()
t = input()
ans = 0
que = deque()
for i in range(n):
    if i < k:
        if t[i] == 'r':
            ans += p
            que.append('p')
        elif t[i] == 's':
            ans += r
            que.append('r')
        else:
            ans += s
            que.append('s')
    else:
        x = que.popleft()
        if t[i] == 'r' and x != 'p':
            ans += p
            que.append('p')
            continue
        elif t[i] == 's' and x != 'r':
            ans += r
            que.append('r')
            continue
        elif t[i] == 'p' and x != 's':
            ans += s
            que.append('s')
            continue
        if i+k < n:
            if t[i+k] == 'r':
                que.append('r')
            elif t[i+k] == 's':
                que.append('s')
            else:
                que.append('p')
        else:
            que.append(t[i])
print(ans)

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  int ans = 1;
  
  rep(i, 0, n) {
    ans = min(ans+k, 2*ans);
  }
    
  cout << ans << "\n";

}


Measured memory_bytes: 256
from itertools import product
n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    can_open.append(sum(1 << (c-1) for c in map(int, input().split())))

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j, (x, y) in product(range(n_bit), zip(can_open, cost)):
    m = j | x
    dp[m] = min(dp[m], dp[j]+y)

print(dp[-1] if dp[-1] != INF else -1)

Measured memory_bytes: 44776
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define loop(i, a, n) for(int i = (a); i < (n); i++)
#ifdef _DEBUG
#define dd(x) cout << #x << " : " << x << endl
#else
#define dd(x)
#endif
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b){
    while(b != 0){
        ll c = a%b;
        a = b;
        b = c;
    }
    return a;
}

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

ll nlcm(set<ll> a){
    ll res = *a.begin();
    for(ll num : a) res = lcm(res, num);
    return res;
}

int main(){
    ll n, m; cin >> n >> m;
    set<ll> a;
    rep(i, n) {
        ll tmp; cin >> tmp;
        a.insert(tmp/2);
    }

    ll min_a = *a.begin();
    ll two_pow = 1;
    while(min_a%2 == 0) {
        two_pow *= 2;
        min_a /= 2;
    }
    for(ll num : a) {
        ll tmp = num/two_pow;
        if(tmp%2 == 0 && tmp != 1) {
            cout << 0 << endl;
            return 0;
        }
    }

    ll base = nlcm(a);
    if(base > m) {
        cout << 0 << endl;
        return 0;
    }
    ll ans = m/base;
    cout << ((ans & 1)?ans/2+1:ans/2) << endl;
    return 0;
}


Measured memory_bytes: 4008
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#define NDEBUG
#endif
#include<bits/stdc++.h>
#define int long long
#define LL long long
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fi first
#define se second
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef pair<int,int>PII;typedef vector<int>VI;typedef vector<PII>VII;
template<typename T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<typename T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
int x;
void exgcd(int a,int b,int&x,int&y){
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
signed main(){
	rd(x);
	x*=2;
	vector<pair<int,int> >d;
	rep(i,2,x/i)while(x%i==0){
		if(d.empty()||d.back().fi!=i){
			d.EB(i,i);
		}else{
			d.back().se*=i;
		}
		x/=i;
	}
	if(x>1){
		d.EB(x,x);
	}
	int ans=1e18;
	rep(i,0,(1<<SZ(d))-1){
		int d1=1,d2=1;
		rep(j,0,SZ(d)-1)
			if(i>>j&1){
				d1*=d[j].se;
			}else{
				d2*=d[j].se;
			}
		int k1,k2;
		exgcd(d1,d2,k1,k2);
		if(k1<0){
			int t=(-k1)/d2+1;
			k1+=t*d2,k2-=t*d1;
		}
		int t=min((k1-1)/d2,(-k2-1)/d1);
		k1-=t*d2,k2+=t*d1;
		assert(k1*d1+k2*d2==1);
		D("%lld %lld\n",k1,d1);
		if(k1>0&&k2<0)ans=min(ans,k1*d1-1);
	}
	pt(ans,'\n');
	return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())


void solve() {
  int a[55];
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];
  REP(i, n) if(a[i] != i+1) {
    int b = a[i];
    a[i] = a[b-1];
    a[b-1] = b;
    break;
  }
  REP(i, n) if(a[i] != i+1) {
    cout << "NO" << endl;
    return;
  }
  cout << "YES" << endl;
}

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


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	LL R,C;
	cin >> R >> C;
	if( R>C ){
		swap(R,C);
	}
	if(R==1){
		if(C==1){
			cout << 1 << endl;
		}else if(C==2){
			cout << 0 << endl;
		}else{
			cout << C-2 << endl;
		}
	}else if(R==2){
		cout << 0 << endl;
	}else{
		cout << (R-2)*(C-2) << endl;
	}
	
}
#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
  int n, a[10001] = {};
  cin >> n;
  for (int i = 1; i <= 100; i++) {
    for (int j = 1; j <= 100; j++) {
      for (int k = 1; k <= 100; k++) {
        int x = i * i + j * j + k * k + i * j + j * k + k * i;
        if (x <= n) {
          a[x]++;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << endl;
  }
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FI first
#define SE second
#define endl "\n"
#define ciosup cin.tie(0);ios::sync_with_stdio(false);
#define eb emplace_back
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

int main()
{
    ciosup;
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << H * W - (h * W + w * H - h * w) << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(n: int, p: "List[int]"):
    ret = 0
    for p0, p1, p2 in zip(p, p[1:], p[2:]):
        s0, s1, s2 = sorted([p0, p1, p2])
        ret += int(s1 == p1)
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    p = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    result = solve(n, p)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5500
#include <bits/stdc++.h>
using namespace std;
int  absdiff(int t,int n,int arr[])
{
    int i,slow=0,shigh=0,result;
    for (i=0;i<t;i++){
            slow+=arr[i];
    }
  	for (i=t;i<n;i++){
      shigh+=arr[i];
    }
    if (slow>shigh)
        result=slow-shigh;
    else
        result=shigh-slow;
    return result;
}
int main()
{
    int ans=100000,u,N;
    cin>>N;
    int a[N];
    for (u=0;u<N;u++){
        cin >> a[u];
    }
    for (u=0;u<N;u++){
        if (absdiff(u,N,a)<ans){ans=absdiff(u,N,a);}
    }
    cout<<ans;
    return 0;
}


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

using namespace std;

int main(){
    string S, T;
    cin >> S >> T;
    
    // 1対1対応するか確認するための対応表
    vector<int> original(26, -1);
    vector<int> mapping(26, -1);
    
    for(int i = 0; i < S.length(); i++){
        int a = S[i] - 'a';
        int b = T[i] - 'a';
        
        // 写像元と写像先の対応が違えば、その時点ではじく
        if(original[a] != -1 || mapping[b] != -1){
            if(original[a] != b || mapping[b] != a){
                cout << "No\n";
                return 0;
            }
        }
        else{
            original[a] = b;
            mapping[b] = a;
        }
    }
    
    cout << "Yes\n";
}

Measured memory_bytes: 776
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
CSF = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]


def solve(from_i):
    t = 0
    for c, s, f in CSF[from_i:]:
        t = max(s, math.ceil(t / f) * f) + c
    return t


for i in range(N - 1):
    print(solve(i))
print(0)


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

int f[8]={1,1,2,3,5,8,13,21};
ll INF=1000000007;

ll solve(int h,int w,int s,int g){
    if(h==0){
        if(s==g) return 1;
        return 0;
    }
    if(h==1){
        if(s==g) return f[s-1]*f[w-s];
        if(s == g-1) return f[s-1]*f[w-s-1];
        if(s == g+1) return f[s-2]*f[w-s];
        return 0;
    }
    ll res=0;
    for(int i=1;i<=w;i++){
        res += solve(h/2,w,s,i)*solve(h-h/2,w,i,g)%INF;
    }
    return res%INF;
}

int main() {
    int h,w,k;
    cin >> h >> w >> k;
    cout << solve(h,w,1,k) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
#define inf 2147483647
#define rep(i,a,b) for(int i=a;i<b;i++)
#define  rr read()
#define ll long long
#define repb(i,a,b) for(int i=a;i<=b;i++)
#define CloseIo   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
ll read()
{
    char ch = getchar();
	int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int MOD=1e9+7,N=1e5+5;
ll n,m,step=0,ans=0;
map<ll,ll>mp;
int dp[N]={0};
int main()
{
  n=rr;m=rr;
  rep(i,0,m)
  {
  	 ll t=rr;
  	mp[t]=1;
  }
  dp[n]=1;
  for(int i=n-1;i>=0;i--)
  {
  	 if(mp[i]==1)
  	 {
  	 	dp[i]=0;
  	 	continue;
	   }
	   dp[i]=(dp[i+1]+dp[i+2])%MOD;
  }
  cout<<dp[0];
}




Measured memory_bytes: 6912
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n;
	cin >> n;
	VI a(n);
	REP(i, n) { cin >> a[i]; }
	int sum = 0;
	REP(i, n) { sum ^= a[i]; }
	REP(i, n) { cout << (sum ^ a[i]) << ' '; }
	cout << endl;
	return 0;
}


Measured memory_bytes: 4044
#D
S=input()
Q=int(input())
t=1 # 1:正順,0:逆順
fro=''
bac=''
for _ in range(Q):
    q=input()
    if q[0]=='1':
        t=(t+1)%2
    else:
        __,f,c=q.split()
        if f=='1':
            if t==1:
                fro=c+fro
            else:
                bac=bac+c
        else:
            if t==1:
                bac=bac+c
            else:
                fro=c+fro
    # print(S)
ans=fro+S+bac
print(ans if t else ans[::-1])

Measured memory_bytes: 4616
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>
#define fi first
#define se second
#define N 100005

using namespace std;
typedef long long ll;

template <class T> inline void read(T &x) {
	char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	if (flag) x = -x;
}

inline int input() {
	int x; char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return flag ? -x : x;
}

const int mod = 1e9 + 7;
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; }
inline void inc(int &x, int y) { x += y; x -= x >= mod ? mod : 0; }

inline int Power(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll) res * x % mod;
		x = (ll) x * x % mod, y >>= 1;
	} return res;
}

template <class T> void chkmax(T &x, T y) { x = x > y ? x : y; }
template <class T> void chkmin(T &x, T y) { x = x < y ? x : y; }
template <class T> T gcd(T x, T y) { return !y ? x : gcd(y, x % y); }

int q, A, B, C, D;

int main() {
	q = input();
	while (q--) {
		A = input(), B = input(), C = input(), D = input();
		int n = A + B, len = (max(A, B) - 1) / (min(A, B) + 1) + 1;
		int l = 0, r = n + 1, mid, ans;
		while (l < r) {
			mid = (l + r) >> 1;
			int a = A - mid / (len + 1) * len - mid % (len + 1);
			int b = B - mid / (len + 1);
			if (b <= (ll) a * len) l = mid + 1;
			else r = mid;
		}
		ans = l;
		int a = A - ans / (len + 1) * len - ans % (len + 1);
		int b = B - ans / (len + 1), P = ans + b - a * len + 1;
		for (int i = C; i <= min(D, ans); ++i) putchar(i % (len + 1) ? 'A' : 'B');
		for (int i = max(C, ans + 1); i <= D; ++i) putchar(abs(P - i) % (len + 1) ? 'B' : 'A');
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

typedef long long ll;

int main() {
    int n;  cin >> n;
    ll *a = new ll[n];
    ll sum = 0, x = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    ll ans = LLONG_MAX;
    for (int i = 0; i < n-1; i++) {
        x += a[i];
        ans = min(ans, abs(sum - 2*x));
    }

    cout << ans << endl;

    return 0;
}  

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define itrep(type, it, t) for(type::iterator it=t.begin(); it!=t.end(); it++)
using namespace std;


int main(void) {

    char c;
    cin >> c;
    cout << (char)(c+1);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 1000000000;
using namespace std;
int main() {
  int n, s;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a = 0, b = 0;
    bool key = 1;
    for (int j = 0; j < 10; j++) {
      cin >> s;
      if (s > a)
        a = s;
      else if (s > b)
        b = s;
      else
        key = 0;
    }
    cout << (key ? "YES" : "NO") << endl;
  }
  return 0;
}

Measured memory_bytes: 2980
#include<vector>
#include<iostream>
#include<numeric>
#include<list>
#include<limits>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<unordered_set>

#define pi 3.141592653589793
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

using namespace std;
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;

const long long MOD = 10e9 + 7;
const long long INF = 10e9 ;

template <typename T>
std::ostream& operator<<(ostream& os, 
                        const vector<T> &v)
{
    for (T const& i: v) {
        os << i << " ";
    }
    os<<endl;
    return os;
}

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
vector<int> sieve(int n){
    vector<bool> s(n, true);
    for(int i =2 ; i*i <= n; i++ )
        if(s[i])
            for(int j=2*i; j< n; j +=i )
                s[j] = false;

    vector<int> primes;
    for(int i =0; i<n; i++)
        if( s[i] )
            primes.push_back(s[i]);

    return primes;
}

int main(){
    int t;
    cin>>t;
    cout<< 2 * 3.1415 * t;

    return 0;
}

Measured memory_bytes: 3764
# https://atcoder.jp/contests/abc140/tasks/abc140_d
n, k = map(int, input().split())

s = input()
block = 0
start = 0
seg = []
block = 0
for i in range(n - 1):
    if s[i] == s[i + 1]:
        block += 1

ans = min(n - 1, block + k * 2)
print(ans)


Measured memory_bytes: 67844
n = int(input())
A = list(map(int, input().split()))

i = 1
ans = 1
flg = 0
for i, j in zip(A[:-1],A[1:]):
    if i < j:
        if flg == 0:
            flg = 1
        elif flg == 2:
            ans += 1
            flg = 0
    if i > j:
        if flg == 0:
            flg = 2
        elif flg == 1:
            ans += 1
            flg = 0
print(ans)

Measured memory_bytes: 86308
/*
 * ARC081_D.cpp
 *
 *  Created on: Jun 5, 2018
 *      Author: 13743
 */
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}

vector<bool> dom;

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

	int N;
	cin >> N;
	string line;
	cin >> line;
	cin >> line;


	REP(i, N) {
		if(i<N && line[i] == line[i+1]) {
			dom.pb(false);
			i++;
		}
		else {
			dom.pb(true);
		}
	}

	lng ans;
	if(dom[0] == true) ans = 3;
	else ans = 6;

	FOR(i, 1, SZ(dom)-1) {
		if(dom[i-1]&&dom[i]) ans *= 2;
		else if(dom[i-1]&&!dom[i]) ans *= 2;
		else if(!dom[i-1]&&dom[i]) ans *= 1;
		else ans *= 3;
		ans %= 1000000007;
	}

	cout << ans << endl;

}






Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cfloat>
#define zero(x) (((x)>0?(x):-(x))<eps)

#define pause cout << " press ansy key to continue...",  cin >> chh
#define file_r(x) freopen(x,  "r",  stdin)
#define file_w(x) freopen(x,  "w",  stdout)
#define lowbit(x) ((x) & (-x))
#define repit(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repe(i, u) for (int i = head[u]; i != -1; i = nxt[i])
#define repd(i, n) for (int i = (n - 1); i >= 0; i--)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
#define FORD(i, n, m) for (int i = (n); i >= (m); i--)
#define pb push_back
#define X first
#define Y second
#define ins insert
#define rb rbegin
#define be begin
#define er erase
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define SZ(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define sqr(r) ((r) * (r))
#define dis(x1, y1, x2, y2) (((x1) - (x2)) * ((x1) - (x2)) + ((y1) - (y2)) * ((y1) - (y2)))
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

#define sc(x) cout << #x" = " << x << endl, pause
#define sc2(x, y) cout << #x" = " << x << " " << #y" = " << y << endl, pause
#define sc3(x, y, z) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << endl, pause
#define sc4(x, y, z, w) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << " " << #w" = " << w << endl, pause

#define in(n) scanf("%d", &n)
#define in2(n, m) scanf("%d %d", &n, &m)
#define in3(x, y, z) scanf("%d %d %d", &x, &y, &z)

using namespace std;
int chh;

typedef vector<int> vi;
typedef set<int> si;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<int, pii> pi3;
typedef vector< pair<int, int> > vpii;
typedef long long LL;

const int N = 100005;

int n;
int a[N];

int main() {
    int ans, flag, id;
    while (~in(n)) {
        rep (i, n) in(a[i]);
        if (n == 1) {
            puts("1");
            continue;
        }
        ans = 0, flag = -1;
        FOR (i, 1, n - 1) {
            if (a[i] == a[i - 1]) continue;
            id = (a[i] - a[i - 1]) > 0;
            if (flag == -1) {
                flag = id;
                continue;
            }
            if (flag ^ id) ans++, flag = -1;
            // sc2(i, flag);
        }
        printf("%d\n", ans + 1);
    }
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
const ll MOD = (ll)1e9+7;
const ll INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

int mx[]={0, 0, 1, -1}, my[]={1, -1, 0, 0};
string dir = "ANan";

int func(char d){
	if('A'<=d&&d<='M')return 0;
	if('N'<=d&&d<='Z')return 1;
	if('a'<=d&&d<='m')return 2;
	if('n'<=d&&d<='z')return 3;
}

int main(){
	int n;
	string str;
	cin >> n >> str;
	int x = 0;
	int y = 0;
	foreach(i, str){
		int di = func(i);
		x += mx[di];
		y += my[di];
	}

	cout << abs(x)+abs(y) << endl;

	while(x){
		if(x>0){
			--x;
			cout << dir[2];
		}else{
			++x;
			cout << dir[3];
		}
	}

	while(y){
		if(y>0){
			--y;
			cout << dir[0];
		}else{
			++y;
			cout << dir[1];
		}
	}
	cout << endl;
	return 0;
}



Measured memory_bytes: 3336
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,a,b,c,d = LI()
    s = input()
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    if c == d:
        print("No")
    else:
        if c < d:
            k = s[b:d+1]
            for i in range(d-b):
                if k[i] == k[i+1] == "#":
                    print("No")
                    quit()
            k = s[a:c+1]
            for i in range(c-a):
                if k[i] == k[i+1] == "#":
                    print("No")
                    quit()
            print("Yes")
        else:
            k = s[b:d+1]
            for i in range(d-b):
                if k[i] == k[i+1] == "#":
                    print("No")
                    quit()
            k = s[a:c+1]
            for i in range(c-a):
                if k[i] == k[i+1] == "#":
                    print("No")
                    quit()
            k = s[b-1:d+2]
            for i in range(len(k)-2):
                if k[i] == k[i+1] == k[i+2] == ".":
                    print("Yes")
                    quit()
            print("No")
    return

#B
def B():
    def f(n):
        return n*(n+1)//2
    s = S()
    n = len(s)
    ans = 0
    i = 0
    while i < n-2:
        if s[i] == "A":
            if s[i+1] == "B":
                if s[i+2] == "C":
                    j = i
                    while j < n-2 and s[j] == "A" and s[j+1] == "B" and s[j+2] == "C":j += 3
                    j -= 3
                    l = i
                    r = j+2
                    while l >= 0 and s[l] == "A":l -= 1
                    while r < n and s[r-1] == "B" and s[r] == "C":r += 2
                    l += 1
                    r -= 2
                    a = i-l
                    b = (j-i)//3+1
                    c = (r-j)//2-1
                    for k in range(b+c):
                        s[2*k+l] = "B"
                        s[2*k+l+1] = "C"
                    for k in range(a+b):
                        s[k+l+2*(b+c)] = "A"
                    ans += f(b)+a*b+b*c+c*a
                    i = r
        i += 1
    print(ans)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()


Measured memory_bytes: 64240
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
  int N,A;
  int x[111];
  ll dp[111][111][5555];
int main() {
  
  cin >> N >> A;

  for(int i = 0;i<N;i++){
    cin >> x[i];
  }
  for(int i = 0;i<55;i++){
    for(int j = 0;j<55;j++){
      for(int k = 0;k<2550;k++){
    dp[i][j][k] = 0;
    }
   }
  }
  dp[0][0][0] = 1;
  for(int j = 0;j<=N;j++){
    for(int k = 0;k<=N;k++){
      for(int s = 0;s<=5550;s++){
  dp[j+1][k][s] += dp[j][k][s];
  if(s>=x[j]) dp[j+1][k+1][s] += dp[j][k][s-x[j]];
      }
    }
  }
  ll sum = 0;
  for(int k = 1;k<=N;k++){
  sum +=  dp[N][k][k*A];
  }
  
  
  cout << sum<< endl;
}


Measured memory_bytes: 243200
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;


int main()
{
    int a, b ;
    int n ;
    cin >> n ; 
    int x[n] , c = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] ;
    }
    for (int i = 0; i < n; i++)
    {
        int y; cin >> y; 
        if(x[i] - y > 0){
            c+=(x[i] - y);
        } 

    }
    cout << c << endl ;
    
    return 0 ;
}

Measured memory_bytes: 256
#define taskname ""

#include <iostream>
#include <algorithm>

using namespace std;
#define long long long

const int N = 1e5 + 10;

typedef pair<int, int> pii;
pii pack[N];
int n, total;
long f[N][110];

int main()
{
//    freopen(taskname".INP", "r", stdin);
//    freopen(taskname".OUT", "w", stdout);
    cin.tie(nullptr); ios_base::sync_with_stdio(false);

    cin >> n >> total;
    for (int i = 1; i <= n; ++i) cin >> pack[i].first >> pack[i].second;

    for (int sum = 1; sum <= total; ++sum)
        for (int i = 1; i <= n; ++i) {
            f[sum][i] = f[sum][i - 1];
            if (sum >= pack[i].first) f[sum][i] = max(f[sum][i], f[sum - pack[i].first][i - 1] + pack[i].second);
        }
    cout << f[total][n];

    return 0;
}


Measured memory_bytes: 86272
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

// namespace
using namespace std;
namespace mp = boost::multiprecision;

// types
using pii = pair<int, int>;
using ll = long long int;
using ld = long double;
using mpi = mp::cpp_int;
using mpf = mp::number<mp::cpp_dec_float<1024>>;

int main() {
    ll N, K, a;
    cin >> N >> K;
    a = N % K;
    a = min(a, N);
    a = min(a, K - (N % K));
    cout << a << endl;
    return 0;
}


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

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;

template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


bool solve(){
    int n, m;
    cin >> m >> n;
    vector<vector<double>> v(n, vector<double>(m));
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            cin >> v[j][i];

    vector<vector<double>> dp(n, vector<double>(1 << m, -1));

    function<double(int,int)> f = [&](int pos, int mask){
        if(dp[pos][mask] >= -0.5)
            return dp[pos][mask];
        dp[pos][mask] = 0;
        for(int k = 0; k < m; ++k){
            if(mask & (1 << k))
                continue;
            double per = 1.0;
            double ret = 0;
            for(int i = pos; i < n; ++i){
                ret += per * (1.0 - v[i][k]) * f(i, mask | (1 << k));
                per *= v[i][k];
            }
            ret += per;
            chmax(dp[pos][mask], ret);
        }
        return dp[pos][mask];
    };

    printf("%.20lf\n", f(0, 0));
    return false;
}

signed main(){
    while(solve());
}



Measured memory_bytes: 11716
#include<stdio.h>
#include<limits.h>
#define LIM  667000
int P,C[6] = {1,5,10,50,100,500};
int N[6],R[6],limit;
int clerk[LIM];
int i,j;
  

int getChange(int sum){ // clerk
  int ret = 0;
  int l;
  for(l=5;l>=0;l--){
    if(sum >= C[l]){
      ret += sum/C[l];
      sum -= sum/C[l]*C[l];
    }    
  }
  return ret;
}

int getChangeBy(int sum){
  int ret = 0;
  int index = sum;
  int e;
  for(e = 0;e<6;e++)R[e] = 0;
  for(e=5;e>=0;e--){
    if(sum >= C[e] && N[e] != 0){
      R[e] = sum/C[e]>N[e]?N[e]:sum/C[e];
      sum -= R[e]*C[e];
ret += R[e];      
    } 
  }
  if(sum != 0)return -1;
  return ret;
}

void createChange(){
  for(i=0;i<LIM;i++)clerk[i] = 0;
  int B,f;
  for(f=1;f<666001;f++){  
    B = getChange(f);
    clerk[f] = B;
    //if(f < 100)printf("%d\n",clerk[f]);
  }

}


int main(){
  createChange();
 
  while(scanf("%d",&P) && P){
    int cnt,pay,ans,res;

 
    
     limit = 0;
     int u;
     for(u=0;u<6;u++){
       scanf("%d",&N[u]);
       
       limit += N[u]*C[u];
     }

    
    ans = INT_MAX;
    for(i=0;i<limit;i++)clerk[i] = -1;
    for(i=P;i<=P+500;i++){
      cnt = getChangeBy(i); 
      if(cnt == -1 || ans <= cnt)continue;
      pay = 0;
      for(j = 0;j<6;j++)pay += C[j]*R[j];
      if(clerk[pay-P] == -1)clerk[pay-P] = getChange(pay-P);
      if(cnt+clerk[pay-P] < ans){
	ans = cnt+clerk[pay-P];
      }
    }
    printf("%d\n",ans);

  }
  return 0;
}

Measured memory_bytes: 3204
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define pb push_back
const ll mod = 1000000007;
const ll MAX_N = 510;

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

	vvl X(MAX_N, vl(MAX_N));
	rep(i, m) {
		ll l, r;
		cin >> l >> r;
        X[l][r]++;
	}

	vvl C(MAX_N, vl(MAX_N));
	exrep(i, 1, n) {
		exrep(j, 1, n) {
            C[i][j] = C[i][j-1] + X[i][j];
        }
	}
	
	rep(loop, Q) {
		ll p, q; 
        cin >> p >> q;
		ll ans = 0;
		exrep(i, p, q) { 
            ans += C[i][q] - C[i][p-1];
        }
		cout << ans << "\n";
	}

	return 0;
}

Measured memory_bytes: 4992
using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace debug
{
    class ProgramD
    {
        static void Main(string[] args)
        {

            //入力
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            var r = new List<int>();
            var g = new List<int>();
            int[] b = new int[n];
            long count = 0;

            //RかBかでそれぞれリストを作る
            for (int i = 0; i < n; i++)
            {
                if (s[i] == 'R')
                    r.Add(i + 1);
                else if (s[i] == 'G')
                    g.Add(i + 1);
                else
                    b[i] = 1;
            }

            int b_num = n - r.Count - g.Count;

            //Rの方を小さい順に取り出す
            foreach (var a1 in r)
            {
                var x = a1;
                foreach (var a2 in g)
                {
                    var y = a2;

                    //それぞれ
                    count += b_num;
                    if (2 * y - x - 1 >= 0 && 2 * y - x - 1 < n)
                        if (b[2 * y - x - 1] == 1)
                            count--;

                    if ((x + y) / 2 - 1 >= 0 && (x + y) / 2 - 1 < n && (x + y) % 2 == 0)
                        if (b[(x + y) / 2 - 1] == 1)
                            count--;

                    if (2 * x - y - 1 >= 0 && 2 * x - y - 1 < n)
                        if (b[2 * x - y - 1] == 1)
                            count--;
                }

            }

            //答え出力
            Console.WriteLine(count);


        }
    }

}


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

#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    string S;
    cin >> S;
    int N = S.size();
    REP(int,i,0,N){
        if ( i % 2 == 0 ){
            if ( S.at(i) == 'R' || S.at(i) == 'U' || S.at(i) == 'D' ) continue;
            else{ printf("No\n"); return 0;}
        }
        else{
            if ( S.at(i) == 'L' || S.at(i) == 'U' || S.at(i) == 'D' ) continue;
            else{ printf("No\n"); return 0;}
        }
    }
    printf("Yes\n"); return 0;
}

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

using namespace std;

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

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}

#define deb(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define END '\n'
#define inf 9e18
#define ff first
#define ss second
#define pb push_back

void solve(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << (((b * 10 + c) % 4 == 0) ? "YES" : "NO");
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3612
#include <vector>
#include <array>
#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <assert.h>
#include <queue>
#include <deque>
#include <iomanip>
#include <numeric>
#include <fstream>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fi first
#define se second

#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<ld>> vvd;
typedef vector<string> vs;
typedef vector<bool> vb;

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


int main() {
    cout << setprecision(30);
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    const ll MAXX = 1e9;
    ll k, x;
    cin >> k >> x;
    ll l = max(-MAXX, x - k + 1);
    ll r = min(+MAXX, x + k - 1);
    for (ll i = l; i <= r; ++i) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256