akhauriyash/Code-Regression huggingface dataset:
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n;
double p[100];
vector<int> g[100];
vector<int> rg[100];
bool vis[100];
vector<int> ord;
int c[100];
double d[100];
vector<int> gg[100];
int in[100];

void dfs(int v){
  vis[v] = true;
  each(u, g[v]) if (!vis[u]) dfs(u);
  ord.push_back(v);
}

void dfs(int v, int ii){
  vis[v] = true;
  c[v] = ii;
  each(u, rg[v]) if (!vis[u]) dfs(u, ii);
}

int main(){
  while (cin >> n, n){
    rep(i, 100) g[i].clear();
    rep(i, 100) rg[i].clear();
    memset(vis, 0, sizeof(vis));
    ord.clear();
    rep(i, 100) gg[i].clear();
    memset(in, 0, sizeof(in));

    rep(i, n){
      int m;
      cin >> p[i] >> m;
      //p[i] = 1.0 - p[i];
      g[i].resize(m);
      each(x, g[i]){
        cin >> x, x--;
        rg[x].push_back(i);
      }
    }
    rep(i, n) if (!vis[i]) dfs(i);
    reverse(all(ord));
    memset(vis, 0, sizeof(vis));
    int ii = 0;
    each(i, ord) if (!vis[i]) dfs(i, ii++);
    rep(i, ii) d[i] = 1.0;
    rep(i, n){
      d[c[i]] *= p[i];
      each(j, g[i]) if (c[i] != c[j]) gg[c[i]].push_back(c[j]);
    }
    rep(i, ii){
      sort(all(gg[i]));
      gg[i].erase(unique(all(gg[i])), end(gg[i]));
    }
    /*
    double res = 1.0;
    rep(i, ii){
      cout << i << ": ";
      each(j, gg[i]) cout << j << " ", d[j] *= d[i];
      cout << endl;
      if (gg[i].empty()) res *= d[i];
    }
    cout << 1.0 - res << endl;
    */
    rep(i, ii) each(j, gg[i]) in[j]++;
    double res = 1.0;
    rep(i, ii) if (in[i] == 0) res *= 1.0 - d[i];
    cout << res << endl;
  }
}

Measured memory_bytes: 3344
import java.util.Scanner;

public class Main {

