akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define llong long long
#define fr(i,l,r) for(i=(l);i<(r);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000//10^12


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


int main(void)
{
	//変数の宣言
	int n;
	static int a[200010];
	static int b[200010];
	static int use[200010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	llong int temp,temp1,temp2;
	int max,min;
	int len;
	int sum=0;

	//データの読み込み
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		use[i]=0;
	}
	
	

//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	qsort(a, n, sizeof(int), compare_int);
	
//	for(i=0;i<n;i++){
//		printf("%d ",a[i]);
//	}
//	pritnf("\n");
	
	j=0;
	for(i=0;i<n;i++){
		if(i==0){
			b[0]=a[0];
			temp=a[0];
			use[0]++;
		}else{
			if(a[i]!=temp){
				j++;
				b[j]=a[i];
				temp=a[i];
				use[j]++;
			}else{
				use[j]++;
			}
		}
	}
	
	n=j+1;
	
//	for(i=0;i<n;i++){
//		printf("%dは%dこ\n",b[i],use[i]);
//	}
	
	i=0;
	k=0;
	l=0;
	while(i<n){
//		printf("i=%d,k=%d,l=%d\n",i,k,l);
		if(use[i]==0||flag==1){
//			printf("b[i]=%dは探索終了 use[i]=%d\n",b[i],use[i]);
//			for(j=0;j<n;j++){
//				printf("%d ",use[j]);
//			}
//			printf("\n");
			i++;
			flag=0;
		}else{
//			printf("tag0 temp=%lld,i=%d, b[i]=%d\n",temp,i,b[i]);
			temp=1;
			while(temp<b[i]+1){
//				printf("tag1\n");
				temp=temp*2;
			}
			
			k=i;
			l=n-1;
			
//			printf("tag1 temp=%lld,i=%d, b[i]=%d\n",temp,i,b[i]);
			
			if(temp==b[i]*2){
//				printf("%d,%d pair\n",b[i],b[k]);
					ans=ans+use[i]/2;
					use[i]=use[i]%2;
				flag=1;
			}else if(temp-b[i]==b[l]){
//				printf("%d,%d pair\n",b[i],b[l]);
				temp2=min(use[i],use[l]);
				ans=ans+temp2;
				use[i]=use[i]-temp2;
				use[l]=use[l]-temp2;
				flag=1;
			}else{
				while(l-k>1){
					j=(l+k)/2;
//					printf("tag2 i=%d,k=%d,l=%d j=%d b[j]=%d \n",i,k,l,j,b[j]);
					if(temp-b[i]==b[j]){
//						printf("%d,%d pair\n",b[i],b[j]);
						if(i==j){
							ans=ans+use[j]/2;
							use[j]=use[j]%2;
						}else{
							temp2=min(use[i],use[j]);
							ans=ans+temp2;
							use[i]=use[i]-temp2;
							use[j]=use[j]-temp2;
						}
						flag=1;
						break;
					}else if(temp-b[i]>b[j]){
//						printf("temp=%d,b[i]=%d,b[j]=%d kをjに\n",temp,b[i],b[j]);
						l=j;
					}else if(temp-b[i]<b[j]){
//						printf("temp=%d,b[i]=%d,b[j]=%d lをjに\n",temp,b[i],b[j]);
						k=j;
					}
				}
				if(l-k<=1){
					flag=1;
				}
			}
		}
	}
	
//	printf("計算部分終了\n");
	//出力
	printf("%d",ans);
	
	
//	printf("結果の出力終了\n");
	
	return 0;
	
}



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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
const int MAX_N=55;
int par[MAX_N];
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
    }
}
int root(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=root(par[x]); 
    }
}
bool same(int x,int y){
    return root(x)==root(y);
}
void unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y){
        return;
    }else{
        par[x]=y;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
  	string s=in<string>();
  	ll ans;ans=0;
  	int cnt_B;cnt_B=0;
  	REP(i,s.size()){
    	if(s[i]=='B'){
          	cnt_B++;
        	continue;
        }else{
        	ans+=cnt_B;
        }
    }
  	print(ans);
    return 0;
}


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

#define int long long
int f(int b, int n){
	if(n < b) return n;
	else return f(b, n / b) + (n % b);
}

