akhauriyash/Code-Regression huggingface dataset:
import math
import itertools
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
point_range = range(n)


def length(point1, point2):
    delx = point1[0]-point2[0]
    dely = point1[1]-point2[1]
    return math.pow(delx*delx + dely*dely, 0.5)


def main():
    count = 0
    ways = math.factorial(n)
    for route in itertools.permutations(point_range, n):
        for i in range(len(route)-1):
          count += length(points[route[i]], points[route[i+1]])

    print(count / ways)

main()

Measured memory_bytes: 40560
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    X=LI()
    ans = inf
    for a in range(100+1):
        res = 0
        for x in X:
            res += (x-a)**2
        ans = min(ans, res)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 66284
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    A_cum = [0] * (N + 1)
    for i in range(N):
        A_cum[i+1] = A_cum[i] + A[i]

    ans = 0
    cnt = collections.Counter(A_cum)
    for i in cnt.values():
        ans += i * (i - 1) // 2

    print(ans)

if __name__ == '__main__':
    resolve()


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  auto b = a;
  sort(b.begin(), b.end(), greater<int>());
  for (auto &x : a) {
    int ans = (x == b[0]) ? b[1] : b[0];
    cout << ans << '\n';
  }
  return 0;

  
}

Measured memory_bytes: 3200
O = input()
E = input()
 
ans = ""
if len(O) == len(E):
    for i in range(len(O)):
        ans = ans + O[i]+E[i]
else:
    for i in range(len(E)):
        ans = ans + O[i]+E[i]
    ans = ans + O[-1]
print(ans)

Measured memory_bytes: 38384
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>

using namespace std;

int main(void){

  int a,b,c;
  int k;

  cin>>a;
  cin>>b;
  cin>>c;
  cin>>k;

  int sum=a+b+c;

  cout << (long long int)(max({a,b,c})*pow(2,k)+sum-max({a,b,c})) << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

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

  int H[N];
  rep(i,0,N-1) cin >> H[i];

  int ans=0,cnt=0;
  rep(i,1,N-1) {
    if (H[i-1] >= H[i]) {
      cnt++;
      ans = max(ans, cnt);
    } else cnt = 0;
  }

  cout << ans << endl;
  return 0;
}


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

int main(){

    while(1){
        int m, f, r;
        scanf("%d %d %d", &m, &f, &r);
        if(m == -1 && f == -1 && r == -1){
            return 0;
        }else{
            if(m == -1 || f == -1){
                cout << "F" << endl;
            }else if(m + f >= 80){
                cout << "A" << endl;
            }else if(m + f >= 65){
                cout << "B" << endl;
            }else if(m + f >= 50){
                cout << "C" << endl;
            }else if(m + f >= 30){
                if(r >= 50){
                    cout << "C" << endl;
                }else{
                    cout << "D" << endl;
                }
            }else{
                cout << "F" << endl;
            }
        }
    }

return 0;}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
long long spf[10000002]; 
void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2;i<10000002; i++) 
    spf[i] = i; 
    for (int i=4; i<10000002; i+=2) 
    spf[i] = 2; 
  
    for (int i=3; i*i<10000002; i++) 
    { 
      if (spf[i] == i) 
        { 
            for (int j=i*i; j<10000002; j+=i) 
            if (spf[j]==j) 
            spf[j] = i; 
        } 
    } 
} 

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
     sieve(); 
    long long n,i,j,k,sum=0,count=0,ans=0,x=0,y=0,l,r;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(i<=2)
        ans+=i*i;
        else
        {
            k=i;
            map<long long ,long long>m1;
            while(k!=1)
            {
                m1[spf[k]]++;
                k=k/spf[k];
            }
            count=1;
            for(auto it=m1.begin(); it!=m1.end();it++)
            {
                count=count*(it->second+1);
            }
            ans+=i*(count);
        }
    }
    cout<<ans;
	return 0;
}

Measured memory_bytes: 81744
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[9]={-1,-1,-1,0,0,0,1,1,1},dy[9]={-1,0,1,-1,0,1,-1,0,1};
typedef pair<int,int> P;

string s[30][2],t[6][2];
int ans,h,n;