	public static void main(String args[]) throws Exception {

		int N = 0;
		int K = 0;
		int X;
		int lOCATION[] = null;
		int ans = (int) (2 * Math.pow(10, 15));

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();

		if (N >= 1 && N <= (int) Math.pow(10, 5)) {
			lOCATION = new int[N];
			K = sc.nextInt();
			sc.nextLine();
			if (K >= 1 && K <= N) {
				for (int i = 0; i <= N - 1; i++) {
					X = sc.nextInt();
					if (Math.abs(X) >= 1 && Math.abs(X) <= Math.pow(10, 8)) {
						lOCATION[i] = X;

					}

				}

			}

		}
		for (int i = 0; i + K - 1 <= N - 1; i++) {
			int l = i;
			int r = i + K - 1;
			ans = Math.min(ans, lOCATION[r] - lOCATION[l] + Math.min(Math.abs(lOCATION[l]), Math.abs(lOCATION[r])));
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 52728
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    vector<ll> A(9);
    for(int i = 0; i < 9; ++i){
        cin >> A[i];
    }
    ll N; cin >> N;
    vector<ll> used(9);
    for(int i = 0; i < N; ++i){
        ll B; cin >> B;
        for (int j = 0; j < 9; ++j) {
            if(B == A[j]){
                used[j] = true;
            }
        }
    }
    bool f = false;
    if(used[0] == true && used[1] == true && used[2] == true) f = true;
    if(used[3] == true && used[4] == true && used[5] == true) f = true;
    if(used[6] == true && used[7] == true && used[8] == true) f = true;
    if(used[0] == true && used[3] == true && used[6] == true) f = true;
    if(used[1] == true && used[4] == true && used[7] == true) f = true;
    if(used[2] == true && used[5] == true && used[8] == true) f = true;
    if(used[0] == true && used[4] == true && used[8] == true) f = true;
    if(used[2] == true && used[4] == true && used[6] == true) f = true;
    string ans = "No";
    if(f) ans = "Yes";
    cout << ans << endl;

}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt", "input5.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


Measured memory_bytes: 256
//ABC086C
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	int n;
	cin >> n;
	int t = 0, x = 0, y = 0;
	int flag = 1;
	for(int i=0;i<n;i++){
		int a, b, c;
		cin >> a >> b >> c;
		if(abs(t-a)-abs(x-b)-abs(y-c) >= 0 && (abs(t-a)-abs(x-b)-abs(y-c))%2 == 0){
			t = a;
			x = b;
			y = c;
		}else{
			flag = 0;
		}
	}
	if(flag == 1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	string s0 = "YAKI";
	bool flag = true;
	if (s.length() < 4)
		flag = false;
	for (int i = 0; i < 4; i++)
		if (s[i] == s0[i])
			continue;
		else
			flag = false;
	if (flag)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	//cin >> s;
}

Measured memory_bytes: 256
// C++ Program to find n'th fibonacci Number in 
// with O(Log n) arithmatic operations 
#include <bits/stdc++.h> 
using namespace std; 
typedef long long ll;
  
const int MAX = 1000; 

int f[MAX] = {0}; 
  

ll fib(ll n) { 
    if (n == 0) return 0; 
    if (n == 1 || n == 2) return (f[n] = 1); 

    if (f[n]) return f[n]; 
    int k = (n & 1)? (n+1)/2 : n/2; 
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) : (2*fib(k-1) + fib(k))*fib(k); 
    return f[n]; 
} 
  
/* Driver program to test above function */
int main() { 
    ll n; cin >> n; 
    cout << fib(n+1) << endl;
    return 0; 
} 


Measured memory_bytes: 3120
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int K;
int vis[1000000];
int main(){
  int res = 1;
  int cur;
  rd(K);
  cur = 7 % K;
  while(cur){
    if(vis[cur]){
      wt_L(-1);
      wt_L('\n');
      return 0;
    }
    vis[cur] = 1;
    res++;
    cur = (cur * 10 + 7) % K;
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// int K;
// int vis[1d6];
// {
//   int res = 1, cur;
//   rd(K);
//   cur = 7 % K;
//   while(cur){
//     if(vis[cur]) wt(-1), return 0;
//     vis[cur] = 1;
//     res++;
//     cur = (cur * 10 + 7) % K;
//   }
//   wt(res);
// }


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

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* [💭] [💡] [🎈] */

using namespace std;

const ll mod = 998'244'353;
ll dp[3001][3001];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    dp[a][b] = 1;
    for (int i = a; i <= c; i++) {
        for (int j = b; j <= d; j++) {
            if (i == a && j == b) continue;
            dp[i][j] = dp[i - 1][j] * j + dp[i][j - 1] * i - ((dp[i - 1][j - 1] * (i - 1) % mod) * (j - 1));
            dp[i][j] %= mod;
            dp[i][j] += mod;
            dp[i][j] %= mod;
        }
    }

    cout << dp[c][d];

    return 0;
}

Measured memory_bytes: 73808
<?php

//----------------------------------------------------------------------------------
// Input
//----------------------------------------------------------------------------------

$sc = new Scanner();
$n = $sc->nextInt();

$a = array();
for ($i = 0; $i < $n; $i++) {
  $a[] = $sc->nextInt();
}

//----------------------------------------------------------------------------------
// Input for test
//----------------------------------------------------------------------------------
/*
$n = 3;
$a = array(16, 16, 16);
*/
//----------------------------------------------------------------------------------
// Main
//----------------------------------------------------------------------------------

$ans = 0;
while (1) {
  for ($i = 0; $i < count($a); $i++) {
    if ($a[$i] % 2 == 1) { break 2; }
    $a[$i] /= 2;
//echo $a[$i]."\n";
  }
  $ans++;
}


//----------------------------------------------------------------------------------
// Output
//----------------------------------------------------------------------------------
out::println($ans);



//----------------------------------------------------------------------------------
// Ref: https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
//----------------------------------------------------------------------------------
class Scanner {
  private $arr = array();
  private $count = 0;
  private $pointer = 0;
  public function next() {
    if($this->pointer >= $this->count) {
      $str = trim(fgets(STDIN));
      $this->arr = explode(' ', $str);
      $this->count = count($this->arr);
      $this->pointer = 0;
    }
    $result = $this->arr[$this->pointer];
    $this->pointer++;
    return $result;
  }
  public function hasNext() {
    return $this->pointer < $this->count;
  }
  public function nextInt() {
    return (int)$this->next();
  }
  public function nextDouble() {
    return (double)$this->next();
  }
}

class out {
  public static function println($str = "") {
    echo $str . PHP_EOL;
  }
}

?>


Measured memory_bytes: 3700
#include <stdio.h>
int main() {
  long long n;
  long long hasil =1;
  scanf("%lld",&n);
  long long in[n];
  for(int i=0; i<n;i++){
  	scanf("%lld",&in[i]);
  }
  for(int i=0; i<n;i++){
  	if(in[i] == 0){
  		printf("0\n");
  		return 0;
	  }
  }
  for(int i=0; i<n;i++){
  	if(in[i] <= 1000000000000000000/hasil){
  		hasil *=in[i];
	  }
	  else{
	  	printf("-1\n");
	  	return 0;
	  }
  }
  printf("%lld\n",hasil);
  return 0;
}

Measured memory_bytes: 2932
import java.util.*;
import java.lang.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        String t = sc.next();
        String result = new String();
        for(int i = 0;i<s.length();i++){
            result = result.concat(String.valueOf(s.charAt(i)));
            result = result.concat(String.valueOf(t.charAt(i)));
        }
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 100000000000000

/*方針*/
/*x->yへのkを通る最短距離=(k->xの最短距離)+(k->yの最短距離)である*/

//➀それぞれの辺の間の距離をdistに記憶
//➁bfsで頂点kからのそれぞれの頂点に対する最短距離を求める
//➂q個のquestionに対して     (k->xのmin)+(k->yのmin)を足して出力


int main(){
	ll n;cin>>n;//頂点数
	map<pair<int,int>,int> dist;//頂点間距離
	vector<vector<int>> G(n);//隣接行列

/*➀*/	for(int i=0;i<n-1;i++){//辺と距離について
		ll a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
		dist[make_pair(a,b)]=dist[make_pair(b,a)]=c;
		dist[make_pair(i,i)]=0;
	}

	ll q,k;cin>>q>>k;//頂点kを必ず経由
	k--;

	queue<ll> que;
	que.push(k);//kから各頂点への最短距離を知りたい

	vector<bool> visit(n,false);
	vector<ll> distance_from_k(n,0);
	visit[k]=true;

/*➁*/	while(que.size()!=0){
		ll now=que.front();
		que.pop();
		visit[now]=true;

		for(auto next:G[now]){
			if(visit[next]) continue;
			
			distance_from_k[next]=distance_from_k[now]+dist[make_pair(now,next)];
			que.push(next);
		}
	}
	
	vector<pair<int,int>> want(q);//この頂点間最短距離を求める 
	for(int i=0;i<q;i++){
		ll x,y;cin>>x>>y;
		x--;y--;
		want[i]=make_pair(x,y);
	}

/*➂*/	for(int i=0;i<q;i++){
		cout<<distance_from_k[want[i].first]+distance_from_k[want[i].second]<<endl;
	}

	return 0;
}

Measured memory_bytes: 30308
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int n,f[111][22],p[111][22],ans=-1e9;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<10;j++)
		{
			cin>>f[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=10;j++)
		{
			cin>>p[i][j];
		}
	}
	for(int i=1;i<(1<<10);i++)
	{
		int a[22],now=i,cnt=0;
		for(int j=0;j<10;j++)
		{
			a[j]=(now%2);
			now/=2;
		}
		for(int j=0;j<n;j++)
		{
			int c=0;
			for(int k=0;k<10;k++)
			{
				if(a[k]==f[j][k])
				{
					c+=a[k];
				}
			}
			cnt+=p[j][c];
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
class diceClass:
	def __init__(self, valuelist):
		# [t, s, e, w, n, b]
		self.valuelist = valuelist
		self.t = valuelist[0]
		self.s = valuelist[1]
		self.e = valuelist[2]
		self.w = valuelist[3]
		self.n = valuelist[4]
		self.b = valuelist[5]

	def print(self):
		print('t={0}, s={1}, e={2}, w={3}, n={4}, b={5}'.format(self.t, self.s, self.e, self.w, self.n, self.b))

	def throw(self, direction):
		# N,S,W,E
		if direction == 'North':
			self.t, self.s, self.b, self.n = self.s, self.b, self.n, self.t
		elif direction == 'South':
			self.t, self.s, self.b, self.n = self.n, self.t, self.s, self.b
		elif direction == 'West':
			self.t, self.e, self.b, self.w = self.e, self.b, self.w, self.t
		elif direction == 'East':
			self.t, self.e, self.b, self.w = self.w, self.t, self.e, self.b
		elif direction == 'Right':
			self.s, self.e, self.w, self.n = self.e, self.n, self.s, self.w
		elif direction == 'Left':
			self.s, self.e, self.w, self.n = self.w, self.s, self.n, self.e


while True:
	n = int(input())
	if n == 0:
		break
	A = [1, 2, 3, 4, 5, 6]
	dice = diceClass(A)
	tsum = dice.t
	for i in range(n):
		s = input().strip()
		dice.throw(s)
		tsum = tsum + dice.t
	print(tsum)



Measured memory_bytes: 5628
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,k;cin>>n>>k;
    vector <int >v;
    for(int i=0;i<n;i++)
    {
        int l;cin>>l;
        
        v.push_back(l);
    }
    
    sort(v.begin(),v.end(),greater<int >());
    long long int sum=0;
    for(int i=0;i<k;i++)
    {
        sum+=v[i];
    }
    cout << sum;
    return 0;
    
}


Measured memory_bytes: 256
//“Failure is unimportant. It takes courage to make a fool of yourself.”
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
#define int long long int
#define P 1000000007
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 1000
#define PI 3.14159265359
#define inf LLONG_MAX
using namespace __gnu_pbds;
using namespace std;


signed main() {
    teevra_gati

    
    string s,t;
    cin>>s>>t;
    ll n = lt(s), m = lt(t);;
    vvl dp(n+1, vl(m+1,0));
    f(i,1,n+1){
        f(j,1,m+1){
            if(s[i-1]==t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    string ans = "";

    ll i=n, j=m;
    while(i>0 && j>0){
        if(dp[i][j]==dp[i-1][j]) i--;
        else if(dp[i][j]==dp[i][j-1]) j--;
        else{
            ans += s[i-1];
            i--;
            j--;
        }
    }
    reverse(all(ans));
    cout<<ans;
    return 0;
}


Measured memory_bytes: 70784
#include<iostream>
#include<vector>
#include<math.h>
#include<stdio.h>
using namespace std;
#define inf 1<<21
struct cell{
  double x,y,z,r;
};
double dis(cell a,cell b){
  double o=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-(a.r+b.r);
  if(o<=0) return 0;
  return o;
}
int main(){
  int n;
  cin >> n;
  while(n!=0){
    int i,j,k;
    vector<cell> cells;
    cell c;
    for(i=0;i<n;i++){
      cin >> c.x >> c.y >> c.z >> c.r;
      cells.push_back(c);
    }
    
    double cost[100][100]={{}};
    for(i=0;i<n;i++){
      for(j=i;j<n;j++){
	if(i==j) cost[i][j]=inf;
	else{
	  cost[i][j]=dis(cells[i],cells[j]);
	  cost[j][i]=cost[i][j];
	}
      }
    }
    
    int color[100]={},p[100]={};
    double d[100]={};
    for(i=0;i<n;i++){
      color[i]=0;
      d[i]=inf;
      p[i]=-1;
    }
    double sum=0,minv;
    int u;
    d[0]=0;
    while(1){
      minv=inf;
      u=-1;
      for(i=0;i<n;i++){
	if(minv>d[i]&&color[i]!=2){
	  u=i;
	  minv=d[i];
	}
      }
      if(u==-1) break;
      color[u]=2;
      for(i=0;i<n;i++){
	if(color[i]!=2&&u!=i){
	  if(d[i]>cost[u][i]){
	    d[i]=cost[u][i];
	    p[i]=u;
	    color[i]=1;
	  }
	}
      }
      
    }
    for(i=0;i<n;i++){
      if(p[i]!=-1) sum+=cost[i][p[i]];
    }
    
    printf("%.3f\n",sum);
    
    cin >> n;
  }
  return 0;
}

Measured memory_bytes: 1360
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int NMAX = 3010;
double dp[2][NMAX];

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

    cin >> n;

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        double * act = dp[i & 1];
        double * prv = dp[(i & 1) ^ 1];
        fill(act, act + n + 1, 0);

        double p;
        cin >> p;

        for (int i = 0; i <= n; i++)
            act[i] += (1 - p) * prv[i], act[i + 1] += p * prv[i];
    }

    double s = 0;
    for (int i = (n + 1) / 2; i <= n; i++)
        s += dp[n & 1][i];

    cout << setprecision(9) << fixed;
    cout << s << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>

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

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


int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];

    ll ans = 0;
    rep(i, n-1) {
        ans += min(ll(b), (x[i+1] - x[i]) * ll(a));
    }

    cout << ans << endl;



    return 0;

}


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

int main() {
  int S;
  cin >> S;
  int P, L;
  P = S / 100;
  L = S % 100;
  if (P >= 1 && P <= 12) {
    if (L >= 1 && L <= 12) {
      cout << "AMBIGUOUS" << endl;
    }
    else {
      cout << "MMYY" << endl;
    }
  }
  else {
    if (L >= 1 && L <= 12) {
      cout << "YYMM" << endl;
    }
    else {
      cout << "NA" << endl;
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>
#include <chrono>
#include <set>


#define rep(i,p,q) for(ll i = p;i < q;i++)
#define ll long long

using namespace std;

vector<vector<ll>> graph;
vector<ll> query;
vector<ll> ans;
vector<ll> visited;


const long long MAX_N = 1 << 17;

long long dat[2 * MAX_N - 1];

ll ecd(ll a, ll b) {
	if (a < b) swap(a, b);
	if (b == 0) return a;
	else {
		return ecd(b, a % b);
	}
}

//142 D
int main(void) {
	ll a, b;
	cin >> a >> b;
	map<ll,ll> mp, mpData = map<ll,ll>();
	ll c = ecd(a, b);
	
	rep(i, 1, sqrt(c) + 1) {
		if (c % i == 0) {
			mp[i] += 1;
			mp[c / i] += 1;
			mpData[i] += 1;
			mpData[c / i] += 1;
		}
	}

	ll ans = 1;
	for (const auto& v : mpData) {
		ll key = v.first;
		if (mp.count(key) > 0 && key > 1) {
			vector<ll> del = vector<ll>();
			for(const auto& j : mp){
				if (j.first % key == 0) {
					del.push_back(j.first);
				}
			}
			rep(i, 0, del.size()) {
				mp.erase(del[i]);
			}
			ans++;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 1152
N, x = map(int, input().split())
a = list(map(int, input().split()))

pos = a.index(min(a))
na = [a[pos]] + a[pos+1:] + a[:pos]

ans = sum(a)
old_b = na[:]
for k in range(1, N):
    b = []
    for i in range(N):
        if i - k >= 0:
            b.append(min(old_b[i], na[i - k]))
        else:
            b.append(old_b[i])
    # print(k, b)
    old_b = b
    ans = min(ans, k * x + sum(b))
print(ans)


Measured memory_bytes: 3316
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> _P;
typedef pair<_P,int> P;
char map[1000][1001];
bool vst[1000][1000];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int H,W,N,x,y;
int bfs(char ch) {
	memset(vst,0,sizeof(vst));
	queue<P> Q;
	Q.push(P(_P(x,y),0));
	vst[x][y]=true;
	while(!Q.empty()) {
		P p=Q.front(); Q.pop();
		if(map[p.first.second][p.first.first]==ch) {x=p.first.first; y=p.first.second;return p.second;}
		for(int i=0;i<4;i++) {
			int nx=p.first.first+dx[i],ny=p.first.second+dy[i];
			if(0>nx||nx>=W||0>ny||ny>=H) continue;
			if(vst[nx][ny]) continue;
			if(map[ny][nx]=='X') continue;
			Q.push(P(_P(nx,ny),p.second+1));
			vst[nx][ny]=true;
		}
	}
}
int main() {
	scanf("%d %d %d",&H,&W,&N);
	for(int i=0;i<H;i++) {
		scanf("%s",map[i]);
		for(int j=0;j<W;j++)
			if(map[i][j]=='S') x=j,y=i;
	}
	int sum=0;
	for(int i=1;i<=N;i++)
		sum+=bfs(i+'0');
	printf("%d\n",sum);
}

Measured memory_bytes: 3008
S = input()
odd ={"R","U","D"}
even = {"L","U","D"}
l = len(S)
S_odd = {S[i] for i in range(l) if i%2==0}
S_even = {S[i] for i in range(l) if i%2==1}

if S_odd <= odd and S_even <= even:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define call(var) cout<<#var<<"="<<var<<endl;
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

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

int main(){
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    bool ok = true;
    rep(i,h){
        rep(j,w) if(s[i][j]=='#'){
            bool yes = false;
            rep(k,4){
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(ni<0 || ni>=h || nj<0 || nj>=w) continue;
                if(s[ni][nj]=='#') yes = true;
            }
            ok &= yes;
        }
    }
    cout << (ok? "Yes":"No") << endl;
}

Measured memory_bytes: 256
import sys
from collections import defaultdict, deque
n = int(sys.stdin.readline().split()[0])
A = defaultdict(deque)
ans = []
for query in sys.stdin:
    if query[0] == '0':
        t, x = query[2:].split()
        A[t].append(x)
    elif query[0] == '1':
        if A[query[2:-1]]:
            ans.append(A[query[2:-1]][0] + '\n')
    else:
        if A[query[2:-1]]:
            A[query[2:-1]].popleft()
sys.stdout.writelines(ans)


Measured memory_bytes: 20128
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
int main(){
  int a,b;
  cin >> a >> b;
  for(int i = 1; i <= 10000; i++){
    if((i * 8) / 100 == a && i / 10 == b){
      cout << i << endl;
      break;
    }
    if(i == 10000){
      cout << -1 << endl;
    }
  }
}
  

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

int gcd(int a,int b){
  return b ? gcd(b,a%b) : a;
}

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int g=gcd(a,b);
  if(c%g==0){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

ll modpow(ll a, ll b){
    if(b == 0) return 1;
    else if(b % 2 == 0){
        ll d = modpow(a, b / 2) % MOD;
        return (d * d) % MOD;
    }
    else{
        return (a * modpow(a, b - 1)) % MOD;
    }
}

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

    int n, k; cin>>n>>k;

    vector<ll> cnt(k+1, 0);
    for(int i=k; i>=1; i--){
        ll cur = modpow(k / i, n);
        for(int j=2*i; j<=k; j+=i){
            cur -= cnt[j];
            cur += MOD;
            cur %= MOD;
        }
        cnt[i] = cur;
    }

    ll ans = 0;
    for(int i=1; i<=k; i++){
        ans += cnt[i] * i;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; }}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; }}

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

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    combination C(101);

    cout << C(M, 2)  + C(N, 2) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define S 1000001
#define N 30

int dp[S] = {0}; // dp[i] := 商品の金額和がSとなるか 

int main(void) {
	int isprime[S];
	int i,j;
	for(i = 0; i < S; i++) isprime[i] = 1;
	
	isprime[2] = 1;
	for(i = 2; i < S; i++) {
		if (isprime[i]) {
			for(j = i + i; j < S; j += i) {
				isprime[j] = 0;
			}
		}
	}
	while(1) {
		int n, x;
		int prices[N];
		scanf("%d %d", &n, &x);	
		if (n == 0) break;
		for(i = 0; i < n; i++) {
			scanf("%d", &prices[i]);
		}
	
		for(i = 0; i < S; i++) {
			dp[i] = 0;
		}
		
		dp[0] = 1;
		for(i = 0; i <= x; i++) {
			if (dp[i]) {
				for(j = 0; j < n; j++) {
					if (i + prices[j] <= x) {
						dp[i + prices[j]] = 1;	
					}
				}
			}
		}
		
		int ans = 0;
		for(i = x; i >= 0; i--) {
			if (dp[i] && isprime[i]) {
				ans = i;
				break;
			}
		}
		if (ans) {
			printf("%d\n", ans);
		} else {
			printf("NA\n");
		}
		
	}
	
	return 0;
}

Measured memory_bytes: 8424
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


int main(){
  
  int h,w,K;
  cin >> h >> w >> K;
  vector<vector<ll>> val(h+1,vector<ll> (w+1,0));
  rep(i,K){
    int r,c,v;
    cin >> r >> c >> v;
    val[r][c] = v;
  }
  vector<vector<vector<ll>>> dp(h+1,vector<vector<ll>>(w+1,vector<ll>(4,0)));
  rep(i,h+1)rep(j,w+1)rep(k,4){
    if(i+1 <= h){
      dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][k]);
      dp[i+1][j][1] = max(dp[i+1][j][1],dp[i][j][k]+val[i+1][j]);
    }
    if(j+1 <= w){
      dp[i][j+1][k] = max(dp[i][j+1][k],dp[i][j][k]);
      if(k == 3)continue;
      dp[i][j+1][k+1] = max(dp[i][j+1][k+1],dp[i][j][k]+val[i][j+1]);
    }
  }
  ll res = 0;
  rep(i,4)res = max(res,dp[h][w][i]);
  cout << res << "\n";
  


  return 0;
}

Measured memory_bytes: 707260
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define mrep(i,from,n) for(int i = from; i < n; i++)
#define mreps(i,from,n) for(int i = from; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
typedef long long ll;
typedef pair<ll, ll> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;
int INF = 1001001001;

void solve()
{
	int n; cin >> n;
	vector<int> t(n), x(n), y(n);
	rep(i, n) cin >> t[i] >> x[i] >> y[i];
	int t_now = 0,x_now = 0, y_now = 0;
	rep(i, n)
	{
		int dt =t[i]-t_now;
		int d = abs(x[i]-x_now) + abs(y[i]-y_now);
		if(dt >= d && d%2 == dt%2)
		{
			x_now = x[i];
			y_now = y[i];
			t_now = t[i];
		}
		else
		{
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
using namespace std;
int n,a,b,ans;
int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;++i)
	{
		int d=0,s=i;
		while(s)d+=s%10,s/=10;
		if(a<=d && d<=b) ans+=i;
	}
	cout<<ans<<endl;
	return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int x,y,num;
  cin >> x >> y;
  vector<int> A{1,3,5,7,8,10,12};
  vector<int> B{4,6,9,11};
  
  if(x == y && x == 2){
    cout << "Yes" << endl;
    return 0;
  }
  bool xa = false, ya = false;
  for(int i = 0; i < 6; i++){
    if(x == A.at(i)){
      xa = true;
    }
    if(y == A.at(i)){
      ya = true;
    }
  }
  if(xa && ya){
    cout << "Yes" << endl;
    return 0;
  }
    
    xa = false, ya = false;
  for(int i = 0; i < 4; i++){
    if(x == B.at(i)){
      xa = true;
    }
    if(y == B.at(i)){
      ya = true;
    }
  }
  if(xa && ya){
    cout << "Yes" << endl;
    return 0;
  }
  
  cout << "No" << endl;
}

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

int main() {
	string s; getline(cin, s);
	if (s == "1 0 0")puts("Close");
	if (s == "0 1 0")puts("Close");
	if (s == "1 1 0")puts("Open");
	if (s == "0 0 1")puts("Open");
	if (s == "0 0 0")puts("Close");
}

Measured memory_bytes: 3216
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;
#define INF (1 << 30)
#define size(x) (x?x->size:0)
#define nmin(x) (x?x->min:INF)

struct Node{
	int val, min, size;
	Node *l, *r;        
	Node(int x){
		val = x;
		min = x;
		size = 1;
		l = r = 0;	
	}	
};

Node *root = 0;
                    
typedef pair<Node*, Node*> P;
int vals[108000];
int p = 0;
void dfs(Node *a){
	if(a->l)dfs(a->l);
	vals[p++] = a->val;
	if(a->r)dfs(a->r);
}

void view(Node *a){
	p = 0;
	int s = size(a);
	dfs(a);
	for(int i = 0;i < p;i++){
		cout << vals[i] << " ";
	}cout << endl;
}

Node *update(Node *x){
	if(x == 0)return 0;
	x->min = min(x->val, min(nmin(x->l), nmin(x->r)));
	x->size = 1 + size(x->l) + size(x->r);
	return x;
}


Node *merge(Node *a, Node *b){
	if(a == 0)return b;
	if(b == 0)return a;
	int asize = size(a);
	int bsize = size(b);

	if(rand() % (asize + bsize) < asize){
		Node *tmp = merge(a->r, b);
		a->r = tmp;
		return update(a);
	}
	else{
		Node *tmp = merge(a, b->l);
		b->l = tmp;
		return update(b);
	}
}

P split(Node *a, int pos){
	if(pos == 0)return P(0, a);
	if(pos == size(a))return P(a, 0);
	int lsize = size(a->l);
	if(lsize < pos){
		P tmp = split(a->r, pos - lsize - 1);
		a->r = tmp.first;
		tmp.first = update(a);
		return tmp;
	}
	else{
		P tmp = split(a->l, pos);
		a->l = tmp.second;
		tmp.second = update(a);
		return tmp;
	}
}

Node *shift(Node *a, int l, int r){
	P tmp = split(a, r);
	P tmp2 = split(tmp.first, l);
	P tmp3 = split(tmp.second, 1);
	tmp2.first = merge(tmp2.first, tmp3.first);
	tmp.first = merge(tmp2.first, tmp2.second);
	return merge(tmp.first, tmp3.second);	
}

int minval(Node *a, int l, int r){
	P tmp = split(a, r + 1);
	P tmp2 = split(tmp.first, l);
	int res = nmin(tmp2.second);
	tmp.first = merge(tmp2.first, tmp2.second);
	root = merge(tmp.first, tmp.second);
	return res;
}

Node *setval(Node *a, int pos, int val){
	P tmp = split(a, pos);
	tmp.second = split(tmp.second, 1).second;
	tmp.second = merge(new Node(val), tmp.second);
	return merge(tmp.first , tmp.second);
}
	
int main(){
        int n, q, x, y, z;
	cin >> n >> q;
	for(int i = 0;i < n;i++){
		cin >> x;
		root = merge(root, new Node(x));
	}
	for(int i = 0;i < q;i++){
		cin >> x >> y >> z;
		int l = y, r = z;

		if(x == 0){
			root = shift(root, l, r);
		}
		if(x == 1){
			cout << minval(root, l, r) << endl;
		}
		if(x == 2){
			root = setval(root, y, z);
		}
	}
	return 0;
}

Measured memory_bytes: 13708
import java.util.*;
import java.util.Arrays;
import java.util.Set;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int W=sc.nextInt();
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=Math.abs(a-b);
        if(c>W){
            System.out.println(c-W);
        }else{
            System.out.println(0);
        }
}
        
        
    }


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

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

int main() {
    int n, x[100], sum = 0, ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
        sum += x[i];
        ans += x[i] * x[i];
    }
    int p = round(sum / (double)n);
    ans += -2 * p * sum + n * p * p;
    cout << ans << endl;

    return 0;
}

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

x = A[0]
for j, a in enumerate(A[1:]):
    if j%2==0:
      x -= a
    else:
      x += a
print(x)
for i in A[:-1]:
  x = 2*(i-x/2)
  print(int(x))

Measured memory_bytes: 14028
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		C_ExamAndWizard solver = new C_ExamAndWizard();
		solver.solve(1, in, out);
		out.close();
	}