signed main()
{
	int n, s, b, ans = 1e18;
	cin >> n >> s;
	if(n == s){
		cout << n + 1;
		return 0;
	}
	for(int i = 2; i <= sqrt(n); i++){
		if(f(i, n) == s){
			cout << i;
			return 0;
		}
	}
	for(int i = 1; i <= sqrt(n - s); i++){
		b = (n - s) / i + 1;
		if(f(b, n) == s) ans = min(ans, b);
	}
	if(ans == 1e18) ans = -1;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
s = str(input())
ans = 0
for i in range(2 ** (len(s) - 1)):
    num = [s[0]]
    for j in range(len(s) - 1):
        if ((i >> j) & 1): #+を挿入
            num.append(s[j + 1])
        else: #文字を結合
            num[-1] += s[j + 1]
    ans += sum(list(map(int, (num[i] for i in range(len(num))))))
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	int n;
	ll T;
	cin >> n >> T;
	
	vector<ll> t(n);
	for(int i = 0; i < n; ++i) {
		cin >> t[i];
	}
	
	ll ans = 0LL;
	for(int i = 0; i < n - 1; ++i) {
		if( t[i + 1] - t[i] > T ) ans += T;
		else ans += t[i + 1] - t[i]; 
	}
	
	ans += T;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 4804
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  int D,G;
  cin >>D>>G;
  int P[D];
  int C[D];
  int K[D];
  for(int i=0;i<D;i++){
    cin>>P[i]>>C[i];
  }
  int ans=0;
  int temp=0;
  int minans=10000;

  for(int i=0;i<(1 << D);i++){
    ans=0;
    temp=0;
    fill(K,K+D,1);
    
    for(int j=0;j<D;j++){
      if(i & (1<<j)){
        K[j]=0;
        ans+=P[j];
        temp+=P[j]*(j+1)*100+C[j];
      }
    }
    //cout<<i<<" "<<temp<<"#1#"<<ans<<endl;
    //足りないときは点数の高い未回答問題を中途半端に解く
    if(temp<G){
      for(int k=D-1;k>=0;k--){
        if(K[k]==1){
          int hampa=(G-temp)/((k+1)*100);
          if(hampa>P[k]){
            break;
          }
          //cout<<"####"<<hampa<<"#"<<k<<"#"<<K[k]<<endl;
          if((G-temp)%((k+1)*100) != 0){
            hampa++;      
          }
          ans+=hampa;
          temp+=hampa*(k+1)*100;         
          break;
        }
      }
    }
    //cout<<i<<" "<<temp<<"#2#"<<ans<<endl;
    if(temp>=G){
      minans=min(minans,ans);
    }
  }

  cout<<minans<<endl;
  return 0;
}


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

#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433L;

template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
    string S; cin >> S;
    Yn(S[2]==S[3]&&S[4]==S[5]);



    return 0;
}


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

int main(){
	int mon, day, week;
	string ans[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
	int start_week[13] = {-1, 3, 6, 0, 3, 5, 1, 3, 6, 2, 4, 0, 2};
	while(cin >> mon >> day){
		if(mon==0 && day==0){
			break;
		}
		week = start_week[mon]+day-1;
		week %= 7;
		cout << ans[week] << endl;
	}
	return 0;
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());

    long long sum = 0;
    for (int i = 0; i < k; i++) sum += v[i];
    cout << sum << endl;
}

Measured memory_bytes: 3632
def main():
    N, M = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(N)]
    cd = [list(map(int, input().split())) for _ in range(M)]

    for s in ab:
        tmp = 10 ** 10
        ans = 0
        for i, t in enumerate(cd, 1):
            if tmp > abs(s[0]-t[0]) + abs(s[1]-t[1]):
                ans = i
                tmp = abs(s[0]-t[0]) + abs(s[1]-t[1])
        print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9240
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] a = new int[5];
		
		for(int i = 0; i < 5; i++) {
			a[i] = Integer.parseInt(sc.next());
		}
		
		int k = Integer.parseInt(sc.next());
		
		for(int i = 0; i < 5; i++) {
			for(int j = 4; j >= 0+(i+1); j--) {
				if(Math.max(a[i], a[j]) - Math.min(a[i], a[j]) > k) {
					System.out.println(":(");
					return;
				}
			}
		}
		System.out.println("Yay!");
	}
}


Measured memory_bytes: 25044
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)

	n := nextInt()
	cnt := 0
	r := false

	for i := 0; i < n; i++ {
		d1 := nextInt()
		d2 := nextInt()

		if d1 == d2 {
			cnt++
		} else {
			cnt = 0
		}

		if cnt == 3 {
			r = true
		}
	}

	if r {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1804
ans =  0

def main():
    N, M, Q = map(int, input().split())
    q = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        q.append([a, b, c, d])

    def calc(array):
        global ans
        score = 0
        for a,b,c,d in q:
            if array[b]-array[a] == c:
                score += d
        ans = max(ans, score)

    def search(array):
        global count
        if len(array) == N+1:
            calc(array)
        else:
            for i in range(array[-1], M+1):
                search(array+[i,])
    search([1, ])
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

int a[1010];

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

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

    int ans = 0;

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ans = max(ans,abs(a[i]-a[j]));
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())