int calc(int z,int l) {
  int o,cnt=0;
  for(o=28;o>=-1;o--) {
    rep(i,2)rep(j,2)rep(k,2) {
      if(t[z*2+i][j][k]!='#') continue;
      int x=j+dx[l],y=k+dy[l];
      if(o+i<0||s[o+i][x][y]=='#') goto end;
    }
  }
 end:;
  o++;
  rep(i,2)rep(j,2)rep(k,2) {
    if(t[z*2+i][j][k]!='#') continue;
    int x=j+dx[l],y=k+dy[l];
    s[o+i][x][y]='#';
  }
  rep(i,30) {
    int c=0;
    rep(j,2)rep(k,2)if(s[i][j][k]=='#') c++;
    if(c!=4) continue;
    rep(j,2)rep(k,2)s[i][j][k]='.';
    REP(ii,i+1,30)rep(j,2)rep(k,2)swap(s[ii][j][k],s[ii-1][j][k]);
    i--;
    cnt++;
  }
  return cnt;
}

void dfs(int z,int cnt) {
  if(z==n) {
    ans=max(ans,cnt);
    return;
  }
  for(int l=0; l<9; l++) {
    string r[30][2];
    rep(i,30)rep(j,2)r[i][j]=s[i][j];
    bool f=1;
    rep(i,2)rep(j,2)rep(k,2) {
      if(t[z*2+i][j][k]=='#') {
        int x=j+dx[l],y=k+dy[l];
        if(!check(2,2,x,y)) f=0;
      }
    }
    if(!f) continue;
    int c=calc(z,l);
    dfs(z+1,cnt+c);
    rep(i,30)rep(j,2)s[i][j]=r[i][j];
  }
}
void Main() {
  while(cin >> h >> n && h) {
    rep(i,h)cin >> s[i][0] >> s[i][1];
    REP(i,h,30) s[i][0]=s[i][1]="..";
    rep(i,n)rep(j,2)rep(k,2) R t[i*2+j][k];
    ans=0;
    dfs(0,0);
    pr(ans);
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

int main() {
    string str;
    int n;
    cin>>n;
    cin>>str;
    int c=0;
    for(int i=2;i<n;i++){
        if(str[i]=='C' && str[i-1]=='B' && str[i-2]=='A')
            c++;
        
    }
    cout<<c<<endl;
    return 0;
}

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

typedef vector<vector<char> > vvchar;

inline vvchar init(int n){
	return vvchar(n, vector<char>(n));
}

void mul(vvchar &x, const vvchar &y){
	vvchar z = init(x.size());
	for(int i = 0; i < x.size(); ++i)
	for(int j = 0; j < x.size(); ++j)
	for(int k = 0; k < x.size(); ++k){
		if(x[i][k] && y[k][j]){
			z[i][j] = 1;
			break;
		}
	}
	x.swap(z);
}

void pow(vvchar &x, int k){
	vvchar z = init(x.size());
	for(int i = 0; i < x.size(); ++i){
		z[i][i] = 1;
	}
	while(k){
		if(k & 1){ mul(z, x); }
		mul(x, x);
		k >>= 1;
	}
	x.swap(z);
}

int main(){
	int n, m, z;
	while(scanf("%d%d%d", &n, &m, &z), n){
		vector<int> f(2 * m), t(2 * m);
		for(int i = 0; i < m; ++i){
			scanf("%d%d", &f[i], &t[i]);
			f[i + m] = t[i];
			t[i + m] = f[i];
		}
		
		vvchar x = init(2 * m);
		for(int i = 0; i < 2 * m; ++i)
		for(int j = 0; j < 2 * m; ++j){
			if(t[i] == f[j] && t[j] != f[i]){
				x[i][j] = 1;
			}
		}

		pow(x, z - 1);

		bool ok = false;
		for(int i = 0 ; i < 2 * m && !ok; ++i){
			if(f[i] == 1){
				for(int j = 0 ; j < 2 * m; ++j){
					if(t[j] == n && x[i][j]){
						ok = true;
						break;
					}
				}
			}
		}
		
		puts(ok ? "yes" : "no");
	}
}

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

int main() {
  
  int N;
  cin >> N;
  int p = 0;
  
  for (int i = 0;i < N;i++) {
    int l,r;
    cin >> l >> r;
    p = p + (r - l) + 1;
  }
  
  cout << p << endl;
  
  return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc150/tasks/abc150_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int c, int d) { return c / gcd(c, d) * d; }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    unordered_set<int> st;
    int ans = 1;
    REP(i, N) {
        uint64_t t;
        cin >> t;
        st.insert(__builtin_ctzll(t));
        if (st.size() >= 2) {
            cout << "0\n";
            return 0;
        }
        ans = lcm(ans, t / 2);
    }
    long long res = M / ans;
    cout << (res + 1) / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
import math
score = list(map(int,input().split()))
minut = score[2]*60 + score[3]
jisin = math.radians(minut/2)
hunsin = math.radians(score[3]*6)
jixy = [math.cos(jisin)*score[0] , math.sin(jisin)*score[0]]
huxy = [math.cos(hunsin)*score[1] , math.sin(hunsin)*score[1]]

delx = abs(jixy[0] - huxy[0])
dely = abs(jixy[1] - huxy[1])

answer = (delx**2 + dely**2)**0.5
print(answer)

Measured memory_bytes: 62640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int count=0;
    if(s[0]=='R' ||s[1]=='R' ||s[2]=='R') count++;
    if(s[1]=='R' && s[0]=='R') count++;
    if(s[2]=='R' && s[1]=='R') count++;
    cout<<count<<endl;
} 

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int m, d; cin >> m >> d;
  	int ans = 0;
  	for (int i=1;i<=m;i++) for (int j=1;j<=d;j++) {
      	if (j%10<2||j/10<2) continue;
    	if (j/10*(j%10)==i) ans++;
    }
  	cout << ans << endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint x;

llint check(llint n)
{
	llint ret = 0;
	while(n > 2){
		ret++;
		n--;
		n /= 2;
	}
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> x;
	
	llint ub = 1e18, lb = 2, mid;
	while(ub-lb>1){
		mid = (ub+lb)/2;
		if(check(mid) <= x) lb = mid;
		else ub = mid;
	}
	cout << lb << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef long long LL;

const int MAX = 1000;
int N;
int a[200];

int main()
{
    cin>>N;
    for(int i = 1;i<=N;i++)
        cin>>a[i];
    int sum = 1;
    for(int i = 1;i<=N;i++)
        sum *= 3;
    int sum1 = 1;
    for(int i =1;i<=N;i++){
        if(a[i]%2==0){
            sum1 *= 2;
        }
    }

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


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        System.out.println(c/a*b);
        
    }
    
}


Measured memory_bytes: 24148
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    string s ; cin >> s;
    int x = s.size();
    int res = 0;
    for (int i = 0; i < x-1 ; i+=2){
        if (s[i] == 'h' && s[i+1] == 'i'){
            res +=2;
        }
    }
    cout << (res == x ? "Yes" :"No") << endl;
}


Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> A(n);
    vector<int> B(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i] >> B[i];
    }

    if (A == B) {
        cout << 0 << '\n';
        return 0;
    }

    long long res = accumulate(A.begin(), A.end(), 0LL);
    int mn = 1 << 30;
    for (int i = 0; i < n; ++i) {
        if (A[i] > B[i]) {
            mn = min(mn, B[i]);
        }
    }
    res -= mn;

    cout << res << '\n';


    return 0;
}

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