	static class C_ExamAndWizard {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			Exam[] e = new Exam[n];
			for (int i = 0; i < n; i++) {
				e[i] = new Exam();
				e[i].a = in.nextInt();
			}
			for (int i = 0; i < n; i++) {
				e[i].b = in.nextInt();
				e[i].d = e[i].a - e[i].b;
			}

			Arrays.sort(e);
			int ans = 0;
			long need = 0;
			for (int i = 0; i < n; i++) {
				if (e[i].d < 0) {
					++ans;
					need -= e[i].d;
				}
			}
			for (int i = n - 1; i >= 0; i--) {
				if (e[i].d > 0 && need > 0) {
					++ans;
					need -= e[i].d;
				}
			}
			out.println(need > 0 ? -1 : ans);
		}

		class Exam implements Comparable<Exam> {
			int a;
			int b;
			int d;

			public int compareTo(Exam o) {
				if (d != o.d) {
					return d < o.d ? -1 : 1;
				}
				return 0;
			}

		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}



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

using namespace std;

#define inf 1e15
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
#define P pair<int, int>
#define PP pair<P, llong int>
struct data{
	int place;
	int cost;

	bool operator<(const data &ri) const{
		return cost < ri.cost;
	}
	bool operator>(const data &ri) const{
		return cost > ri.cost;
	}
};
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};