MOD = 10 ** 9 + 7

ctr = [0] * (K + 1)
for n in reversed(range(1, K + 1)):
    ctr[n] = pow(K // n, N, MOD)
    for j in range(2 * n, K + 1, n):
        ctr[n] -= ctr[j]

ans = 0
for n in range(1, K + 1):
    ans += n * ctr[n]
    ans %= MOD

print(ans)


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

#define vint vector<int>

int main() {
	vector<vint> vvec; int an, tn, fn1, fn2, en, set;
	cin >> an >> tn; vvec.resize(an);
	for (int i = 0; i < tn; i++) {
		cin >> fn1;
		switch (fn1) {
		case 0: cin >> fn2 >> en; vvec[fn2].push_back(en); break;
		case 1:	cin >> fn2; set = 0;
			for (int i : vvec[fn2]) cout << (set++ ? " " : "") << i;
			cout << endl; break;
		case 2: cin >> fn2; vvec[fn2].clear(); break;
		}
	}
	return 0;
}


Measured memory_bytes: 5856
#include <bits/stdc++.h>
using namespace std;
#define sorted(a) sort(a.begin(), a.end());
#define ALL(a) (a).begin(), (a).end()
typedef long long unsigned int ll;
const long mod = 1e9 + 7;

int main(void) {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int R, D, X;
  cin >> R >> D >> X;

  for (int i = 0; i < 10; i++) {
    X = R * X - D;
    cout << X << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  bool b=true;
  for(int i=0;i<s.size();i++){
    if(i%2==0){
      if(s[i]=='L'){
        b=false;
      }
    }
    if(i%2==1){
      if(s[i]=='R'){
        b=false;
      }
    }
  }
  if(b){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}



Measured memory_bytes: 256
t = input()
s = [i for i in t]
if s[0] == "?":
    s[0] = "D"
for i in range(1, len(t) - 1):
    if s[i] == "?":
        if s[i-1] == "D" and s[i+1] == "D":
            s[i] = "P"
        elif s[i-1] == "D" and s[i+1] == "?":
            s[i] = "P"
        else:
            s[i] = "D"
if s[-1] == "?":
    s[-1] = "D"
print("".join(s))

Measured memory_bytes: 11116
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int cnt = 1;
		while (true) {
			int x = sc.nextInt();

			if (x == 0) {
				break;
			}

			System.out.println("Case " + cnt + ": " + x);
			cnt++;
		}
	}
}

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

using namespace std;

typedef long long ll;

int n;
ll A[100100];

void solve(ll s)
{
	ll ans=0,S=0;
	int l=0,r=-1;
	while(true)
	{
		while(r<n&&S<=s)
			S+=A[++r];
		//
		if(r>=n) break;
		while(S>s)
		{
			//printf("%d %d %lld\n",r,l,S);
			ans+=r-l;
			S-=A[l++];
		}
	}
	while(l<n)
		ans+=n-(l++);
	printf("%lld\n",ans);
}

int main()
{
	int q,ma=0;
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++)
		scanf("%lld",&A[i]);
	for(int i=0;i<q;i++)
	{
		ll s;
		scanf("%lld",&s);
		solve(s);
	}
	return 0;
}

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

int main() {
	int c = 0;
	double m[100000];
	while(scanf("%lf", &m[c]) != EOF){
		c++;
	}
	sort(m, m + c);
	cout << fixed << m[c - 1] - m[0] << endl;
	return 0;
}

Measured memory_bytes: 1304
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n, W;
    cin>>n>>W;
    vector <ll> w(n);
    vector <ll> v(n);
    ll total_val = 0;
    for(ll i = 0; i < n; i++){
        cin>>w[i]>>v[i];
        total_val += v[i];
    }
    vector <ll> dp(total_val + 1, 10e15);
    dp[0] = 0;
    for(ll i = 0; i < n; i++){
        for(ll j = total_val - v[i]; j >= 0; j--){
            dp[j + v[i]] = min(dp[j + v[i]], dp[j] + w[i]);
        }
    }
    for(ll i = total_val; i >= 0; i--){
        if(dp[i] <= W){
            cout<<i<<endl;
            return 0;
        }
        
    }
    return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
INF = 1000000000
n = int(input())
h = list(map(int, input().split()))
dp = [INF]*n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))

print(dp[n-1])


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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

typedef long long ll;