int main() {
  string s;
  cin >> s;
  bool a = false;
  bool b = false;
  for(int i=0; i<s.size(); i++) {
    if(s[i] == 'A') a=true;
    if(s[i] == 'B') b=true;
  }
  if(a && b) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

#define F first
#define S second
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll gcd(ll x,ll y){
return y? gcd(y,x%y):x;
}

int main(){
  int k,sum;
  sum=0;
  cin>>k;
  For(a,1,k+1){
    For(b,1,k+1){
      For(c,1,k+1){
        if(a==b&&a==c)sum+=a;
        else if(a==b)sum+=gcd(a,c);
        else if(a==c)sum+=gcd(a,b);
        else if(b==c)sum+=gcd(a,b);
        else sum+=gcd(a,gcd(b,c));
      }
    }
  }
  cout<<sum<<endl;
return 0;
}


Measured memory_bytes: 3640
while True:
    c, k, s = map(int, input().split())
    if c+k+s > -3:
        if -1 in [c, k]:
            print('F')
        elif c+k >= 80:
            print('A')
        elif c+k >= 65:
            print('B')
        elif c+k >= 50:
            print('C')
        elif c+k >= 30:
            if s >= 50:
                print('C')
            else:
                print('D')
        else:
            print('F')
    else:
        break


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c;
  cin >>a>>b>>c;
  if(a == b){
    cout << c << endl;
    return 0;
  }
  if(b == c){
    cout << a << endl;
    return 0;
  }
    if(a == c){
    cout << b << endl;
    return 0;
  }
}

Measured memory_bytes: 764
n=int(input())
Wo=[list(map(int,input().split())) for i in range(n)]
Wo.sort(key=lambda x:x[1])

time=0
flag=True
for i in range(n):
  if Wo[i][0]+time<=Wo[i][1]:
    time+=Wo[i][0]
  else:
    flag=False
    break

