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

int checkprime(long a, long b)
{
    bool isPrime = true;
    long i, j;
    for (i = a; i <= b; ++i)
    {
        for (j = 2; j < i; ++j)
        {
            if (i % j == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime && i >= a)
            return i;
        isPrime = true;
    }
    return 0;
}

int main()
{
    long N;
    cin >> N;
    cout << checkprime(N, 2 * N) << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 600000000 //2000000000
#define LINF 1000000000000000000 //9000000000000000000 大きいとワ―シャルフロイドでオーバーフローを起こす
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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

long long int gcd(long long int a, long long int b) { //最大公約数
	if (b == 0) {
		return a;
	}
	return gcd(b, a%b);
}

long long int lcm(long long int a, long long int b) { //最小公倍数
	long long int g = gcd(a, b);
	return a / g * b;
}


int main(void) {
	
	long long int a, b, c, d;
	long long int count = 0;
	long long int cf, ce, df, de;
	long long int zf, ze;
	long long int te = 1;
	long long int p, q, r;
	long long int re = 0;

	cin >> a >> b >> c >> d;

	if (a%c == 0) {
		cf = a / c;
	}
	else {
		cf = a / c+ 1;
	}
	if(a%d==0){
		df = a / d;
	}
	else {
		df = a / d+ 1;
	}

	if (a%lcm(c, d) == 0) {
		zf =a / lcm(c, d);
	}
	else {
		zf =  a / lcm(c, d)+ 1;
	}


	
	ce = b / c;
	de = b / d;
	ze = b/lcm(c, d);

	p = ce - cf + 1;
	q = de - df + 1;
	r = ze - zf + 1;

	p = max(re, p);
	q = max(re, q);
	r = max(re, r);


	//cout << cf << " " << ce << " " << df << " " << de << " " << zf << " " << ze << endl;
	
	cout << (b - a + 1) - p-q+r << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
#define ll long long
#define fast_io cin.tie(0);cout.tie(0);ios::sync_with_stdio(0)
using namespace std;

int main(){
	fast_io;
	ll n,m;
	cin>>n>>m;
	ll l[m+1],r[m+1],cnt=0,ans=0,i,j,minA=INT_MIN,minB=INT_MAX;
	for(i=1;i<=m;i++){
		cin>>l[i]>>r[i];
		minA = max(minA,l[i]);
		minB = min(minB,r[i]);
	}
	if(minA>minB) cout<<"0";
	else{
		ans = minB-minA+1;
		cout<<ans;
	}
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int r = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();
        
        long ans = x;
        for (int i = 0; i < 10; i++) {
            ans = r * ans - d;
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<iomanip>
#define MAX_N 3000

using namespace std;

int N;
double p[MAX_N];
double dp[MAX_N][MAX_N];

int main(){
    cin >> N;
    for(int i=0;i < N;i++){
        cin >> p[i];
    }
    dp[0][0] = 1;

    for(int i=0;i < N;i++){
        for(int j=0;j <= i;j++){
            dp[i+1][j] += (1-p[i])*dp[i][j];
            dp[i+1][j+1] += p[i]*dp[i][j];
        }
    }
    double ans = 0.0;
    for(int i=N/2+1;i <= N;i++) ans += dp[N][i];
    cout << fixed << setprecision(10) <<  ans << endl;
    return 0;
}

Measured memory_bytes: 49904
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

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

    vector<vector<int64_t>> costs(n, vector<int64_t>(n, numeric_limits<int64_t>::max() / 4));
    int64_t total = 0;
    for (auto i : irange(0, n)) {
        for (auto j : irange(0, n)) {
            cin >> costs[i][j];
            if (i > j) {
                total += costs[i][j];
            }
        }
    }

    for (auto i : irange(0, n)) {
        for (auto j : irange(0, n)) {
            bool required = true;
            for (auto k : irange(0, n)) {
                if (k == i || k == j) {
                    continue;
                }

                // check triangle relation
                if (costs[i][k] + costs[k][j] < costs[i][j]) {
                    cout << -1 << endl;
                    return 0;
                }

                if (costs[i][k] + costs[k][j] == costs[i][j]) {
                    required = false;
                }
            }

            if (!required && i > j) {
                total -= costs[i][j];
            }
        }
    }

    cout << total << endl;
}


Measured memory_bytes: 1024
using System;

namespace MSTrust2019A
{
    class Program
    {
        static void Main(string[] args)
        {
            var line1 = Console.ReadLine().Split(' ');
            var m1 = Convert.ToInt32(line1[0]);
            var line2 = Console.ReadLine().Split(' ');
            var m2 = Convert.ToInt32(line2[0]);
            Console.WriteLine(m1 == m2 ? 0 : 1);
        }
    }
}


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

template<class T> inline bool chmin(T& a,T b){
    if (a > b) {
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a,T b){
    if(a < b) {
        a=b;
        return true;
    }
    return false;
}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define INF 999999999

    /*Solve*/

int main(){
    ll n;
    cin >> n;
    ll h[n];
    rep(i,n){
        cin >> h[i];
    }
    ll tmp=0;
    rep(i,n){
        if(i>0 && h[i-1]<=h[i]){
            tmp+=h[i]-h[i-1];
        }
    }
    tmp+=h[0];
    cout << tmp << endl;
}

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





int main() {
	
	string S="NO";
	ll N;
	cin >> N;
	
	set<ll> ve;

	rep(i, N) {
		ll a;
		cin >> a;
		ve.insert(a);
	}
	if (ve.size() == N) {
		S = "YES";
	}
	cout << S << endl;


}


Measured memory_bytes: 9600
s[61][61],q[400];
main(x,y,i,j,f,g,_x,_y){
	for(;scanf("%d%d",&x,&y),x;){
		memset(s,0xff,sizeof(s));
		for(j=1;j<2*y;j++)
			for(i=1;i<2*x;i++)
				s[i][j]=0;
		for(j=1;j<2*y;j++)
			for(i=(j&1)?2:1;i<2*x;i+=2)scanf("%d",s[i]+j);
		q[0]=0x10001;s[1][1]=1;f=0;g=1;
		for(;f!=g;){
			_x=q[f]>>16,_y=q[f]&0xffff;f=(f+1)%400;
			if(s[_x][_y-1]==0&&s[_x][_y-2]==0)q[g]=((_x)<<16)|(_y-2),g=(g+1)%400,s[_x][_y-2]=s[_x][_y]+1;
			if(s[_x][_y+1]==0&&s[_x][_y+2]==0)q[g]=((_x)<<16)|(_y+2),g=(g+1)%400,s[_x][_y+2]=s[_x][_y]+1;
			if(s[_x-1][_y]==0&&s[_x-2][_y]==0)q[g]=((_x-2)<<16)|(_y),g=(g+1)%400,s[_x-2][_y]=s[_x][_y]+1;
			if(s[_x+1][_y]==0&&s[_x+2][_y]==0)q[g]=((_x+2)<<16)|(_y),g=(g+1)%400,s[_x+2][_y]=s[_x][_y]+1;
			if(s[2*x-1][2*y-1])break;
		}
		printf("%d\n",s[2*x-1][2*y-1]);
	}
	exit(0);
}

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

struct pati {int x,y,d;};

pati p[5][1000];

int len(int x1,int y1,int x2,int y2) {
	int x,y;
	x=x1-x2; y=y1-y2;
	if (x<0) x=-x;
	if (y<0) y=-y;
	return x+y;
}
int main () {
	int sx,sy,gx,gy,i,j,k,h,p1,p2,f,x,y,d,m,a1,a2,pn[5];
	char c[1000];
	while(cin >> x >> y && x>0) {
		for (i=0;i<5;i++) pn[i]=0; a2=999999999;
		for (i=0;i<y;i++) {
			cin >> c; 
		    for(j=0;j<x;j++) {
				if (c[j]=='S') { sx=j; sy=i; continue;}
				if (c[j]=='G') { gx=j; gy=i; continue;}
				if (c[j]!='.') { k=c[j]-'1'; p[k][pn[k]].x=j; p[k][pn[k]].y=i; pn[k]++;}   
	          }
		  } 
		f=0;
		for (i=0;i<5;i++) if (pn[i]>0) f++;
		if (f<4) { cout << "NA" << endl; continue;}
		for (i=0;i<5;i++) {
			m=(i+1) % 5;
			for (j=0;j<5;j++) for (k=0;k<pn[j];k++) p[j][k].d=99999999;
			if (pn[m]==0) continue;
			for (j=0;j<pn[m];j++) p[m][j].d=len(sx,sy,p[m][j].x,p[m][j].y);			
		    for (j=0;j<3;j++) {
				h=(m+j) % 5; k=(m+j+1) % 5;
				if (pn[k]==0) break;
				for (p1=0;p1<pn[h];p1++) for (p2=0;p2<pn[k];p2++) {
					d=len(p[h][p1].x,p[h][p1].y,p[k][p2].x,p[k][p2].y);
					if (d+p[h][p1].d<p[k][p2].d) p[k][p2].d=d+p[h][p1].d;
				}
			}
			h=(m+3) % 5;
			for (p2=0;p2<pn[h];p2++) {
				k=len(gx,gy,p[h][p2].x,p[h][p2].y);
				if (a2>p[h][p2].d+k) { a1=i+1; a2=p[h][p2].d+k;}
			}
		}
		cout << a1 << ' ' << a2 << endl;
	}   
	return 0;
}

Measured memory_bytes: 1220
n, a, b = map(int, input().split())
ans = 0
for x in range(n + 1):
    sum = 0
    temp = x
    for id in range(5):
        sum += temp % 10
        if temp < 10: break
        else: temp //= 10
    if a <= sum <= b: ans += x
print(ans)

Measured memory_bytes: 3060
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())

sys.setrecursionlimit(10 ** 9)


def main():
    S = INT()
    K = INT()

    for i, s in enumerate(str(S)):
        if int(s) != 1:
            if i >= K: print(1)
            else: print(s)
            break
    else:
        print(1)


if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include <stdio.h>
int main(){
	int a,b,c,d,e,f,T;
	while(~scanf("%d %d %d %d %d %d\n",&a,&b,&c,&d,&e,&f)){
		T=(d*3600+e*60+f)-(a*3600+b*60+c);
		printf("%d %d %d\n",T/3600,T%3600/60,T%60);
	}


	return 0;
}

Measured memory_bytes: 604
#pragma GCC optimize("Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int mod=1e9+7,N=1<<18;
int sum[N],ans,h,n,p[N];
vector<int> clear;

void dfs2(int x,int mul,bool islc){
	if(x==1) return ;
	mul=1ll*mul*x%mod;
	if(islc) sum[x]=(sum[x]+mul)%mod;
	else ans=(ans+1ll*(x>>1)*sum[x^1]%mod*mul%mod)%mod;
	dfs2(x>>1,mul,islc);
}

void dfs1(int x,int mul,bool islc){
	mul=1ll*mul*x%mod;
	if(x>=n){
		int y=n+p[x-n+1]-1;
		dfs2(y,mul,islc);
		if(islc) clear.push_back(y);
		return ;
	}
	dfs1(x<<1,mul,islc);
	dfs1(x<<1|1,mul,islc);
}

signed main(){
	read(h);
	n=1<<h-1;
	for(int i=1;i<=n;i++) read(p[i]);
	for(int lca1=1;lca1<n;lca1++){
		dfs1(lca1<<1,lca1,1);
		dfs1(lca1<<1|1,1,0);
		for(int leaf:clear) for(int x=leaf;x;x>>=1) sum[x]=0;
		clear.clear();
	}
	write(ans);
}

Measured memory_bytes: 5200
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){

    int N,x;
    cin >> N >> x;
    int a[N];
    REP(i,N) cin >> a[i];

    ll ans = 0;
    FOR(i,1,N){
        if(a[i]>0 && a[i]+a[i-1]>x){
            ans += a[i]+a[i-1]-x;
            a[i] = max(x-a[i-1], 0);
        }
        if(a[i-1]>0 && a[i]+a[i-1]>x){
            a[i-1] = x;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
    int R,G,B,N;
    cin>>R>>G>>B>>N;

    int cnt=0;
    for (int i = 0; i <= N/R; i++){
        for (int j = 0; j <= N/G; j++){
            if((N - R*i-G*j )%B==0 && (N - R*i-G*j>=B || N - R*i-G*j==0)){
                cnt++;
            }
        }
    }

    cout << cnt << endl;


}

Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<vector>//s1.erase(n)=文字列s1の、n文字目以降削除
#include<algorithm>//辞書順=next_permutation
#include<set>
#include<string>//char=小文字のほうが32大きい
#include<sstream>
#include<string.h>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap=数値交換
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(s,n) rep(i,n)cin>>s[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//標準=昇順
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define str string
#define please return
#define AC 0
#define Rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define Pi 3.1415926535897932384626
#define nine 1000000000

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int keta(int n) {
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */


int main(void) {

	int n;
	cin >> n;
	vint l(n);
	vcin(l, n);

	int x = l[0];
	int y = 0;

	rop(i, n-1) {
		x = max(l[i], x);
	}

	int a = 0;

	rep(i, n) {
		if (l[i] == x) {
			a = i;
			break;
		}
	}

	int sum = 0;

	rep(i, n) {
		if (i == a)continue;
		sum += l[i];
	}

	Yes(x < sum);

	please AC;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 100005
#define NIL -1
using namespace std;

typedef struct Node { int parent, left, right; } Node;

Node T[MAX];
int n, D[MAX];

void print(int u)
{
    int i, c;
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].parent << ", ";
    cout << "depth = " << D[u] << ", ";

    if (T[u].parent == NIL) cout << "root, ";
    else if (T[u].left == NIL) cout << "leaf, ";
    else cout << "internal node, ";

    cout << "[";

    for (i = 0, c = T[u].left; c != NIL; i++, c = T[c].right) {
        if (i) cout << ", ";
        cout << c;
    }
    cout << "]" << endl;
}

int getDepth(int u, int p)
{
    D[u] = p;
    if (T[u].right != NIL) getDepth(T[u].right, p);
    if (T[u].left != NIL) getDepth(T[u].left, p + 1);
}

int main(void)
{
    int i, j, id, degree, child, node, root;
    cin >> n;

    for (i = 0; i < n; ++i) T[i].parent = T[i].left = T[i].right = NIL;

    for (i = 0; i < n; ++i) {
        cin >> id >> degree;
        for (j = 0; j < degree; ++j) {
            cin >> child;
            if (j == 0) T[id].left = child;
            else T[node].right = child;
            node = child;
            T[child].parent = id;
        }
    }

    for (i = 0; i < n; ++i) {
        if (T[i].parent == NIL) root = i;
    }
    getDepth(root, 0);

    for (i = 0; i < n; ++i) print(i);
    return 0;
}



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

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int t[5000][5];

void disp(void){
	for(int i=0;i<10;i++){
		for(int j=0;j<5;j++){
			cout<<(int)t[5000-10+i][j];
		}
		cout<<endl;
	}
	cout<<"---------------------\n";
}

bool stop(int ti,int tj,int d,int p){
	if(ti == 4999) return true;

	if(d == 1) REP(j,tj,tj+p){if(t[ti+1][j] == 1) return true;}
	else if(t[ti+1][tj]==1) return true;

	return false;
}

void putBlock(int ti,int tj,int d,int p){
	if(d == 1) REP(j,tj,tj+p) t[ti][j] = 1;
	else for(int i=ti;i>ti-p;i--) t[i][tj] = 1;
}

void dropBlock(int ti){
	for(int i=ti;i>0;i--){
		int sum = 0;
		rep(j,5){
			if(t[i-1][j] == 1) sum++;
			t[i][j] = t[i-1][j];
		}
		if(sum == 0) return;
	}
}

void deleteLine(int from,int to){
	int repeat = from - to;
	int i = from;
	rep(time,repeat){
		int sum = 0;
		rep(j,5) if(t[i][j] == 1) sum++;
		if(sum == 5){
			rep(j,5) t[i][j] = 0;
			dropBlock(i);
		}
		else{
			i--;
		}
	}
}

int main(void){
	int n;
	while(cin>>n,n){
		memset(t,0,sizeof(t));
		rep(i,n){
			int d,p,q;
			cin>>d>>p>>q;
			q--;
			int row;
			for(row=0;!stop(row,q,d,p);row++);
			putBlock(row,q,d,p);
			//disp();
			deleteLine(row,d==1?row-1:row-p);

			//disp();
		}

		int ans = 0;
		rep(i,5000) rep(j,5) if(t[i][j]==1) ans++;
		cout<<ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
while true
    w, h = gets.chomp.split.map(&:to_i)
    break if [w, h] == [0, 0]

    map = []
    x, y = nil, nil
    h.times{|j|
        line = gets.chomp
        map << line
        if z = line.index("@")
            x, y = z, j
        end
    }
#    map.each{|m| puts m}
#    puts "x#{x} y#{y}"
    sum = 0
    list = [[x, y]]
    until list.empty?
        x2, y2 = list.pop
        if map[y2][x2] != "#"
            map[y2][x2] = "#"
            sum += 1
            list << [x2+1, y2] if x2 < w-1 && map[y2][x2+1] == "."
            list << [x2-1, y2] if x2 > 0 && map[y2][x2-1] == "."
            list << [x2, y2+1] if y2 < h-1 && map[y2+1][x2] == "."
            list << [x2, y2-1] if y2 > 0 && map[y2-1][x2] == "."
        end
    end
    puts sum
#    puts
end


Measured memory_bytes: 6856
#include<iostream>
#include<cmath>

using namespace std;

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


	int numberOfMonitoring = 2 * D + 1;

	if (N % numberOfMonitoring == 0) {
		cout << N / numberOfMonitoring << endl;
	}
	else {
		cout << (N / numberOfMonitoring)+1 << endl;
	}
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  vector<int>x(N),y(M);
  for(int i=0;i<N;i++)cin>>x[i];
  for(int i=0;i<M;i++)cin>>y[i];
  for(int z=X+1;z<=Y;z++){
    bool ok=false;
    for(int i=0;i<N;i++)if(x[i]>=z)ok=true;
    for(int i=0;i<M;i++)if(y[i]<z)ok=true;
    if(!ok){
      cout<<"No War"<<endl;
      return 0;
    }
  }
  cout<<"War"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

struct T{
	T *l, *r;
	int h;
	T(){l=r=NULL;h=1;}
	bool operator==(const T &o)const{
		if(h==1||o.h==1)return h==o.h;
		return *l==*(o.l)&&*r==*(o.r);
	}
	bool operator<(const T &o)const{
		if(h!=o.h)return h<o.h;
		if(h==1)return 0;
		if(!(*l==*(o.l)))return *l<*(o.l);
		return *r<*(o.r);
	}
};
T *normalize(T *t){
	T *res=new T();
	if(t->h==1)return res;
	T *l=normalize(t->l), *r=normalize(t->r);
	if(*l<*r)res->r=l, res->l=r;
	else res->l=l, res->r=r;
	res->h=max(l->h,r->h)+1;
	return res;
}
map<T,double> dp;
map<T,set<T> > dp2;
set<T> subsets(T *t){
	if(dp2.count(*t))return dp2[*t];
	if(t->h==1){
		set<T> res;
		res.insert(*t);
		return dp2[*t]=res;
	}
	set<T> res,l=subsets(t->l),r=subsets(t->r);
	res.insert(*t);
	res.insert(all(l));
	res.insert(all(r));
	return dp2[*t]=res;
}
double calc(T *t){
	if(dp.count(*t))return dp[*t];
	if(t->h==1)return dp[*t]=0;
	set<T> sl=subsets(normalize(t->l)), sr=subsets(normalize(t->r)), s=sl;
	s.insert(all(sr));
	int cnt=0;
	fr(i,s)if(sl.count(*i)&&sr.count(*i))cnt++;
	return dp[*t]=cnt*1.0/s.size();
}
string out(T* t){
	if(t->l==NULL)return "x";
	return "("+out(t->l)+" "+out(t->r)+")";
}
int cmp(T *a,T *b){
	double x=calc(normalize(a)), y=calc(normalize(b));
	if(a->h==1&&b->h==1)return 0;
	if(abs(x-y)>EPS)return x<y?-1:1;
	T *a1,*a2,*b1,*b2;
	if(cmp(a->l,a->r)<0)a1=a->l, a2=a->r;
	else a1=a->r, a2=a->l;
	if(cmp(b->l,b->r)<0)b1=b->l, b2=b->r;
	else b1=b->r, b2=b->l;
	int res=cmp(a1,b1);
	if(res)return res;
	return cmp(a2,b2);
}
T* form(T *t,bool left,bool root){
	T *res=new T();
	if(t->h==1)return res;
	if((cmp(t->l,t->r)<0)^!left)res->l=form(t->l,1,0), res->r=form(t->r,0,0);
	else res->l=form(t->r,1,0), res->r=form(t->l,0,0);
	res->h=max(t->l->h,t->r->h)+1;
	return res;
}
string in;
T* rec(int l,int r){
	if(r-1==l)return new T();
	int i,d=0;
	for(i=r-1;i>=l;i--){
		if(in[i]==')')d++;
		if(in[i]=='(')d--;
		if(d==0)break;
	}
	if(i==l)return rec(l+1,r-1);
	T *res=new T();
	res->l=rec(l,i-1);
	res->r=rec(i,r);
	res->h=max(res->l->h,res->r->h)+1;
	return res;
}

	
int main(){
	while(getline(cin,in),in!="0"){
		T *t=rec(0,in.size());
		cout<<out(form(t,1,1))<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define   sz(s)         s.size()
#define   ll            long long int
#define   ull           unsigned ll
#define   ld            long double
#define   print(v)      for(ll i=0;i<v.size();i++)cout<<v[i]<<" "
#define   printpair(v)  for(ll i=0;i<v.size();i++)cout<<v[i].first<<" "<<v[i].second<<"\n"
#define   bmd           1000000007
#define   bmd1          998244353
#define   umll          unordered_map<ll,ll>
#define   mll           map<ll,ll>
#define   mcl           map<char,ll>
#define   pll           pair<ll,ll>
#define   F             first
#define   S             second
#define   setp(x)       setprecision(x)
#define   pb            push_back
#define   all(v)        v.begin(),v.end()
#define   tr(a)         for(auto it=a.begin();it!=a.end();it++)
#define   trr(a)        for(auto it1=a.begin();it1!=a.end();it1++)
#define   vll           vector<long long int>
#define   sorty(v)      sort(v.begin(),v.end())
#define   rsort(v)      sort(v.rbegin(),v.rend())
#define   PI            3.1415926535897932384626
#define   db()          cout<<"\n"<<"here"<<"\n"
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


//---------------------------------------------------------------------------
const int MOD = bmd;
const int N=2e5+100;
inline  ll sqr(ll x){return x*x;}
inline  void normal(ll &a) { a = (a+MOD)%MOD; }
inline  ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline  ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline  ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline  ll modPow(ll b, ll p) { ll r = 1;b=b%MOD; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline  ll modInv(ll a) { return modPow(a, MOD-2); }
inline  ll modDiv(ll a,ll b) { return modMul(a, modInv(b)); }
//---------------------------------------------------------------------------
void solve()
{
    string s1,s2;
    cin>>s1>>s2;
    for(ll i=0;i<sz(s1);i++){
        if(s1[i]!=s2[i]){
            cout <<"No\n";
            return;
        }
    }
    cout <<"Yes\n";


}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);//first give all input then gives output

    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
}*/

signed main()
{
  string k;
  int d;
  cin >> k >> d;
  int n = k.size();
  
  vector<vvi> dp(n+1, vvi(2, vi(d)));
  dp[0][0][0] = 1;
  rep(i, 0, n) rep(j, 0, 2) rep(l, 0, d){
    int x = j ? 9 : k[i]-'0';
    rep(y, 0, x+1){
      (dp[i+1][j|y<x][(l+y)%d] += dp[i][j][l]) %= mod;
    }
  }

  int ans = (dp[n][0][0]+dp[n][1][0]-1+mod) % mod;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 18432
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static void Main()
    {
        new Magatro().Solve();
    }
}

class Magatro
{
    private const int Mod = (int)1e9 + 7;
    private long[] F;
    private int N = int.Parse(Console.ReadLine());
    private int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    private int Not;

    private void CalcF()
    {
        F = new long[N + 2];
        for (int i = 0; i <= N + 1; i++)
        {
            if (i == 0)
            {
                F[i] = 1;
            }
            else
            {
                F[i] = (F[i - 1] * i)%Mod;
            }
        }
    }

    private void Search()
    {
        var map = (new int[N + 1]).Select(i => -1).ToArray();
        for (int i = 0; i < N + 1; i++)
        {
            if (map[A[i]] == -1)
            {
                map[A[i]] = i;
            }
            else
            {
                Not = N + map[A[i]] - i;
                break;
            }
        }
    }

    private long Pow(long a, long b, long mod)
    {
        long result = 1;
        while (b > 0)
        {
            if (b % 2 == 1)
            {
                result *= a;
                result %= mod;
            }
            a *= a;
            a %= mod;
            b /= 2;
        }
        return result;
    }

    private long C(long n, long m, long mod)
    {
        if (n < m)
        {
            return 0;
        }
        long numerator = F[n];
        long denominator = Pow((F[m] * F[n - m]) % mod, mod - 2, mod);
        return (numerator * denominator) % mod;
    }

    public void Solve()
    {
        CalcF();
        Search();
        var sb = new StringBuilder();
        for (int i = 1; i <= N + 1; i++)
        {
            long ans = C(N + 1, i, Mod)-C(Not,i-1,Mod);
            while (ans < 0)
            {
                ans += Mod;
            }
            sb.AppendLine(ans.ToString());
        }
        Console.Write(sb.ToString());
    }
}


Measured memory_bytes: 30812
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    st = sum(a)
    t = 0
    abs_t = 10 ** 10
    for i in range(n-1):
        t += a[i]
        st -= a[i]
        abs_t = min(abs_t, abs(st - t))
    print(abs_t)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 80928
#include <bits/stdc++.h>
#include <ctype.h>
#include <string>
using namespace std;
 
 
int main(){
    string S,T;
    cin>>S>>T;
    S+=S;
    if(S.find(T)==-1)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

typedef unsigned int uint;
int in() {
    int x = 0, c;
    for (; (uint)((c = getchar()) - '0') >= 10; ) { if (c == '-') return -in(); if (!~c) throw ~0; }
    do { x = (x << 3) + (x << 1) + (c - '0'); } while ((uint)((c = getchar()) - '0') < 10);
    return x;
}

using namespace std;

int u[14] = {} , n , sum , tot;
int w[52];
int memo[729][52];


int f(int s){
	if(memo[sum][s] >= 10) return false;
	else memo[sum][s]++;

	if(s==0){
		for(int i = n ; i > 0 ; i--){
			printf("%d%c",w[i],i!=1?' ':'\n');
		}
		return true;
	}
	if(s==n){
		for(int i = 1 ; i <= 13 ; i++){
			if(u[i]){
				--u[i];
				sum += i;
				w[s] = i;
				if( f(s-1) ) return true;
				sum -= i;
				++u[i];
			}
		}
	}else{

		bool chk = 0;
		for(int i = 1 ; i <= 13 ; i++){
			if(u[i] && tot % i == 0) chk = true;
		}
		
		if(!chk ){
			
			return false;
		}
		for(int i = 1 ; i <= 13 ; i++){
			if(u[i] && sum % i == 0){
				--u[i];
				sum += i;
				w[s] = i;
				if( f(s-1) ) return true;
				sum -= i;
				++u[i];
			}
		}
	}
	return false;
}
int main(){
	while(n=in() , n){
		
		tot = 0;
		memset(memo,0,sizeof(memo));
		for(int i = 1 ; i <= 13 ; i++){
			u[i] = 0;
		}
		for(int i = 0 ; i < n ; i++){ int a; a=in(); ++u[a]; tot += a; }
		sum = 0;
		if(!f(n)) cout << "No" << endl;
	}
}

Measured memory_bytes: 0
#!/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 = I()
dp = [[[0]*2 for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for x in range(10):
        if x == 0:
            for j in range(2):
                dp[i+1][1][j] += dp[i][0][j]
                dp[i+1][1][j] += dp[i][1][j]
                dp[i+1][1][j] %= mod
        elif x == 9:
            for j in range(2):
                dp[i+1][j][1] += dp[i][j][1]
                dp[i+1][j][1] += dp[i][j][0]
                dp[i+1][j][1] %= mod
        else:
            for j in range(2):
                for k in range(2):
                    dp[i+1][j][k] += dp[i][j][k]
                    dp[i+1][j][k] %= mod
print(dp[-1][1][1])

Measured memory_bytes: 358936
import Data.List

main :: IO ()
main = do
  (n:x:_) <- fmap (map read . words) getLine :: IO [Int]
  xs <- fmap (map read . words) getLine :: IO [Int]
  print $ solve x xs

solve :: Int -> [Int] -> Int
solve x xs = foldl1' gcd abss
  where
    abss = map (\y -> abs (y - x)) xs


Measured memory_bytes: 36220
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

signed main(){
	IO_STREAM;
	char C;
	cin>>C;
	if(C<'a'){
		cout<<'A'<<endl;
	}
	else{
		cout<<'a'<<endl;
	}
	return 0;
}


Measured memory_bytes: 3620
/// You just can't beat the person who never gives up

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 2e5+5 ,mod = 1e9+7 ;

int n ,k ,x ,cnt0 ;
vector<int> pos ,neg ;
bool Never_give_up(){
    scanf("%d%d",&n,&k);
    long long all = 1 ;
    for(int i=0;i<n;++i){
        scanf("%d",&x);
        all = (all*x%mod+mod)%mod ;
        if(x==0) ++cnt0 ;
        else if(x>0) pos.push_back(x) ;
        else neg.push_back(-x) ;
    }
    if(n==k) return cout << all ,0 ;
    if(pos.size() + neg.size()/2*2 < k) return cout << 0,0 ;
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end());
    all = 1 ;
    if(k%2){
        if(pos.size()){
            all = all*pos.back()%mod ;
            pos.pop_back() ;
            --k ;
        }
        else{
            if(cnt0) return cout << 0,0 ;
            for(int i=0;i<k;++i) all = (all*(-neg[i])%mod+mod)%mod ;
            return cout << all,0 ;
        }
    }
    vector<long long> v ;
    while(pos.size()>=2){
        v.push_back(1ll*pos[pos.size()-1] * pos[pos.size()-2]);
        pos.pop_back();
        pos.pop_back();
    }
    while(neg.size()>=2){
        v.push_back(1ll * neg[neg.size()-1] * neg[neg.size()-2]);
        neg.pop_back();
        neg.pop_back();
    }
    k /= 2 ;
    sort(v.rbegin(),v.rend()) ;
    for(int i=0;i<k;++i) all = 1ll * (v[i]%mod) * all %mod ;
    cout << all ;
    return 0 ;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt" ,"r" ,stdin);
    freopen("output.txt" ,"w" ,stdout);
#endif
    int t = 1 ;
    //scanf("%d",&t);
    while(t--) Never_give_up();
    return 0;
}

Measured memory_bytes: 5516
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ESP 1e-5

int main(void){
    int n, x, t;
    cin >> n >> x >> t;
    int time = (n % x == 0) ? n / x : n / x + 1;
    cout << time * t << endl;
    return 0;
}


Measured memory_bytes: 3528
from collections import Counter

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 0
c = Counter()
c[0] = 1

S = [0] * (N+1)
s = 0

for idx, a in enumerate(A):
    idx += 1

    if idx >= K: c[S[idx-K]] -= 1
        
    s = (s+a) % K
    
    b = (s - idx) % K
    S[idx] = b    
    ans += c[b]
    c[b] += 1
    
print(ans)

Measured memory_bytes: 40504
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
using P = pair<int, int>; 
using ll = long long;
using M = map<int, int>;

int main()
{
  int n;
  cin >> n;
  map<string, int> mp;
  vector<string> v;
  string s[n];
  int m = 0;
  rep(i, n){
    cin >> s[i];
    mp[s[i]]++;
    m = max(m, mp[s[i]]);
  }
  rep(i, n){
    if(mp[s[i]] == m) {
      v.push_back(s[i]);
      mp[s[i]] = 0;
    }
  }
  sort(v.begin(), v.end());
  rep(i, v.size()){
    cout << v[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 33360
import heapq as hq
from collections import deque
n,m,s,t=map(int,input().split())
#リンク情報をつくる
yenLinks={}
snkLinks={}
for _ in range(m):
    u,v,a,b=map(int,input().split())
    if u not in yenLinks:
        yenLinks[u]=[(v,a)]
        snkLinks[u]=[(v,b)]
    else:
        yenLinks[u].append((v,a))
        snkLinks[u].append((v,b))
    if v not in yenLinks:
        yenLinks[v]=[(u,a)]
        snkLinks[v]=[(u,b)]
    else:
        yenLinks[v].append((u,a))
        snkLinks[v].append((u,b))
#Dijkstra法をする関数
INF=float('inf')
def dijkstra(start,links,nodeNum):
    ans=[INF for _ in range(nodeNum+1)]
    ans[start]=0
    PQ=[(0,start)]
    hq.heapify(PQ)
    while PQ:
        (Vd,V) = hq.heappop(PQ)
        #print([V,Vd,ans[V]])
        if Vd > ans[V]:
            continue
        for (W,D) in links[V]:
            cand = ans[V] + D
            if cand < ans[W]:
                ans[W] = cand
                hq.heappush(PQ,(ans[W],W))
            #print(PQ)
    return(ans)
#Dijkstra法実行
yenKstra=dijkstra(s,yenLinks,n)
snkKstra=dijkstra(t,snkLinks,n)
#答えを求める
i=n
ans=INF
answers=[]
while i>0:
    cand = yenKstra[i]+snkKstra[i]
    ans = min(ans,cand)
    answers.append(10**15-ans)
    i-=1
answers.reverse()
#出力
for ans in answers:
    print(ans)

Measured memory_bytes: 91744
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<iterator>
#include<stack>
#include<queue>
#include<utility>
#include<functional>
#include<bitset>
#include<numeric>
#include<cstring>
#include<tuple>
using namespace std;

int n;
long double ans = 0.0, dp[ 3003 ][ 3003 ];
vector< long double > p( 3003 ), pro( 3003, 1 );

long double solve( int i, int heads )
{
	if( i == 0 )
	{
		return !heads;
	}
	else if( i >= 1 && heads == 0 )
	{
		return pro[ i ];
	}
	if( dp[ i ][ heads ] >= 0 )
	{
		return dp[ i ][ heads ];
	}
	dp[ i ][ heads ] = p[ i ] * solve( i - 1, heads - 1 ) + ( 1 - p[ i ] ) * solve( i - 1, heads );
	return dp[ i ][ heads ];
}

int main( void )
{
	ios :: sync_with_stdio( 0 );
	cin.tie( 0 );
	
	memset( dp, -1, sizeof( dp ) );
	cin >> n;
	for( int i = 1; i <= n; ++i )
	{
		cin >> p[ i ];		
	}
	for( int i = 1; i <= n; ++i )
	{
		pro[ i ] = pro[ i - 1 ] * ( 1 - p[ i ] );		
	}
	for( int i = n; i >= n / 2 + 1; --i )
	{
		ans += solve( n, i );
	}
	cout << setprecision( 15 ) << fixed << ans << "\n";
	return 0;
}

Measured memory_bytes: 141440
s=[input() for i in range(3)]
l=[len(s[i]) for i in range(3)]
abc=[0,0,0]
now=0

while abc[now]!=l[now]:
    s_sub=s[now][abc[now]]
    abc[now]+=1
    now=(0 if s_sub=="a" else 1 if s_sub=="b" else 2)
    
print("A" if now==0 else "B" if now==1 else "C")

Measured memory_bytes: 38384
#include <iostream>

int main()
{
    int n;
    int odd = 0;
    std::cin >> n;
    
    for (int i = 1; i <= n; i++) {
        if (i % 2 != 0) {
            odd++;
        }
    }

    std::cout << (double)(odd / (double)n) << std::endl;

    return 0;
}


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

#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int op(int a, int b) { return max(a, b); }

int e() { return -1; }

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  REP(i, n) { cin >> a[i]; }
  const int M = 300000 + 1;
  vector<int> dp(M, 0);
  segtree<int, op, e> seg(dp);

  REP(i, n) {
    int aft = seg.prod(max(a[i] - k, 0), min(a[i] + k + 1, M)) + 1;
    seg.set(a[i], aft);
  }
  cout << seg.prod(0, M) << endl;
}

Measured memory_bytes: 9584
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<int>(1000,10000)(rng)

ll binpow(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
        return res * a;
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    cout<<n+n*n+n*n*n;
    return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner

import scala.collection.mutable.ArrayBuffer
import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val writer = new java.io.PrintWriter(System.out)
    writer.println(solve(sc))
    writer.flush()
  }

  def solve(sc: Scanner): String = {
    val (n, k) = (sc.nextInt(), sc.nextInt())
    val values = Vector.fill(n)(sc.nextLong())
    debug(n, k, values)

    getTakePatterns(k).foldLeft(ArrayBuffer.empty[Long]) { case (acc, (l, r, d)) =>
      val fromLeft = if (l > 0) values.slice(0, l) else Vector.empty[Long]
      val fromRight = if (r > 0) values.slice(l, values.size).reverse.slice(0, r) else Vector.empty[Long]
      val takes = fromLeft ++ fromRight
      val value =
        if (d > 0) {
          val dropValue = takes.sorted.take(d).foldLeft(0L) { (acc, v) =>
            if (v < 0) {
              acc + v
            } else acc
          }
          takes.sum + dropValue * -1
        } else {
          takes.sum
        }
      acc += (if (value > 0) value else 0)
    }.max.toString
  }

  def getTakePatterns(k: Int): Vector[(Int, Int, Int)] = {
    @tailrec
    def dfs(buf: ArrayBuffer[(Int, Int, Int)], i: Int): ArrayBuffer[(Int, Int, Int)] = {
      (0 to k - i).foreach { j =>
        val x = if (k - i - j > 0) k - i - j else 0
        if (i + j >= x) {
          buf += ((i, j, x))
        }
      }
      if (i < k) {
        dfs(buf, i + 1)
      } else buf
    }

    val initialBuf = ArrayBuffer.empty[(Int, Int, Int)]
    dfs(initialBuf, 0).toVector
  }

  private def debug(x: Any): Unit = {
    if (System.getenv("LOCAL_DEBUG") != null) println(x)
  }
}


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

#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define reset(x, y) memset(x, y, sizeof(x))
#define BUG(x) cerr << #x << " = " << (x) << endl
#define BUGP(x) cout << #x << " = " << (x)._1 << ", " << (x)._2 << endl
using namespace std;

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

const int dr[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dc[] = {0, -1, 0, 1, -1, 1, -1, 1};
// Head

LL n;

int main() {
    cin >> n;
    LL cur = 100;
    for (int i = 1; i <= 4000; ++i) {
        cur = cur * 1.01;
        if (cur >= n) {
            cout << i << '\n';
            return 0;
        }
    }
}

Measured memory_bytes: 3636
// Marcin Knapik
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // order_of_key
// #include <ext/pb_ds/tree_policy.hpp> // find by order
// using namespace __gnu_pbds; 
// #define ordered_set tree< int , null_type,less< int >, rb_tree_tag,tree_order_statistics_node_update>  

// const ll MAX_LL = 0xFFFFFFFFFFFFFFFF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_int_distribution<ll>(a, b)(rng)

typedef long double             ld;
typedef long long               ll;
typedef pair<int, int>          ii;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<vll>             vvll;
typedef vector<ii>              vii;
typedef vector<vi>              vvi;
typedef vector<vii>             vvii;
#define pll pair<long long, long long>
#define vpll vector<pll>
#define ull unsigned long long

#define sz(a)                   (int)(a).size()
#define pb                      push_back
#define all(c)                  (c).begin(), (c).end()
#define rall(c)                 (c).rbegin(), (c).rend()
#define FOR(i, a)               for (int i = 0; i < (a); i++)
#define f                       first
#define s                       second

template <class T> inline bool setmin(T &a, T b){if (a > b)return a = b, 1;return 0;}
template <class T> inline bool setmax(T &a, T b){if (a < b)return a = b, 1;return 0;}

template<class T> inline T fast(T a,T b,T mod) {ll res = 1; while(b){if(b&1) res = (res*a)%mod;a = (a*a)%mod;b >>= 1;}return res;}
template<class T> istream &operator>>(istream &os, vector<T> &container){for (auto &u : container)os >> u;return os;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}
template<class T> inline T gcd(T a, T b) { while (b)swap(a %= b, b); return abs(a); }

const ll INF = 1e9 + 7;
const ll mod = 998244353;
const ll BIG_INF = 1e18 + 7;
const ll N = 1e6+7;
const ll T = 1<<20;
const ld inf = 1e18;

ll n, m, q;

void solve(){
	cin >> n;
	cout << (1000 - n % 1000) % 1000 << '\n';
}

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

	q = 1;
	// cin >> q;

	while(q--)
		solve();
}	

Measured memory_bytes: 3652
<?php
  $n = (int)fgets(STDIN);
  for($i=0;$i<$n;$i++) {
      $a = explode(" ",trim(fgets(STDIN)));
      $b = $c = 0;
      $r = "YES";

      foreach($a as $vs) {
          $v = (int)$vs;
          if($b<$v) $b = $v;
          else if($c<$v) $c = $v;
          else {
              $r = "NO";
              break;
          }
      }
      echo $r."\n";
  }

Measured memory_bytes: 15060
function gets(str){
  this._s = str.split("\n");
  this._y = 0;
};
gets.prototype = {
  a: function(f){
    var s = this._s, y = this._y, r;
    if(typeof s[y] === "string")s[y] = s[y].split(" ").reverse();
    r = s[y].pop();
    if(!s[y].length)this._y++;
    return f?r:+r;
  },
  l: function(f){
    var s = this._s[this._y++].split(" ");
    return f?s:s.map(a=>+a);
  },
  m: function(n,f){
    var s = this._s, y = this._y, r = [], i = 0;
    if(f)for(;i < n; i++)r[i] = s[y+i].split(" ");
    else for(;i < n; i++)r[i] = s[y+i].split(" ").map(a=>+a);
    this._y += n;
    return r;
  },
};
var o=new gets(require("fs").readFileSync("/dev/stdin","utf8"));

function inv(a){
  var n = a.length;
  var m = 0;
  for(var i = 1; i < n; i <<= 1){
    var b = [];
    for(var j = 0; j < n;){
      var l = j, r = Math.min(n,l+i), l2 = r, r2 = Math.min(n,r+i);
      while(j < r2){
        if(l === l2)b[j]=a[r++];
        else if(r === r2)b[j]=a[l++];
        else if(a[l] > a[r]){m+=l2-l;b[j]=a[r++];}
        else b[j]=a[l++];
        j++;
      }
    }
    a = b;
  }
  return m;
}

console.log(main());
function main(){
  var n = o.a();
  var a = o.l();
  if(n <= 2)return Math.max(...a);
  var p = Math.floor(n * (n+1) / 4 + 1);
  var l = 2, r = 1e9+1;
  while(l < r){
    var m = l + r >> 1;
    var b = [0];
    for(var i = 0; i < n; i++){
      b[i+1] = b[i];
      if(a[i] < m)b[i+1]--;else b[i+1]++;
    }
    if(inv(b) < p)l = m+1; else r = m;
  }
  return l-1;
}

Measured memory_bytes: 69364
# https://atcoder.jp/contests/abc112/tasks/abc112_d

n, m = map(int, input().split())
if n == 1:
    ans = m
else:
    ans = 1
    i = 1
    limit = m / n
    while i <= limit:
        if m % i == 0 and m // i >= n:
            ans = max(ans, i)
        i += 1
print(ans)


Measured memory_bytes: 40300