const int mod = 1e9+7;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  int n, k;  cin >> n >> k;
  ll a[n];
  vector<ll> pos, neg;
  int z = 0;
  for (int i = 0; i < n; ++i){
    cin >> a[i];
    if(a[i]>0)  pos.push_back(a[i]);
    else  if(a[i]<0)  neg.push_back(a[i]);
    else z++;
  }
  sort(neg.begin(), neg.end());
  sort(pos.begin(), pos.end());
  if(n-z < k){
    cout << "0\n";
    return 0;
  }
  ll ans = 1;
  int negp = neg.size()/2, ni = 0, pi = 0;
  if(k<=min(k/2,negp)*2+pos.size()){
    reverse(pos.begin(), pos.end());
    if(k&1){
      ans = pos[0], k--, pi++;
    }
    while(k){
      if(neg.size()-ni>=2 and pos.size()-pi>=2){
        if(neg[ni+1]*neg[ni] > pos[pi+1]*pos[pi]){
          ans = ans*neg[ni+1]%mod*neg[ni]%mod, ni += 2;
        } else {
          ans = ans*pos[pi+1]%mod*pos[pi]%mod, pi += 2;
        }
      } else if(neg.size()-ni>=2){
        ans = ans*neg[ni+1]%mod*neg[ni]%mod, ni += 2;
      } else {
        ans = ans*pos[pi+1]%mod*pos[pi]%mod, pi += 2;
      }
      k -= 2;
    }
  } else {
    if(z){
      cout << "0\n";
      return 0;
    }
    reverse(neg.begin(), neg.end());
    while(k){
      if(ni==neg.size()){
        ans = ans*pos[pi++]%mod;
      } else if(pi==pos.size()){
        ans = ans*neg[ni++]%mod;
      } else {
        if(abs(neg[ni])<pos[pi]){
          ans = ans*neg[ni++]%mod;
        } else {
          ans = ans*pos[pi++]%mod;
        }
      }
      k--;
    }
  }
  cout << ((ans%mod)+mod)%mod << "\n";

  return 0;
}


Measured memory_bytes: 6736
n = gets().to_i
l = gets().split(' ').map(&:to_i)

max_i = 0

for i in 1 ... l.length
	max_i = i if l[max_i] < l[i]
end

s = 0

for i in 0 ... l.length
	s += l[i] if i != max_i
end

puts (l[max_i] < s ? "Yes" : "No")


Measured memory_bytes: 3836
#include <stdio.h>
int a[100000],b[100000];
int main(){
  int N,M,x,y,sum=0;
  scanf("%d %d",&N,&M);
  for(int i=1;i<=N;i++)
    a[i]=1;
  b[1]=1;
  for(int i=0;i<M;i++){
    scanf("%d %d",&x,&y);
    if(a[x]!=0){
      a[x]--;
      a[y]++;
      if(b[x]==1){
        if(a[x]==0){
          b[x]=0;
          b[y]=1;
        }else{
          b[y]=1;
        }
      }
    }
  }
  for(int i=0;i<=N;i++)
    sum+=b[i];
  printf("%d\n",sum);
}

Measured memory_bytes: 896
#include <stdio.h>

int main(void) {
	int P, Q, R;
	int asumisu;
	if(scanf("%d%d%d", &P, &Q, &R) != 3) return 1;
	asumisu = P;
	if (asumisu < Q) asumisu = Q;
	if (asumisu < R) asumisu = R;
	printf("%d\n", P + Q + R - asumisu);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

int check(int n){
  int i;
  if(n<2)return 0;
  if(n==2)return 1;
  if(n%2==0)return 0;
  for(i=3;i<=n/i;i+=2)
    if(n%i==0)
      return 0;
  return 1;
}

int main(){
  int i,n,ans=0,a;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a);
    ans+=check(a);
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int m1, m2;
  vector<int> A(3);
  REP(i,3) cin >> A.at(i);
  sort ALL(A);
  m1=A.at(0);
  m2=A.at(1);
  cout << m1+m2 << endl;
}

Measured memory_bytes: 256
// Reads multiple ints in a line, separate by a space.
// It works even if the actual number of ints is smaller than n.
// WARNING: This function does not work for -2^31.
// NOTE: This function does not handle error cases.
fun fastReadInts(n: Int): IntArray {
  val xs = IntArray(n)
  val s = readLine()!!
  var currentValue = 0
  var isNegative = false
  var currentIndex = 0
  for (c in s) {
    if (c == ' ') {
      xs[currentIndex] = currentValue * if (isNegative) -1 else 1
      currentValue = 0
      isNegative = false
      currentIndex++
    } else if (c == '-') {
      isNegative = true
    } else {
      currentValue *= 10
      currentValue += c - '0'
    }
  }
  xs[currentIndex] = currentValue * if (isNegative) -1 else 1
  return xs
}

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val rawXs = fastReadInts(n)
  val xs = IntArray(n + 2)
  for (i in 1..n) {
    xs[i] = rawXs[i - 1]
  }

  val costs = IntArray(n + 2)
  for (i in 1..(n + 1)) {
    costs[i] = costs[i - 1] + Math.abs(xs[i] - xs[i - 1])
  }

  val ans = IntArray(n)
  for (i in 1..n) {
    ans[i - 1] = costs[n + 1] - Math.abs(xs[i + 1] - xs[i]) - Math.abs(xs[i] - xs[i - 1]) +
        Math.abs(xs[i + 1] - xs[i - 1])
  }
  println(ans.joinToString("\n"))
}