int n, m;
PP edge[2001];
llong int d[1001];

llong int belman(){
	fn(d, 1001, -inf);
	d[1] = 0;

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(d[edge[j].first.second] < d[edge[j].first.first] + edge[j].second){
				d[edge[j].first.second] = d[edge[j].first.first] + edge[j].second;
				if(i == n-1 && edge[j].first.second == n) return -1;
			}
		}
	}

	return d[n];
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		llong int a, b, c;
		cin >> a >> b >> c;
		edge[i] = PP(P(a,b),c);
	}

	llong int ans = belman();
	if(ans != -1) cout << ans << endl;
	else cout << "inf" << endl;

	return 0;
}

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

#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))

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

int main(){
int N; cin>>N;
if(N==0){
cout<<'1'<<endl;
}else{
cout<<'0'<<endl;
}

}

Measured memory_bytes: 3632
import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    K, X = sc.intarr()

    if 500*K >= X:
        print("Yes")
    else:
        print("No")


def dfs(N):
    global dp
    if N <= 0:
        return 1

    if dp[N] > -1:
        return dp[N]
    ans = 0
    for i in range(1, 7):
        ans += dfs(N-i)
    dp[N] = ans
    return ans


class Scan():

    def intarr(self):
        num_array = list(map(int, input().split()))
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