if flag:
  print('Yes')
else:
  print('No')

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

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

  long long ans = 0, remedy = 0;
  for(int i = 0; i < N+1; i++){
    // cout << ans << " " << remedy << " " << B[i] << " " << A[i] << endl;
    if( A[i] >= B[i] + remedy ){ //
      ans += B[i] + remedy;
      remedy = 0;
    } else {
      if( remedy >= A[i] ) {
        ans += A[i];
        remedy = B[i];
      } else {
        // A[i] - remedy - B[i] < 0;
        ans += A[i];
        remedy = remedy + B[i] - A[i];
      }
    }
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;
long long n, k;
int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    long long mn = 1e18;
    for (int i = 0; i < (1 << n); i++) {
        long long cur = 1;
        for (int j = 0; j < n; j++)
            if ((i & (1 << j)) != 0) cur *= 2;
            else cur += k;
        mn = min(mn, cur);
    }
    cout << mn << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<double>pro;
int n;
double dp[3003][3003];
void ini(){
    for(int i=0;i<3002;i++){
        for(int j=0;j<3002;j++){
            dp[i][j]=-1;
        }
    }
}
double f(int x,int t){
    if(x==n and t>n/2)return 1;
    else if(x>n-1)return 0;
    if(dp[x][t]!=-1)return dp[x][t];
    return dp[x][t]=f(x+1,t+1)*pro[x]+f(x+1,t)*(1-pro[x]);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    pro.resize(n);
    ini();
    for(int i=0;i<n;i++)
       cin>>pro[i];
    cout<<setprecision(10)<<f(0,0);
}


Measured memory_bytes: 70912
#include<stdio.h>
#include<stdlib.h>

int main()
{
        int N;
        int A[1000000];
        int arraycount=1;
        int prev=0;
        int i;

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


Measured memory_bytes: 2432
s = input()
a = [c for c in s]

n = len(a)
r_a = a[::-1]
#print(a,r_a)
f = a[0:int((n-1)/2)]
r_f =f[::-1]
#print(f,r_f)
l = a[int((n+1)/2):]
r_l =l[::-1]
#print(l,r_l)
if (a==r_a)and(f==r_f)and(l==r_l):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
string a;
int main()
{
    cin>>a;
    for(int i=0;i<a.size()-1;i++)if(a[i]=='A'&&a[i+1]=='C')
    {
        cout<<"Yes";return 0;
    }
    cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1e9+7;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> cnt(n+1);
    for(int i = 0; i <= n; i++) cnt[i] = 0;
    cnt[0] = 3;
    ll ans = 1;
    for(int i = 0; i < n; i++)
    {
        int cand = a[i];
        ans = ans * cnt[cand] % MOD;
        cnt[cand+1]++;
        cnt[cand]--;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<cassert>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<limits>
#include<ctime>
#include<stack>

using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int m = 0, ans = 0;
    for(int i=0;i<n;i++){
        m += a[i];
    }
    if((m*10 / n) % 10 >= 5)m = m / n + 1;
    else m = m / n;
    for(int i=0;i<n;i++){
        ans += pow(a[i] - m, 2);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3592
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        x: i64,
    };
    println!(
        "{}",
        match x {
            x if x >= 1800 => 1,
            x if x >= 1600 => 2,
            x if x >= 1400 => 3,
            x if x >= 1200 => 4,
            x if x >= 1000 => 5,
            x if x >= 800 => 6,
            x if x >= 600 => 7,
            x if x >= 400 => 8,
            _ => panic!("not defined"),
        }
    );
}


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

int main(){
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  std::vector<bool> ch(n,false);
  rep(i,n){
    int temp;
    std::cin >> temp;temp--;
    v[i]=temp;
  }

  int ans=0;
  int now=0;
  while (now!=1){
    if(ch[now]==true){
      std::cout << "-1" << '\n';
      return 0;
    }
    ch[now]=true;
    now=v[now];
    ans++;
  }
  std::cout << ans << '\n';


return 0;
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import bisect
    
    N=I()
    A=LI()
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        u,v=MI()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)
        
    #DFSで見ていく．オイラーツアーを作っておく．更新情報をstackに積んでおき，巻き戻る時にpopしていく
    
    #非再帰オイラーツアー
    #ETにオイラーツアー を，ET1,ET2はそれぞれ開始番号と終了番号．
    #stackで管理，行きがけと帰りがけをそれぞれi,~iで表現
    
    st_ch=[]
    #(どの場所を更新したか，元々の値は何か)を持っておく
    
    
    inf=10**10
    dp=[inf]*(N+1)
    #dp[i]は長さiを取れるときの最小末尾（普通のLISと同じ持ち方）
    dp[0]=0
    
    ans=[0]*N#答えを入れとく


    def EulerTour(n, X, i0=0):
        # 隣接グラフXを消費しながら，親リストPを作りながら進む．
        #i0が根
        P = [-1] * n
        st = [~i0, i0]
        ct = -1
        ET = []
        ET1 = [0] * n
        ET2 = [0] * n
        DE = [0] * n
        de = -1
        while st:
            #頂点 i を見る
            i = st.pop()
            
            #帰り際の処理，ここを入れる場合，オイラーツアーの最後に「-1」がつくので注意
            if i < 0:
                ct += 1
                # ↓ 戻りもETに入れる場合はこれを使う
                ET.append(P[~i])#notのnot
                ET2[~i] = ct
                de -= 1
                
                #dp-rollback
                num,val=st_ch.pop()
                dp[num]=val
                
                continue
            
            #行きがけの処理
            if i >= 0:
                ET.append(i)
                ct += 1
                if ET1[i] == 0: ET1[i] = ct
                de += 1
                DE[i] = de
                
                #dp-update
                num=bisect.bisect_left(dp,A[i])
                st_ch.append((num,dp[num]))#更新情報を入れておく
                dp[num]=A[i]#更新
                
                ans_num=bisect.bisect_left(dp,inf)
                ans[i]=ans_num-1
                
                #
                
                
            for a in X[i][::-1]:
                if a != P[i]:
                    P[a] = i
                    for k in range(len(X[a])):
                        if X[a][k] == i:
                            del X[a][k]
                            break
                    st.append(~a)
                    st.append(a)
        return (ET, ET1, ET2)
    
    EulerTour(N,adj)
    for i in range(N):
        print(ans[i])
    


                    
                
        
    

main()


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

int main() {
  int N;
  cin>>N;
  std::vector<int> q(12);
  q[11]=1;
  q[0]=9;
  q[5]=6;
  for(int i=1;i<5;i++)q[i]=q[i-1]*9;
  for(int i=6;i<11;i++)q[i]=q[i-1]*6;
  sort(q.begin(),q.end());
  std::vector<int> v(N+1,1000000);
  v[0]=0;
  for(int i=1;i<N+1;i++){
    for(int j=0;j<12;j++){
      if(i-q[j]>=0)v[i]=min(v[i],v[i-q[j]]+1);
    }
  }
  cout<<v[N]<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[N], a[N];
int main() {
	int n, c, k;
	scanf("%d%d%d", &n, &c, &k);
	for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	int j = 0;
	for (int i = 1; i <= n; ++ i) {
		while (j + 1 < i && (a[i] - a[j + 1] > k || i - j > c)) ++ j;
		f[i] = f[j] + 1;
	}
	cout << f[n] << endl;
}



Measured memory_bytes: 1024
use std::str::FromStr;
use std::io::*;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = AtRead::from(i);
    let s = i.read_line();
    let r = match solve(s) {
        Some(r) => (1 + r.0 as isize, 1 + r.1 as isize),
        None => (-1, -1),
    };
    writeln!(o, "{} {}", r.0, r.1).unwrap();
}
fn solve(s: &str) -> Option<(usize, usize)> {
    let s = s.as_bytes();
    for i in 1..s.len() {
        if s[i - 1] == s[i] {
            return Some((i - 1, i));
        }
    }
    for i in 2..s.len() {
        if s[i - 2] == s[i] {
            return Some((i - 2, i));
        }
    }
    None
}

mod utils {
    use super::*;
    use std::ops::*;

    pub struct AtRead<R: BufRead> {
        r: R,
        s: String,
    }
    impl<R: BufRead> AtRead<R> {
        pub fn from(r: R) -> Self {
            AtRead {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }
    }
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <cinttypes>
#include <string.h>
#include <bits/stdc++.h>

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define pi pair<int,int>
#define fi first
#define se second

#define FOR(var, to)          for (register s64 var = 0; var < (s64)to; var++)
#define FROMTO(var, from, to) for (register s64 var = from; var <= (s64)to; var++)

#define INIT(var) FOR(i,countof(var)) var[i] = 0
#define INPUT(var) FOR(i,countof(var)) var[i] = ri()

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)

#define MOD 1000000007
#define INF (1 << 30)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

using namespace std;

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

static inline s64 rs64() {
  s64 a;
  scanf("%" SCNd64, &a);
  return a;
}

static inline void wi(int a) {
  printf("%d", a);
}

static inline void wu64(u64 a) {
  printf("%" PRIu64, a);
}

static inline void ws64(s64 a) {
  printf("%" PRId64, a);
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
  int n = ri();
  int k = ri();
  int res = (n%k)?1:0;
  wi(res);
  
  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <math.h> 
#include <algorithm>
using namespace std;

int main(){
    long long n, ans = 10000000000000;
    cin >> n;
    long long a = sqrt(n);
    for(int i = a; i > 0; i--){
        if(!(n%i)) ans = min(ans, i+(n/i) - 2);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, *p = map(int, open(0).read().split())

ans = 0
for i in range(n-1):
        if p[i]==i+1:
                p[i], p[i+1] = p[i+1], p[i]
                ans += 1
if p[n-1]==n: ans += 1
print(ans)

Measured memory_bytes: 14068
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

// reference: http://ir5.hatenablog.com/entry/20171209/1512821837

struct Scanner<'a> {
    cin: StdinLock<'a>,
}
 
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }
 
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }
 
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

use std::mem;

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let h: u32 = sc.read();
    let n: u32 = sc.read();
    if h < n {
        println!("{}", h.to_string().repeat(n as usize));
    } else {
        println!("{}", n.to_string().repeat(h as usize));
    }
}

Measured memory_bytes: 2012
a,b,c,d=map(int,input().split())
e=a//d
f=c//b
x=a-e*d
y=c-f*b
if x==y==0:
  if f<=e:
    print('Yes')
  else:
    print('N0')
elif x==0 and y!=0:
  if f+1<=e:
    print('Yes')
  else:
    print('No')
elif y==0 and x!=0:
  if f<=e+1:
    print('Yes')
  else:
    print('NO')
else:
  if f<=e:
    print('Yes')
  else:
    print('No')
  

Measured memory_bytes: 8912
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

int gcd(int a, int b){
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

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

void solve(){
    int N;
    cin >> N;

    vector<ll> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }

    ll ans = 0, k;
    for (int i = N-1; i >= 0; i--) {
        k = (A[i] + ans) / B[i] + ( (A[i] + ans) % B[i]  > 0 );
        ans += B[i] * k - (A[i] + ans);
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			string s;
			cin>>s;
			if(s=="snuke")
			{
				cout<<char(j-1+'A')<<i<<endl;
				return 0;
			}
		}
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  string s;
  cin >> s;
  int cnt;
  for (int i  = s.size() - 2; i >= 0; i--) {
    if (i % 2 == 0) continue;
    cnt = 0;
    int m = (i - 1) / 2;
    int tmp = i;
    for (int j = m; j >= 0; j--) {
      if (s[j] == s[tmp]) cnt++;
      else break;
      if (cnt == m + 1) break;
      tmp--;
    }
    if (cnt == m + 1) break;
  }
  cout << cnt * 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    string N;
    cin >> N;
    bool c = (N[0] == '9' || N[1] == '9');
    puts(c?"Yes":"No");
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<set>
#define rep(i,n) for(ll i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,ll>P;

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
    string s;
    int ans=INF;
    cin>>s;
    int l=s.length();
    rep(i,l-2)
    {
        string temp=s.substr(i,3);
        int val=atoi(temp.c_str());
        if(ans>abs(val-753))
        {
            ans=abs(val-753);
        }
    }

    cout<<ans<<endl;

    

}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void insertionSort(int* a,int N){
	int v;
	int j;
	for(int i=0;i<=N-1;i++){
		v=a[i];
		j=i-1;
		while(j>=0&&a[j]>v){
			a[j+1] = a[j];
			j--;
		}
		a[j+1]=v;
		
		for(int k=0;k<N;k++){
			printf("%d",a[k]);
			if(k!=N-1)printf(" ");
		}
		printf("\n");
	}
}

int main(void){
	
	int n;
	scanf("%d",&n);
	int* a=(int*)malloc(sizeof(int)*n);
	
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	
	insertionSort(a,n);
	
	return 0;
	
}


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

typedef long long           ll;
typedef unsigned long long  ull;

#define srev                reverse(s.begin(),s.end())
#define sortstr             sort(s.begin(), s.end());
#define gtl(x)              getline(cin, (x))
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define PI                  acos(-1)
#define Precision(a) 		cout << fixed << setprecision(a)
#define FasterIO()     		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);}
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
//scanf("%[^\n]%*c", str);
//sort(s,s+n,greater<int>());

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a-b+1 << endl;
    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s,t;
bool fl;
struct edge{int to,cost;};
map<char,ll> mp;

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>s>>t;
    ll nex=1;
    rep(i,n-1){
        (mp[s[i]]+=nex)%=MOD;
        (nex=mp[t[i+1]])%=MOD;
    }
    Cout(mp[t[n-1]]);
    return 0;
}



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

int main(){
    priority_queue<int> q;

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

    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        q.push(a);
    }

    while(m--){
        int v = q.top();
        q.pop();
        v /= 2;
        q.push(v);
    }

    LL ans = 0;

    while(!q.empty()){
        ans += q.top();
        q.pop();
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main()
{
	vector<int> a(4), b(4);

	while (cin >> a[0] >> a[1] >> a[2] >> a[3],
		cin >> b[0] >> b[1] >> b[2] >> b[3])
	{
		int hit = 0, blow = 0;

		for (int i = 0; i < a.size(); ++i)
			if (a[i] == b[i]) hit++;

		for (int i = 0; i < a.size(); ++i)
			for (int j = 0; j < b.size(); ++j)
				if (a[i] == b[j]) blow++;

		cout << hit << " " << blow - hit << endl;
	}

	return 0;
}

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

int main() {
    string ans = "Yes";
    int N;
    cin >> N;
    vector<ll> H(N);
    rep(i, N) cin >> H[i];
    rep(i, N - 1) {
        if(H[N - 2 - i] - 1 > H[N - 1 - i]) {
            ans = "No";
            break;

        } else if(H[N - 2 - i] - 1 == H[N - 1 - i])
            H[N - 2 - i]--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 4028
import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+(1<<i),x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

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

string s;

int main() {
    cin >> s;
    char prev = '@';
    bool isgood = true;
    for(auto x : s) {
        if(prev == x)
            isgood = false;
        prev = x;
    }

    if(isgood)
        cout << "Good" << endl;
    else
        cout << "Bad" << endl;
}

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

int main(){
    int a,b; cin >> a >> b;
    if(a!=b) cout << max(a,b)*2-1 << endl;
    else cout << a+a << endl;
return 0;
}

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

#define __INIT_CC__ ios::sync_with_stdio(false); \
	cin.tie(0);

#ifdef __WIN32__
	char getchar_unlocked() {return getchar();}
#endif

#define FOR(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<(_t);++(_i))
#define FORN(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<=(_t);++(_i))
#define FORD(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i>=(_t);--(_i))
#define RESET(_a,_value) memset(_a,_value,sizeof(_a))
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define mp make_pair
#define SIZE(_a) (int)_a.size()
#define VSORT(_a) sort(_a.begin(),_a.end())
#define SSORT(_a,_val) sort(_a,_a+(_val))
#define ALL(_a) _a.begin(),_a.end()
#define mt make_tuple
#define _get(_tuple,_i) get<_i>(_tuple)
#define eb emplace_back
 
using namespace std;

using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<ii>;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using pdd = pair<double,double>;
using vpdd = vector<pdd>;
template <typename T> using uset = unordered_set<T>;
template <typename T> using umultiset = unordered_multiset<T>;
template <typename K, typename V> using umap = unordered_map<K, V>;
template <typename K, typename V> using umultimap = unordered_multimap<K, V>;

const int dr[] = { 1, 0,-1, 0, 1, 1,-1,-1};
const int dc[] = { 0, 1, 0,-1, 1,-1,-1, 1};
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const ll INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);

template <typename T> T take(queue<T> &O) {T tmp=O.front();O.pop();return tmp;}
template <typename T> T take(stack<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T> T take(priority_queue<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T>
inline bool inRange(const T& z, const T& a, const T& b){return a <= z && z <= b;}

void OPEN(const string& in = "input.txt", const string& out = "output.txt")
{
	freopen(in.c_str(), "r", stdin);
	freopen(out.c_str(), "w", stdout);
	return ;
}

//using sokokaleb's template v4.0

ll n, a, b;

int main(int argc, char** argv) {
	__INIT_CC__
	cin >> n >> a >> b;
	if (a > b) cout << 0 << "\n";
	else if (a == b) cout << 1 << "\n";
	else if (n == 1) {
		if (a == b) cout << 1 << "\n";
		else cout << 0 << "\n";
	} else if (n == 2) cout << 1 << "\n";
	else {
		n -= 2;
		b -= a;
		a -= a;
		b *= n;
		cout << b + 1 << "\n";
	}
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		Scanner scan = null;
		try{
			int num;
			int[] prime = new int[10000];
			prime[0] = 2;
			for(int i = 3 ,j = 1;j <prime.length;i += 2){
				boolean check = false;
				for(int k = 3; k < i /2; k += 2){
					if(i % k ==0){
						check = true;
						break;
					}
				}
				if(!check){
					prime[j] = i;
					j++;
				}
			}
			for(scan = new Scanner(System.in);(num = scan.nextInt()) !=0;){
				int sum = 0;
				for(int i = 0; i < num;i++){
					sum += prime[i];
				}
				System.out.println(sum);
			}
		}finally{
			if(scan !=null)scan.close();
		}
	}
}

Measured memory_bytes: 19920
#[allow(unused_imports)]
use std::cmp::{min,max};
use std::collections::BinaryHeap;

fn main() {
    let xs = read_vec_i64();
    let (v,e,r) = (xs[0] as usize, xs[1] as usize, xs[2] as usize);
    let mut adj = vec![];
    adj.resize(v,vec![]);
    for _ in 0..e {
        let ys = read_vec_i64();
        let (s,t,d) = (ys[0] as usize, ys[1] as usize, ys[2]);
        adj[s].push((t,d));
    }
    let inf = 1 << 60;
    let mut dists = vec![];
    dists.resize(v, inf);
    dists[r] = 0;
    let mut heap = BinaryHeap::new();
    heap.push((0,r));
    while let Some((md,s)) = heap.pop() {
        let d = -md;
        for t_dd in adj[s].iter() {
            let (t,dd) = *t_dd;
            let nd = d + dd;
            if nd < dists[t] {
                dists[t] = nd;
                heap.push((-nd,t));
            }
        }
    }
    for d in dists {
        if d != inf {
            println!("{}", d);
        }
        else {
            println!("INF");
        }
    }
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    let mut ret :i64 = 0;
    for c in ss.chars() {
        if ! ('0' <= c && c <= '9') { break; }
        let t = c.to_digit(10).unwrap() as i64;
        ret = ret * 10 + t;
    }
    return ret;
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let ss = read_line();
    let mut res = Vec::new();
    let mut edited = false;
    let mut x:i64 = 0;
    for c in ss.chars() {
        if !('0' <= c && c <= '9') {
            if edited {
                edited = false;
                res.push(x);
                x = 0;
            }
        }
        else {
            let t = c.to_digit(10).unwrap() as i64;
            x = x * 10 + t;
            edited = true;
        }
    }
    if edited {
        res.push(x);
    }
    return res;
}



Measured memory_bytes: 23348
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg)/360)*2*M_PI)
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;
const ll MAX = 1e5 + 10;


int main() {
	ll i, j, k;
	ll N, K, R, S, P;
	cin >> N >> K >> R >> S >> P;
	string T;
	cin >> T;

	ll ans = 0;

	for (k = 0; k < K; k++) {
		ll pr = 0;
		ll ps = 0;
		ll pp = 0;
		ll nr = 0;
		ll ns = 0;
		ll np = 0;
		for (i = k; i < N; i += K) {
			if (T[i] == 'r') {
				nr = max(ps, pp);
				ns = max(pr, pp);
				np = max(pr, ps) + P;
			}
			if (T[i] == 's') {
				nr = max(ps, pp) + R;
				ns = max(pr, pp);
				np = max(pr, ps);
			}
			if (T[i] == 'p') {
				nr = max(ps, pp);
				ns = max(pr, pp) + S;
				np = max(pr, ps);
			}
			pr = nr;
			ps = ns;
			pp = np;
		}
		ans += max(nr, max(ns, np));
	}
	cout << ans << endl;

}


Measured memory_bytes: 512
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    d = defaultdict(int)

    for x in range(1, int(math.sqrt(N)) + 1):
        for y in range(1, int(math.sqrt(N)) + 1):
            for z in range(1, int(math.sqrt(N)) + 1):
                tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                d[tmp] += 1
    for i in range(1, N+1):
        print(d[i])


if __name__ == '__main__':
    main()

Measured memory_bytes: 77252
#include<iostream>
using namespace std;
int main(){
  int n,ans,o,d,k;
  cin >> o;
  for(int i=1;i<=o;i++){
    cin >> n;
    cout << "Case " << i << ":" << endl;
    for(int i=0;i<10;i++){
      ans = 0;
      d = 100000;
      k = 1000;
      n *= n;
      for(int j=0;j<4;j++){
	ans += n/d%10*k;
	d /=10;
	k /= 10;
      }
      n = ans;
      cout << ans << endl;
    }
  }
    return 0;
}

Measured memory_bytes: 1160