Measured memory_bytes: 45188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {
    int N;
    cin >> N;
    vector<set<ll>> v(N);
    int a, b;
    REP(i, N-1){
        cin >> a >> b;
        a--;
        b--;
        v[a].insert(b);
        v[b].insert(a);
    }
    vector<int> d(N, -1), d1(N, -1);
    d[0] = 0;
    d1[N-1] = 0;
    vector<int> tmp, tmp1;
    tmp.push_back(0);
    for(int i = 0; i < tmp.size(); i++){
        int iter = tmp[i];
        for(auto j: v[iter]){
            if (d[j] < 0){
                tmp.push_back(j);
                d[j] = d[iter] + 1;
            }
        }
    }

    tmp1.push_back(N-1);
    for(int i = 0; i < tmp1.size(); i++){
        int iter = tmp1[i];
        for(auto j: v[iter]){
            if (d1[j] < 0){
                tmp1.push_back(j);
                d1[j] = d1[iter] + 1;
            }
        }
    }
    a = 0, b = 0;
    REP(i, N) if (d[i] <= d1[i]) a++; else b++;
    string ans = (a > b) ? "Fennec" : "Snuke";
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 13944
#[derive(Default)]
//NOTE
//declare variables to reduce the number of parameters for dp and dfs etc.
struct Solver {}

impl Solver {
    fn solve(&mut self) {
        let stdin = std::io::stdin();
        let mut scn = Scanner {
            stdin: stdin.lock(),
        };
        let d: usize = scn.read();
        let t: usize = scn.read();
        let s: usize = scn.read();
        let result = if s * t >= d { "Yes" } else { "No" };
        println!("{}", result);
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| {
            let mut solver = Solver::default();
            solver.solve()
        })
        .unwrap()
        .join()
        .unwrap();
}
pub mod utils {
    const DYX: [(isize, isize); 8] = [
        (0, 1),   //right
        (1, 0),   //down
        (0, -1),  //left
        (-1, 0),  //top
        (1, 1),   //down right
        (-1, 1),  //top right
        (1, -1),  //down left
        (-1, -1), //top left
    ];

    pub fn try_adj(y: usize, x: usize, dir: usize, h: usize, w: usize) -> Option<(usize, usize)> {
        let ny = y as isize + DYX[dir].0;
        let nx = x as isize + DYX[dir].1;
        if ny >= 0 && nx >= 0 {
            let ny = ny as usize;
            let nx = nx as usize;
            if ny < h && nx < w {
                Some((ny, nx))
            } else {
                None
            }
        } else {
            None
        }
    }
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 2204
h, w = gets.split.map(&:to_i)
c = []
10.times do
  c << gets.split.map(&:to_i)
end
a = []
h.times do
  a << gets.split.map(&:to_i)
end

0.upto(9) do |k|
  0.upto(9) do |i|
    0.upto(9) do |j|
      c[i][j] = c[i][j] < c[i][k] + c[k][j] ? c[i][j] : c[i][k] + c[k][j]
    end
  end
end

ans = 0
a.each do |ai|
  ai.each do |a|
    ans += c[a][1] if a != -1 && a != 1
  end
end
puts ans


Measured memory_bytes: 2556
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer> tgt = new ArrayList<Integer>();
	static ArrayList<Integer> ans = new ArrayList<Integer>();
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {

		while(sc.hasNext()) {
			hit_and_blow();
		}
    }


	private static void hit_and_blow() {
		int h = 0;
		int b = 0;

		for (int i = 0; i < 4; i++) {
			tgt.add( sc.nextInt() );
		}

		for (int i = 0; i < 4; i++) {
			ans.add( sc.nextInt() );
		}

		for (int i = 0; i < 4; i++) {
			if ( tgt.contains( ans.get(i) ) == true){
				if ( ans.get(i) == tgt.get(i) ) {
					h++;
					continue;
				}

				b++;
			}
		}

		System.out.printf("%d %d\n", h, b);
		tgt.clear();
		ans.clear();
	}

}


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

int card[255][14]={{0}};

int main(void){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        char c;
        int num;
        cin >> c >> num;
        card[(int)c][num]=1;
    }
    for(int i=1;i<=13;i++){
        if(card[(int)'S'][i]==0){
            cout << "S " << i << endl;
        }
    }
    for(int i=1;i<=13;i++){
        if(card[(int)'H'][i]==0){
            cout << "H " << i << endl;
        }
    }
    for(int i=1;i<=13;i++){
        if(card[(int)'C'][i]==0){
            cout << "C " << i << endl;
        }
    }
    for(int i=1;i<=13;i++){
        if(card[(int)'D'][i]==0){
            cout << "D " << i << endl;
        }
    }
}