def gcd(a, b):  # 最大公約数
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):  # 最小公倍数
    return a * b // gcd(a, b)


main()


Measured memory_bytes: 3316
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

N = lines[0][0]
Inf = 10 ** 10

trade = []
for i in 1..N do
  trade.push(0)
end

price = lines[1].clone

money = 1000
for i in 1..N do
  if i != N and price[i-1] < price[i] then
    money = (money / price[i-1]) * price[i] + (money % price[i-1])
  end
end
  
puts money

Measured memory_bytes: 14352
A, B, C, X = (int(input()) for _ in range(4))
count = 0

for a in range(min(A, X // 500) + 1):
    leave500 = X - a * 500
    for b in range(min(B, leave500 // 100) + 1):
        leave100 = leave500 - b * 100
        if leave100 // 50 <= C and leave100 % 50 == 0:
            count += 1

print(count)


Measured memory_bytes: 3060
// sortして後ろからK個とって足す.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
  int n,k,ans=0; cin >> n >> k;
  vector<int> v;
  for(int i=0;i<n;i++){
    int l; cin >> l; v.push_back(l);
  }
  sort(v.begin(), v.end());
  for(int i=0;i<k;i++) ans += v[n-1-i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# B - 81
# https://atcoder.jp/contests/abc144/tasks/abc144_b

n = int(input())

result = 'No'
for i in range(1, 10):
    for j in range(1, 10):
        if i * j == n:
            result = 'Yes'
            break
    if result == 'Yes':
        break

print(result)


Measured memory_bytes: 9120
import java.util.Scanner;

public class Main {

	static long solve(int n, int[] a) {
		long sum = 0;
		for (int i = 1; i < n; i++) {
			if (a[i] < a[i - 1]) {
				int num = a[i - 1] - a[i];
				sum += num;
				a[i] += num;
			}
		}

		return sum;
	}

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

		int n = stdIn.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = stdIn.nextInt();
		}
		long result = solve(n, a);
		System.out.println(result);

		stdIn.close();
	}
}


Measured memory_bytes: 50068
#include "stdio.h"
int main() {
  long long int x1, x2, y1, y2, n1, n2, n3, n4, result;
  scanf("%lld %lld %lld %lld", &x1, &x2, &y1, &y2);
  n1=x1*y1;
  n2=x1*y2;
  n3=x2*y1;
  n4=x2*y2;
  //printf("%lld %lld %lld %lld\n", n1, n2, n3, n4);
  result=n1;
  if (n1<=n2 && n3<=n2 && n4<=n2) {
    //printf("DONE if1\n");
    result=n2;
  }
  else if (n1<=n3 && n2<=n3 && n4<=n3) {
    //printf("DONE if2\n");
    result=n3;
  }
  else if (n1<=n4 && n2<=n4 && n3<=n4) {
    //printf("DONE if3\n");
    result=n4;
  }
  printf("%lld\n", result);
  return 0;
}


Measured memory_bytes: 1732
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define MIN(a,b) ((a) < (b) ? (a) : (b))
struct node {
  int id;
  int cap;
  struct node *next;
};
struct node **list;
int **flow, *visit, *delta, *prev, *queue;
void Insert(int, int, int);
int Maxflow(int, int, int);
int main(void)
{
  int i, v, e, s, t, c, maxflow = 0;
  scanf("%d %d", &v, &e);
  list = (struct node**)malloc(sizeof(struct node*) * v);
  flow = (int**)malloc(sizeof(int*) * v);
  visit = (int*)malloc(sizeof(int) * v);
  delta = (int*)malloc(sizeof(int) * v);
  prev = (int*)malloc(sizeof(int) * v);
  queue = (int*)malloc(sizeof(int) * v);
  for (i = 0; i < v; i++) {
    list[i] = NULL;
    flow[i] = (int*)calloc(v, sizeof(int));
  }
  for (i = 0; i < e; i++) {
    scanf("%d %d %d", &s, &t, &c);
    Insert(s, t, c);
  }
  while (Maxflow(0, v - 1, v)) {
    int n = v - 1;
    do {
      flow[prev[n]][n] += delta[v-1];
      flow[n][prev[n]] -= delta[v-1];
      n = prev[n];
    } while(n);
    maxflow += delta[v-1];
  }
  printf("%d\n", maxflow);
  for (i = 0; i < v; i++) {
    free(list[i]);
    free(flow[i]);
  }
  free(list);
  free(flow);
  free(visit);
  free(delta);
  free(prev);
  free(queue);
}
void Insert(int a, int b, int c)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->cap = c;
  p->next = list[a];
  list[a] = p;
  p = (struct node*)malloc(sizeof(struct node));
  p->id = a;
  p->cap = 0;
  p->next = list[b];
  list[b] = p;
}
int Maxflow(int s, int t, int size)
{
  struct node *n;
  int i, reached = 0, head = 0, tail = 0;
  for (i = 0; i < size; i++) {
    visit[i] = 0;
    delta[i] = INT_MAX;
    prev[i] = -1;
  }
  visit[s] = 1;
  queue[tail++] = s;
  do {
    i = queue[head++];
    for (n = list[i]; n != NULL; n = n->next) {
      int v = n->id;
      if (!visit[v] && flow[i][v] < n->cap) {
        queue[tail++] = v;
        visit[v] = 1;
        prev[v] = i;
        delta[v] = MIN(delta[i], n->cap - flow[i][v]);
        if (v == t) reached = 1;
      }
    }
  } while (head != tail && !reached);
  return reached;
}


Measured memory_bytes: 2104