Measured memory_bytes: 3084
/*
 * Author : Sadi
 * Sat 04/07/2020
 * 17:26:10.18
 */
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    int n;
    cin >> n;
    int sum = 0;
    int maxlen = -1;
    for(int i = 0; i < n; ++i) {
        int len;
        cin >> len;
        sum += len;
        maxlen = max(maxlen, len);
    }
    if(sum - maxlen > maxlen) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
#!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()
    A = LI()
    B = [0] * N

    for i in range(1, N+1)[::-1]:
        j = 2
        tmp = 0
        while i * j <= N:
            tmp ^= B[i * j - 1]
            j += 1

        B[i - 1] = tmp ^ A[i - 1]

    print(sum(B))
    for i in range(N):
        if B[i]:
            print(i+1, end=" ")

if __name__ == '__main__':
    main()

Measured memory_bytes: 103000
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll a,b;
    cin >> a >> b;
    ll ichiretsu = (a+1)/2;
    ll answer;
    if(a == 1 || b == 1){
        cout << 1 << endl;
        return 0;
    }
    if(a%2){
        answer =(ichiretsu * (b/2))+(ichiretsu-1)*(b/2);
        if(b%2)answer+=ichiretsu;
    }
    else
        answer = ichiretsu * b;
    
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []

stop = []
heapq.heapify(stop)
deleted = []
heapq.heapify(deleted)

for i in range(q):
    D = readint()
    while block:
        if block[0][0]<=D:
            a = heapq.heappop(block)
            heapq.heappush(stop,a[1])
        else:
            break
    while free:
        if free[0][0]<=D:
            a = heapq.heappop(free)
            heapq.heappush(deleted,a[1])
        else:
            break
    while deleted:
        if stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        else:
            break
    if stop:
        ans.append(stop[0])
    else:
        ans.append(-1)

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)


Measured memory_bytes: 151000
import java.util.*;
import java.math.*;
     
class Main{
    public static void main(String[] args) {
        
        try(Scanner sc = new Scanner(System.in)){
            int n = Integer.parseInt(sc.next());
            long ans = 0;

            Long[] list = new Long[n];
            for(int i = 0; i < n; i++) list[i] = (long)0;          

            for(int i = 1; i <= n; i++){
                for(int j = i; j <= n; j += i){
                    list[j - 1] += 1;
                }                
            }

            for(int i = 0; i < n; i++){
                ans += list[i]*(i + 1);
            }

            System.out.println(ans);

        }catch(Exception e){
            e.printStackTrace();
        }        
    }
}

Measured memory_bytes: 94024
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <ctime>
#include <complex>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 1020000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
ll pcount(ll x) {return __builtin_popcountll(x);}
//const int mod = 1e9 + 7;
const int mod = 998244353;

ll dp[3030][3030][5];

int main(){
	ll n,k; cin >> n >> k;
	vl p(n); rep(i,n) cin >> p[i], p[i]--;
	vl c(n); rep(i,n) cin >> c[i];
	ll ans = -linf;
	rep(i,n){
		ll cycle = c[i];
		vl sum;
		sum.push_back(c[i]);
		ll now = p[i];
		ll cnt = 1;
		while(now != i){
			cycle += c[now];
			sum.push_back(max(sum.back(), cycle));
			now = p[now];
			cnt++;
		}
		ll t = k / cnt;
		ll r = k % cnt;
		if(cycle > 0){
			if(r != 0) chmax(ans, t * cycle + sum[r-1]);
			else chmax(ans, t * cycle);
			if(t > 0) chmax(ans, (t-1) * cycle + sum.back());
		}else{
			chmax(ans, sum[min(k-1, cnt-1)]);
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 3808
N, P = map(int, input().split())
S = input()

if P in [2, 5]:
  ans = 0
  for i, s in enumerate(S, 1):
    if int(s) % P == 0:
      ans += i
  print(ans)
else:
  dp = [0] * (N+1)
  for i, s in enumerate(S, 1):
    dp[i] = (dp[i-1]*10 + int(s)) % P
  digit = 1
  for i in range(N):
    j = N - i
    dp[j] = (dp[j] * digit) % P
    digit = (digit * 10) % P
  
  d = {}
  ans = 0
  for r in dp:
    if r in d:
      ans += d[r]
      d[r] += 1
    else:
      d[r] = 1
  print(ans)

Measured memory_bytes: 11616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;

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

  vector<vector<int>> x(n);
  vector<vector<int>> y(n);
  rep(i,n){
    int j_;
    cin>>j_;
    x[i]=vector<int>(j_);
    y[i]=vector<int>(j_);
    rep(j,j_){
      cin>>x[i][j]>>y[i][j];
      x[i][j]--;
    }
  }

  lint p=(1<<n)-1;
  int cmax=0;
  while(p>=0){
    int c=0;
    rep(i,n){
      if((p>>i)&1){
        c++;
        rep(j,x[i].size()){
          if(((p>>x[i][j])&1)!=y[i][j]) goto BREAK;
        }
      }
    }
    //cout<<p<<c<<endl;
    cmax=max(cmax,c);
    BREAK:
    p--;
  }

  return cmax;
}

int main(){cout<<app()<<endl;return 0;}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		//Input
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int X = Integer.parseInt(sc.next());

		int L[] = new int[N];
		for(int i = 0; i < N ; i++) {
			L[i] = Integer.parseInt(sc.next());
		}
		sc.close();

		//Logic
		int answer = 1;
		int D = 0;

		for(int i = 0; i < N ; i++) {
			D = D + L[i];
			if(D <= X) {
				answer += 1;
			}else {
				break;
			}
		}

		//output
		System.out.print(answer);
	}

}


Measured memory_bytes: 21716
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    #0からi番目までの値の和を求める
    def acc(self, i):
        i += 1
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s
        
def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx

def judge(x):
    l = []
    
    for ai in a:
        if ai>=x:
            l.append(1)
        else:
            l.append(-1)
    
    acc = [0]*(N+1)
    
    for i in range(N):
        acc[i+1] = acc[i]+l[i]
    
    idx = compress(acc)
    bit = BIT(len(idx.keys()))
    cnt = 0
    
    for i in range(N+1):
        cnt += bit.acc(idx[acc[i]])
        bit.add(idx[acc[i]], 1)

    return cnt>=(N*(N+1)//2+1)//2
    
def binary_search():
    l, r = 0, max(a)
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
a = list(map(int, input().split()))
print(binary_search())

Measured memory_bytes: 127132
// finish date: 2019/2/22

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N;
    cin >> N;
    vd p(N);
    rep(i, N) cin >> p[i];
    vvd dp(N, vd(N + 1, 0));
    dp[0][0] = 1 - p[0];
    dp[0][1] = p[0];
    FOR(i, 1, N) {
        rep(j, N) {
            dp[i][j] += dp[i - 1][j] * (1 - p[i]);
            dp[i][j + 1] += dp[i - 1][j] * p[i];
        }
    }
    double ans = 0;
    FOR(i, N / 2 + 1, N + 1) {
        ans += dp[N - 1][i];
    }
    printf("%.10lf", ans);

    return 0;
}

Measured memory_bytes: 70656
import sys
sys.setrecursionlimit(1000000)

n, m = map(int,input().split())

a = [[] for _ in range(n)]

for _ in range(m):
    l, r, d = map(int,input().split())
    a[l-1].append((r-1,d))
    a[r-1].append((l-1,-d))

x = [None for _ in range(n)]

def check(y):
    for z,d in a[y]:
        if x[z] is None:
            x[z] = x[y] + d
            if not check(z):
                return False
        elif x[z] != x[y] + d:
            return False
    return True

for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not check(i):
            print('No')
            exit(0)
print('Yes')

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

using ll = long long;
const ll MAX = 1e18;
int main()
{
    int n;
    cin >> n;
    ll a[n];
    ll val = 1;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] == 0) {
            cout << "0";
            return 0;
        }
    }
    for(int i = 0; i < n; i++) {
        ll x = a[i];
        //if((MAX/val < x) || ((MAX/val == x) && (MAX%val != 0))) {
        if(MAX/val < x) {
            cout << "-1" << endl;
            return 0;
        }
        val *= x;
    }
    cout << val;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>

int main(){
  int N; cin>>N;
  string board[2]; CINA(board,2);
  ll ans = 1;
  char mode = 'x';
  REP(i,N){
    if(board[0][i]==board[1][i]){
      if(mode=='x'){
        ans *= 3;
      }else if(mode=='t'){
        ans *= 2; 
      }else{
        ans *= 1;
      }
      ans %= MOD;
      mode = 't';
    }else{
      if(mode=='x'){
        ans *= 6; //3P2 
      }else if(mode=='t'){
        ans *= 2;
      }else{
        ans *= 3;
      }
      ans %= MOD;
      mode = 'y';
      ++i;
    }
  }
  cout << ans << "\n";
  
}

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

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

  vector<long> d1(N);
  vector<long> d2(N);

  for(int i=0;i<N;i++){
    cin>>d1[i]>>d2[i];
    }
    long ans=0;
for(int i=0;i<N-2;i++){
  if(d1[i]==d2[i]&&d1[i+1]==d2[i+1]&&d1[i+2]==d2[i+2]){
    cout<<"Yes"<<endl;
    return 0;
  }
}

cout<<"No"<<endl;
}


Measured memory_bytes: 3608
#include <iostream>
#include <map>
using namespace std;
#define X first
#define Y second
int main(){
	int n,N,d;
	while(cin >> N && N){
		map<int,pair<int,int> >coord;
		int x1=(1<<21),x2=0,y1=(1<<21),y2=0;
		
		for(int i=0;i<N;i++){
			if(i){
				cin >> n >> d;
				switch(d){
				case 0:
					coord[i].X = coord[n].X-1;
					coord[i].Y = coord[n].Y  ;
					break;
				case 1:
					coord[i].X = coord[n].X;
					coord[i].Y = coord[n].Y+1;
					break;
				case 2:
					coord[i].X = coord[n].X+1;
					coord[i].Y = coord[n].Y;
					break;
				case 3:
					coord[i].X = coord[n].X;
					coord[i].Y = coord[n].Y-1;
					break;
				}
			}else{
				coord[0].X = coord[0].Y = 0;
			}
			x1 = min(x1,coord[i].X);
			x2 = max(x2,coord[i].X);
			y1 = min(y1,coord[i].Y);
			y2 = max(y2,coord[i].Y);
		}
		cout << x2-x1+1 << " " << y2-y1+1 << endl;
	}
}

Measured memory_bytes: 0
using System;
using System.Linq;

namespace testes
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] d = new int[N];
            for(int i = 0; i < N; i++) d[i] = int.Parse(str[i]);
            int ans = 0;
            int count = 0;
            
            for(int i = 0; i < N; i++)
            {
                count++;
                for(int j = count; j < N; j++)
                {
                    ans += d[i] * d[j];
                }
            }

            Console.WriteLine(ans);

           
        }

        static bool AAABBB(long target, long N,long K, long[] F, long[] A)
        {
            long count = 0, need;
            for (long i = 0; i < N; i++)
            {
                need = target / F[i];
                count += Math.Max(0, A[i] - need);
            }
            return count <= K;
        }
        public static long LIS(long[] c)
        {
            // 部分数列和
            long count = 1;
            long N = c.Length;
            long[] array = new long[N];
            array[0] = c[0];

            for (long i = 1; i < N; i++)
            {
                //for (long p = 0; p < N; p++) Console.Write($"{array[p]},");
                // Console.WriteLine("");
                if (array[count - 1] < c[i])
                {
                    array[count] = c[i];
                    count++;
                    continue;
                }
                for (long j = count - 2; j >= 0; j--)
                {
                    if (array[j] < c[i])
                    {
                        array[j + 1] = c[i];
                        break;
                    }
                }
                if(array[0] > c[i])array[0] = c[i];
            }
            return count;
        }
        public static void Rotation(char[] array, long l, long r)
        {          
        }      
    }   
}

/*
long a, b, c;
a = long.Parse(Console.ReadLine()); //標準入力
string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
b = long.Parse(str[0]);  //数値で受け取りたい場合は変換する
c = long.Parse(str[1]);
string S = Console.ReadLine();
char[] C = new char[N];
C = S.ToCharArray();
Console.Write("改行なし a = {0} b = {1} c = {2}", a, b, c)//改行なし出力
Console.WriteLine("改行あり a = {0} b = {1} c = {2}", a, b, c);//改行付き出力
Member = ReadLine().Split(' ').Select(long.Parse).ToArray();

string[] str = Console.ReadLine().Split(' ');
long[] a = new long[N];
for(long i = 0; i < N; i++) a[i] = long.Parse(str[i]);
 */


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

int main()
{
    int weight[6] = {2,3,5,10,12,15};
    int price[6] = {380,550,850,1520,1870,2244};
    int dp[52];
    int a=0;
    for(int i=0;i<52;i++){
        dp[i] = 1000000000;
    }
    dp[0] = 0;

    for(int i=0;i<52;i++){
        for(int j=0;j<6;j++){
            if(i-weight[j] >= 0)
                dp[i] = min(dp[i],dp[i-weight[j]]+price[j]);
        }
    }
    int n;
    while(cin >> n){
        if(n==0)
            break;
        cout << dp[n/100] << endl;
    }
    return 0;
}
        

Measured memory_bytes: 1160