akhauriyash/Code-Regression huggingface dataset:
a = list(str(input()))
n = len(a)
#b_list = list(map(int,input().split()))
#print(" ".join(map(str,c_list)))
count = 0
for i in range(0,n,2):
    if a[i] != "R" and  a[i] != "U" and a[i] != "D":
        count = 1
for i in range(1,n,2):
    if a[i] != "L" and  a[i] != "U" and a[i] != "D":
        count = 1
if count == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

//蟻本写経版 O(N*(logN)^2)
struct SuffixArray{
    VI sa;
    int k;
    const string S;
    VI rank,tmp;
    int n;

    SuffixArray(const string &str) : S(str){
        sa.resize(S.size()+1);
        rank.resize(S.size()+1);
        tmp.resize(S.size()+1);
        n = S.size();
        construct_sa();
    }

    // (rank[i],rank[i+k]),(rank[j],rank[j+k])を比較
    bool compare_sa(int i, int j){
        if(rank[i] != rank[j]) return rank[i] < rank[j];

        int ri = i + k <= n ? rank[i+k] : -1;
        int rj = j + k <= n ? rank[j+k] : -1;
        return ri < rj;
    }

    void construct_sa(){
        int n = S.length();
        for(int i = 0; i <= n; i++){
            sa[i] = i;
            rank[i] = i < n ? S[i] : -1;
        }

        for(k = 1; k <= n; k *= 2){
            sort(sa.begin(),sa.end(),[this](int a, int b){
                return compare_sa(a,b);
            });

            tmp[sa[0]] = 0;
            for(int i = 1; i <= n; i++){
                tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1],sa[i]) ? 1 : 0);
            }
            for(int i = 0; i <= n; i++){
                rank[i] = tmp[i];
            }
        }
    }

    bool contain(string T){
        int l = 0, r = n;
        while(r-l > 1){
            int mid = (r+l) / 2;
            if(S.compare(sa[mid], T.length(), T) < 0) l = mid;
            else r = mid;
        }
        return S.compare(sa[r], T.length(), T) == 0;
    }
};



signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; int Q;
    cin >> S;
    SuffixArray sa(S);
    cin >> Q;
    while(Q--){
        string T;
        cin >> T;
        cout << sa.contain(T) << endl;

    }

}



Measured memory_bytes: 15808
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

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

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    int n;
    cin>>n;
    vll a(n);
    ll over =1e18+7;
    double result=1;
    bool zero=false;
    rep(i,0,n){
        cin>>a[i];
        if(a[i]==0)zero=true;
    }
    if(zero){
        cout<<0<<endl;
        return 0;
    }
    ll cnt=0;
    ll ans=1;
    rep(i,0,n){
        result*=a[i];
        ans*=a[i];
        while(result>=10){
            cnt++;
            result/=10;
        }
    }
    bool ok=false;
    if(ans<=1000000000000000000)
        if((cnt<18||(result==1.0&&cnt==18)))
            ok=true;
    if(ok)cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}




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


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


    cout << N*(N-1)/2 - N/2 << endl;
    if( N % 2 == 0 ){
        for( int i = 1; i <= N; ++i ){
            for( int j = 1; j < i; ++j ){
                if( j != N+1-i ) cout << i << " " << j << endl;
            }
        }
    }else{
        for( int i = 1; i <= N; ++i ){
            for( int j = 1; j < i; ++j ){
                if( j != N-i ) cout << i << " " << j << endl;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 384
import sys
from itertools import accumulate
import bisect
n, k = [int(i) for i in sys.stdin.readline().split()]
ls = []
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    ls.append([a, b])
ls.sort(key=lambda x:x[0])
a_ls, b_ls = zip(*ls)
res = [i for i in accumulate(b_ls)]
print(a_ls[bisect.bisect_left(res, k)])

Measured memory_bytes: 28328
import java.util.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		String[] sa = s.split("");
		String[] ta = t.split("");
		Arrays.sort(sa);
		Arrays.sort(ta,Comparator.reverseOrder());
		
		
		s = "";
		t = "";
		for(int i=0; i < sa.length; i++) {
			s = s + sa[i];
		}
		for(int i = 0; i< ta.length; i++) {
			t = t + ta[i];
		}
		String ans;
		if(s.compareTo(t) < 0) {
			ans = "Yes";
		}else {
			ans = "No";
		}
		
		System.out.print(ans);
	}
}

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

using namespace std;

typedef long long ll;

int main(){

	int N;
	cin >> N;
	int ts = 0;
	int xs = 0;
	int ys = 0;
	int te,xe,ye;
	string ans = "Yes";
	
	for (int i = 0; i < N; i++)
	{
		cin >> te >> xe >> ye;
		int dx = abs(xe-xs);
		int dy = abs(ye-ys);
		int dt = te -ts;
		if ((dt-dx-dy)%2 == 0 && dt >= dx+dy)
		{
			ts = te;
			xs = xe;
			ys = ye;
		}
		else{
			ans = "No";
			break;
		}
	}

	cout << ans << endl;

	return 0;	
}

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

int main(){
    int N,M,A,i;
    cin >> N >> M;
    for (i=0;i<M;i++){
        cin >> A;
        N -= A;

    }
    if (N<0){
        cout << -1;
    }
    else{
        cout << N;
    }
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
using Graph = vector<vector<int>>;
int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin>>s;
    int min_x=1005;
    rep(i,s.size()-2){
        min_x=min(min_x,abs(753-(s[i]-'0')*100-(s[i+1]-'0')*10-(s[i+2]-'0')));
    }
    cout<<min_x<<endl;

    return 0;
}

Measured memory_bytes: 3572
from sys import stdin
input = stdin.readline

MAX = 510000
MOD = 10**9 + 7

def MakeTable():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def COM(n, k):
    if n < k:
        return 0
    elif n < 0 or k < 0:
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

H, W, A, B = map(int, input().split())
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

N = min(H-A, W-B)
x, y = 0, 0
result = 0

MakeTable()

for _ in range(N):
    n1 = H-A-1+B+x-y
    n2 = A+W-1-B-x+y
    result += (COM(n1, B+x) * COM(n2, A+y)) % MOD
    x += 1
    y += 1

print(result%MOD)

Measured memory_bytes: 69580
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++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(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    ll n;
    cin >> n;
    VL a(n);
    REP(i,n){
        a[i] = in();
    }
    ll s = 0;
    REP(i,n){
        if (i % 2) s -= 2 * a[i];
        else s += 2 * a[i];
    }
    VL ans(n);
    ans[0] = s / 2;
    FOR(i,1,n-1){
        ans[i] = 2 * a[i - 1] - ans[i - 1];
    }
    REP(i,n) cout << ans[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 2944
#include <stdio.h>

int main(void) {
    int a, b, c, esc;
    esc = 0;
    scanf("%d %d %d", &a, &b, &c);
    int arr[] = {a, b, c};
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(arr[i] < arr[j]) {
                esc = arr[i];
                arr[i] = arr[j];
                arr[j] = esc;
            }
        }
    }
    printf("%d %d %d\n", arr[0], arr[1], arr[2]);
}


Measured memory_bytes: 2124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		while(true){
			int n = stdIn.nextInt();
			int k = stdIn.nextInt();
			if(n==0&&k==0){
				return;
			}
			int[] have = new int[k];
			for(int i=0;i<k;i++){
				have[i] = stdIn.nextInt();
			}
			boolean f = true;
			for(int i=0;i<n;i++){
				for(int j=0;j<k;j++){
					have[j] -= stdIn.nextInt();
					if(have[j]<0){
						f = false;
					}
				}
			}
			if(f){
				System.out.println("Yes");
			}
			else{
				System.out.println("No");
			}
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m,t,a;
    cin>>n>>m>>t;
    std::deque<int> baggage;
    for (int i=0;i<n;i++) {
        cin>>a;
        baggage.emplace_back(a);
    }
    int ans=0;
    int itr=0;
    int flag=0;
    int j=0;
    while (j<t) {
        if (flag==1) {
            if (itr==baggage.size()) {
                j+=m;
                flag=0;
                //cout<<j<<" "<<ans<<endl;
            } else if (j==baggage[itr]) {
                itr++;
            } else if (j+m*2>baggage[itr]) { 
                j++;
                //cout<<j<<" "<<ans<<endl;
            } else {
                j+=m;
                flag=0;
                //cout<<j<<" "<<ans<<endl;
            }
        } else {
            if (j+m==baggage[itr]) {
                j+=m;
                itr++;
                flag=1;
                //cout<<j<<" "<<ans<<endl;
            } else {
                j++;
                ans++;
                //cout<<j<<" "<<ans<<endl;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	int n, m, a[1000],count=0;
	cin >> n >> m;
	for (int i = 0; i < m * 2 ; i++)cin >> a[i];
	for (int i = 1; i <=n; i++) {
		for (int j = 0; j < m * 2 ; j++) {
			if (a[j] == i)count++;
		}
		cout << count << endl;
		count = 0;
	}
	int x;
	cin >> x;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i=0;i<n;i++)
#define REP1(i,n) for(long long i=1;i<=n;i++)
#define ITE(arr) for(auto ite=(arr).begin();ite!=(arr).end();ite++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
typedef long long ll;
typedef pair<int,int> pii;
//---------------------
#define MAXN
//---------------------
ll a,p;
int main(){
	cin>>a>>p;
	p+=a*3;
	cout<<(p>>1)<<endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
C = [0] * (N + 1)
for a in A:
    C[a] += 1
D = [0] * (N + 1)
for c in C:
    D[c] += 1
P = [0] * (N + 1)
Q = [0] * (N + 1)
for i in range(1, N+1):
    P[i] = P[i-1] + i * D[i]
    Q[i] = Q[i-1] + D[i]
F = [0] * (N + 1)
for i in range(1, N+1):
    F[i] = int((P[i] + i * (Q[N] - Q[i])) / i)
index = N
for i in range(1, N+1):
    while True:
        if index == 0:
            print(0)
            break
        if F[index] >= i:
            print(index)
            break
        else:
            index -= 1

Measured memory_bytes: 48312
class Unionfind:
  def __init__(self,n):
     self.Tree=[i for i in range(n)]

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
      
N,M=map(int,input().split())
Uf=Unionfind(N)
Flag=0
B=0
A=[]
Edge=[[int(i) for i in input().split()] for i in range(M)]
for m in range(M):
  Edge_copy=list(Edge)
  del Edge_copy[m]
  for e in Edge_copy:
    Uf.unite(e[0]-1,e[1]-1)
  for a in range(N):
    A.append(Uf.find(a))
  for n in range(N-1):
    if Uf.find(n)!=Uf.find(n+1):
      Flag=1
      break
  if Flag==1:
    B+=1
  Flag=0
  Uf=Unionfind(N)
  A=[]
print(B)   

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
using namespace std;
typedef long long ll;
ll prime(ll x) {
	ll i;
	if (x < 2)return 0;
	else if (x == 2) return 1;
	if (x % 2 == 0) return 0;
	for (i = 3; i*i <= x; i += 2) {
		if (x%i == 0) return 0;
	}
	return 1;
}
ll gcd(ll a, ll b) {
	if (a<b) { return gcd(b, a); }
	else if (a%b) { return gcd(b, a%b); }
	else { return b; }
}

ll MOD = 1000000007;
int main() {
	ll N, K;
	cin >> N >> K;
	ll A[N + 100];
	for (ll i = 0; i < N; i++) {
		cin >> A[i];
	}
	ll ans = A[0];
  	sort(A,A+N);
  	reverse(A,A+N);
	for (ll i = 0; i < N; i++) {
		ans = gcd(ans, A[i]);
	}
  	if(K>A[0])
      cout<<"IMPOSSIBLE"<<endl;
	else if (K%ans == 0)
		cout << "POSSIBLE" << endl;
	else
		cout << "IMPOSSIBLE" << endl;
}

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

using namespace std;

int main(){

	int n; cin >>n;
	bool flag = true;
	for(int i=0; i<n; i++){
		int t; cin >> t;

		if(t % 2 ==0){
			if(t % 3 ==0 || t % 5 == 0)
			{

			}
			else if(t % 3 !=0 && t % 5 != 0){
				flag = false;
				break;
			}
		}

	}
	if(flag)cout << "APPROVED" << endl;
	else 
		cout << "DENIED" << endl;
	
		
	return 0;
}

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

typedef ostringstream OSS;
typedef istringstream ISS;

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<PII> VPII;

#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x) (x).begin(),(x).end()
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int N, M, s, t;
VVI es;

VI bfs(int p0) {
	VI d(N, INF);
	d[p0] = 0;

	queue<int> q;
	q.push(p0);

	while (q.size()) {
		int p = q.front();
		q.pop();

		int next_cost = d[p] + 1;
		
		for (auto next : es[p]) {
			int &dist = d[next];
			if (next_cost < dist) {
				dist = next_cost;
				q.push(next);
			}
		}
	}

	return d;
}

int main(void) {
	cin >> N >> M >> s >> t;
	--t; --s;
	es.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		es[a].PB(b);
		es[b].PB(a);
	}

	// s, t????????????????????¢?±???????
	VI sd = bfs(s);
	VI td = bfs(t);
	int st = sd[t];

	// ?????¢->?????°?????????
	VI d2c_t(100010);
	for (auto d : td) {
		if (d == INF) continue;
		d2c_t[d]++;
	}

	// count
	LL cnt = 0;
	for (auto d : sd) {
		if (d == INF) continue;
		int idx = st - d - 2;
		if (idx >= 0) {
			cnt += d2c_t[idx];
		}
	}

	cout << cnt << endl;


	return 0;
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    sort(a.begin(), a.end());
    cout << accumulate(a.begin(), a.begin() + min(k, n), 0);
}


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

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) begin(a), end(a)
#define has(a, b) (a.find(b) != a.end())
#define fora(i, n) for(int i = 0; i < n; i++)
#define forb(i, n) for(int i = 1; i <= n; i++)
#define forc(a, b) for(const auto &a : b)
#define ford(i, n) for(int i = n; i >= 0; i--)
#define maxval(t) numeric_limits<t>::max()
#define minval(t) numeric_limits<t>::min()
#define imin(a, b) a = min(a, b)
#define imax(a, b) a = max(a, b)
#define sz(x) (int)(x).size()

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

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

void calc(const vector<ll> &A, vector<vector<ll>> &dp) {
	int L = sz(A);
	dp = vector<vector<ll>>(3, vector<ll>(L + 1));

	fora(i, L) {
		ll v = A[i];
		ll sub = 0;
		if (v == 0) sub = 1;
		if (v % 2 == 0) {
			dp[0][i + 1] = max(0ll, dp[0][i] + A[i] - 1);
			dp[1][i + 1] = max({0ll, dp[1][i] + A[i] - 2 * sub, dp[0][i] + A[i] - 1});
			dp[2][i + 1] = max({0ll, dp[2][i] + A[i] - 2 * sub });
			imax(dp[0][i + 1], dp[2][i + 1]);
		} else {
			dp[0][i + 1] = max(0ll, dp[0][i] + A[i]);
			dp[1][i + 1] = max({0ll, dp[0][i] + A[i], dp[1][i] + A[i] - 1});
			dp[2][i + 1] = max({0ll, dp[2][i] + A[i] - 1});
			imax(dp[0][i + 1], dp[2][i + 1]);
		}
	}
}

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

	int L;
	cin >> L;

	vector<ll> A(L);
	fora(i, L) cin >> A[i];

	ll sum = 0;
	fora(i, L) sum += A[i];

	vector<vector<ll>> dp, rdp;
	calc(A, dp);
	reverse(all(A));
	calc(A, rdp);
	reverse(all(rdp[0]));
	reverse(all(rdp[1]));
	reverse(all(rdp[2]));

	/*fora(i, L + 1) cout << dp[0][i] << " ";
	cout << endl;
	fora(i, L + 1) cout << dp[1][i] << " ";
	cout << endl;
	fora(i, L + 1) cout << dp[2][i] << " ";
	cout << endl;
	fora(i, L + 1) cout << rdp[0][i] << " ";
	cout << endl;
	fora(i, L + 1) cout << rdp[1][i] << " ";
	cout << endl;
	fora(i, L + 1) cout << rdp[2][i] << " ";
	cout << endl;*/


	ll res = 0;
	fora(i, L + 1) {
		fora(j, 3) fora(k, 3) {
			//imax(res, dp[j][i] + rdp[k][i]);
			imax(res, dp[j][i]);
			imax(res, rdp[k][i]);
			imax(res, dp[0][i] + rdp[0][i]);
			if (j == 2 || k == 2) imax(res, dp[j][i] + rdp[k][i]);
		}
	}

	cout << sum - res << endl;
}


Measured memory_bytes: 12772
(* O(1) *)
let f0 n =
  let last = if n mod 2 = 0 then n else 0 in
  last lxor if (n + 1) / 2 mod 2 = 0 then 0 else 1

(* O(1) *)
let solve a b = f0 (a - 1) lxor f0 b

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

let _ =
  match read_ints () with
  | [a; b] -> solve a b |> string_of_int |> print_endline
  | _ -> ()

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


void solve(long long X){
  for(long long a = -1000; a <= 1000; a++) {
    long long pow_a = pow(a, 5);

    for(long long b = -1000; b <= 1000; b++) {
      if(pow_a - pow(b, 5) == X) {
        cout << a << " " << b << endl;
        return;
      }
    }
  }
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long X;
  scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 4028
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
    long long int n,c=0,ans=100000000000;
    cin>>n;
    vector<long long int>a(1000000);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<100;i++){
        for(int j=0;j<n;j++){
            c+=(a[j]-i)*(a[j]-i);
        }
        if(ans>c){
            ans=c;
        }
        c=0;
    }
    cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }



main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    int ans = 0, pref = 0;
    for (int i = 0; i < n; i++) {
        pref = (pref + a[i]) % MOD;
    }
    for (int i = 0; i < n; i++) {
        pref = (pref - a[i] + MOD) % MOD;
        ans = (ans + (ll)pref * a[i]) % MOD;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3980
D = gets.to_i
C = gets.chomp.split.map(&:to_i)
s = D.times.map{gets.split.map(&:to_i)}
c = Array.new(26, 0)
t = []

(0..D-1).each do |i|

  (0..25).each do |l|
    c[l] += C[l]
  end
ans = 0
boder = s[i][0]+10*c[0]

  (1..25).each do |e|
    if s[i][e]+10*c[e] >= boder
      ans = e
      boder = s[i][e]+10*c[e]
    end
  end
c[ans] = 0
puts ans+1
end


  



Measured memory_bytes: 14344
#include <stdio.h>
#include <string.h>

int main(void) {

  char s[200001];
  scanf("%s", s);
  int length = strlen(s);
  long white = 0;
  long score = 0;
  for (int i = 0; i < length; i++) {
    if (s[i] == 'W') {
      white++;
      score += i;
    }
  }
  white = white*(white-1)/2;
  printf("%ld\n", score-white);

  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	string s;
	cin>>s;
	s[3] = '8';
	cout<<s<<endl;
}

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

struct node
{
	int key;
	node* lc, * rc, * p;
};

node* root = NULL;

void insert(int x)
{
	node* pre = root;        //设当前节点为根，以根为起点
	node* temp = pre;        //用来保存当前节点的临时指针

	node* in = (node*)malloc(sizeof(node));
	in->key = x;
	in->lc = NULL;     
	in->rc = NULL;     

	while (pre != NULL)
	{
		temp = pre;
		if (in->key < pre->key)
			pre = pre->lc;
		else
			pre = pre->rc;
	}
	pre = temp;

	in->p = pre;
	if (pre == NULL)
		root = in;
	else
	{
		if (in->key < pre->key)
			pre->lc = in;
		else
			pre->rc = in;
	}
}

void Inorder(node* r)
{
	if (r->lc != NULL)
		Inorder(r->lc);

	cout << " " << r->key;

	if (r->rc != NULL)
		Inorder(r->rc);
}

void Preorder(node* r)
{
	cout << " " << r->key;

	if (r->lc != NULL)
		Preorder(r->lc);
	if (r->rc != NULL)
		Preorder(r->rc);
}

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

	int n, x;
	string p;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> p;

		if (p == "insert")
		{
			cin >> x;
			insert(x);
		}
		else
		{
			Inorder(root);
			cout << endl;
			Preorder(root);
			cout << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 26680
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <limits>
#include <random>
#include <utility>
#include <vector>

namespace procon {
  class UnionFind {
  private:
    struct nodeinfo {
      int par;
      int rank;
      nodeinfo(int par) : par(par), rank(0) {}
    };
    std::vector<nodeinfo> node;

  public:
    UnionFind(int n) : node() {
      node.reserve(n);
      for (int i = 0; i < n; ++i) {
	node.push_back(nodeinfo(i));
      }
    }
    int root(int x) {
      if (node[x].par == x) {
	return x;
      }
      return node[x].par = root(node[x].par);
    }
    void unite(int x, int y) {
      x = root(x);
      y = root(y);
      if (x == y) {
	return;
      }
      if (node[x].rank < node[y].rank) {
	node[x].par = y;
      } else {
	node[y].par = x;
	if (node[x].rank == node[y].rank) {
	  ++node[x].rank;
	}
      }
    }
    bool is_same_set(int x, int y) { return root(x) == root(y); }
  };
}
  
int main(void) {
  int size, n_query;
  std::cin.read((char *)&size, sizeof(int));
  std::cin.read((char *)&n_query, sizeof(int));

  std::vector<uint64_t> query(n_query);
  std::cin.read((char *)query.data(), sizeof(uint64_t) * n_query);

  const int mask = (1 << 30) - 1;

  uint64_t res = 123456789;
  procon::UnionFind uf(size);
  for (uint64_t q : query) {
    const int com = q >> 60;
    const int x = (q >> 30) & mask;
    const int y = (q >> 0) & mask;
    assert(0 <= x && x < size);
    assert(0 <= y && y < size);
    if (com) {
      res = res * 17 + (uf.is_same_set(x, y) ? 1 : 0);
    } else {
      uf.unite(x, y);
    }
  }
  std::cout << res << std::endl;
  return 0;
}



Measured memory_bytes: 89044
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n,b=0,cnt=0;
  string a;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    if(a=="A")b++;
    else b--;
    if(b==-1)cnt++;
  }
  if(cnt==0&&b==0)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 3156
#include<iostream>
using namespace std;
int main(){
	int W,H,x,y,r;
	cin>>W>>H>>x>>y>>r;
	if(W>=x+r&&x-r>=0&&H>=y+r&&y-r>=0){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

class UFTree {
private:
	static const int	UFTREE_NODE_NUM = 200001;
	int mNode[UFTREE_NODE_NUM];
	int mRank[UFTREE_NODE_NUM];
	int mNodeNum[UFTREE_NODE_NUM];

public:
	void init(int n)
	{
		for (int i = 0; i < n; i++) {
			mNode[i] = i;
			mRank[i] = 0;
			mNodeNum[i] = 1;
		}
	}

	int find(int x)
	{
		if (mNode[x] == x) {
			return x;
		}
		else {
			mNode[x] = find(mNode[x]);
			return mNode[x];
		}
	}

	void unite(int x, int y)
	{
		int idxX = find(x);
		int idxY = find(y);

		if (idxX == idxY) {
			return;
		}

		if (mRank[idxX] > mRank[idxY]) {
			mNode[idxY] = idxX;
			mNodeNum[idxX] += mNodeNum[idxY];
		}
		else {
			mNode[idxX] = idxY;
			mNodeNum[idxY] += mNodeNum[idxX];
			if (mRank[idxX] == mRank[idxY]) {
				mRank[idxY]++;
			}
		}
	}

	bool isSameSet(int x, int y)
	{
		return find(x) == find(y);
	}

	int getNodeNum(int x)
	{
		auto node = find(x);
		return mNodeNum[node];
	}
};

UFTree treeR;
UFTree treeT;


int main()
{
	int N, K, L;
	cin >> N >> K >> L;

	treeR.init(N + 1);
	treeT.init(N + 1);

	for (auto i = 0; i < K; ++i)
	{
		int p, q;
		cin >> p >> q;
		treeR.unite(p, q);
	}

	for (auto i = 0; i < L; ++i)
	{
		int r, s;
		cin >> r >> s;
		treeT.unite(r, s);
	}

	vector<pair<int, int>> list;
	map<pair<int, int>, int> m;
	for (auto i = 1; i <= N; ++i)
	{
		auto p = make_pair(treeR.find(i), treeT.find(i));
		list.push_back(p);
		if (m.find(p) != m.end())
		{
			++m[p];
		}
		else
		{
			m[p] = 1;
		}
	}

	for (auto i = 0; i < N; ++i)
	{
		cout << m[list[i]];
		if (i < N)
		{
			cout << " ";
		}
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 18160
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	S = input()
	cnt = 0
	val = 0
	for i in S:
		if i != "S":
			val += 1
			cnt = max(val, cnt)
		else:
			cnt = max(val, cnt)
			val = 0

	cnt = max(val, cnt)
	print(cnt)


	




if __name__ == '__main__':
	main()

Measured memory_bytes: 9388
N, K = map(int, input().split())
X = list(map(int, input().split()))

time = 100000000000007
for i in range(0, N-K+1):
  if X[i] < 0 and X[i+K-1] > 0:
    if abs(X[i]) >= abs(X[i+K-1]):
      time = min(abs(X[i+K-1]-X[i]) + abs(X[i+K-1]),time)
    else:
      time = min(abs(X[i+K-1]-X[i]) + abs(X[i]),time)
  if X[i] >= 0:
      time = min(abs(X[i+K-1]-X[i]) + abs(X[i]),time)
  if X[i+K-1] <= 0:
      time = min(abs(X[i+K-1]-X[i]) + abs(X[i+K-1]),time)

print(time)


Measured memory_bytes: 14372
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(n);i++)
#define PI 3.1415926535897932384626433832795028841971693993
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9+7;

int main(){
    int n,ans=0;
    cin>>n;
    map<ll,ll> dat;
    rep(i,n){
        int a;
        cin>>a;
        if(dat[a]==0){
            ans++;
            dat[a]++;
        }
        else{
            ans--;
            dat.erase(a);
        }
    }
    cout<<ans;
}

Measured memory_bytes: 9664
#include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
int main(){
	int n,a[12],b[12];
	while(cin >> n, n) {
		int m = 0;
		rep(i,12) {
			cin >> a[i] >> b[i];
		}
		rep(i,12) {
			m += a[i]-b[i];
			if(m>=n) {
				cout << i+1 << endl;
				break;
			}
		}
		if(m<n) cout << "NA" << endl;
	}
}

Measured memory_bytes: 1160
// B - Comparison
#include <bits/stdc++.h>
using namespace std;
#define ote(x) cout<<(x)<<endl

int main(){
	string A,B; cin>>A>>B;
	int Na = A.size(), Nb = B.size();
	if(Na>Nb){ ote("GREATER"); return 0; }
	else if(Na<Nb){ ote("LESS"); return 0; }
	for(int i=0; i<Na; ++i)
		if(A[i]>B[i]){ ote("GREATER"); return 0; }
		else if(A[i]<B[i]){ ote("LESS"); return 0; }
	ote("EQUAL");
}

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

int main()
{
	vector<int> v(26,0);
	char c;
	while(cin >> c){
		if(isupper(c)) v[c-'A']++;
		else if(islower(c)) v[c-'a']++;
	}
	for(int i=0; i<26; i++){
		cout << (char)(i+'a') << " : " << v[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1172
using System;
using static System.Console;
class Program
{
    static void Main(string[] args)
    {
        string[] input = ReadLine().Split(' ');
        int A = int.Parse(input[0]);
        int B = int.Parse(input[1]);
        int a = Math.Max(A + B, A - B);
        int ans = Math.Max(a, A * B);
        WriteLine(ans);
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
#include<assert.h>

using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }




void solve(void)
{
  int N;cin>>N;
  vector<int> vec (N,0);
  for (int i = 0; i < N; i++)
  {
     cin>>vec[i];
  }  
  int MAX = -1;
  int MIN = INF;
  for (int i = 0; i < N; i++)
  {
    chmax(MAX,vec[i]);
    chmin(MIN,vec[i]);
  }

  if(MAX - MIN >=  2)
  {
    cout<<"No"<<endl;
    return;
  }
  // DEBUG(MAX,MIN);

  if(MAX - MIN == 0)
  {
    int SAME = 1;
    for (int i = 0; i < N; i++)
    {
      if(vec[i] != N -1) SAME = 0;
    }
      if(SAME == 1)
      {
        cout<<"Yes"<<endl;
        return;
      }

      if(2*MAX <= N)
      {
        cout<<"Yes"<<endl;
        return;
      }

      cout<<"No"<<endl;
      return;
    
  }

  if(MAX - MIN == 1)
  {
    int x = 0,y = 0;
    for (int i = 0; i < N; i++)
    {
      if(MAX -1 == vec[i]) x++;
      else y++;


    }
      if(x < MAX && 2*(MAX - x )<= y)
      {
        cout<<"Yes"<<endl;
        return;
      }
    cout<<"No"<<endl;
    
  }
  


  

  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	    // input N
        // 整数 N に対して 1,2,...,N を入れ替えた P1,P2,...PN なる数列を選ぶ
        // P1 % 1 + P2 % 2 + ... PN % N の最大値を出力せよ
        // N = 13 の場合、 ANS = 78
        // 13 1 2 3 4 5 6 7 8 9 10 11 12
        Scanner sc = new Scanner(System.in);
        long numN = sc.nextLong();
        long retNum = 0;
        if(numN > 1){
            long subN = numN - 1;
            retNum = (subN + 1) * subN / 2;
        }
        System.out.println(retNum);
    }
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int a, b; cin >> a >> b;
  cout << (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0 ? "Possible" : "Impossible") << endl;
  
}


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

using namespace std;

typedef long long ll;

struct para
{
    ll x, y;
};

ll maxi(ll a, ll b)
{
    if (a > b)
        return a;
    return b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<para> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;
    ll X = a[0].x, Y = a[0].y;
    for (int i = 1; i < n; ++i)
    {
        ll A;
        if (X % a[i].x == 0)
            A = X;
        else
            A = X - (X % a[i].x) + a[i].x;
        ll B;
        if (Y % a[i].y == 0)
            B = Y;
        else
            B = Y - (Y % a[i].y) + a[i].y;
        ll k1 = A / a[i].x;
        ll k2 = B / a[i].y;
        ll k = maxi(k1, k2);
        X = a[i].x * k;
        Y = a[i].y * k;
    }
    cout << X + Y;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#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 <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  int n; cin >> n;
  vector<lint> a(n);
  vector<lint> b(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  if(accumulate(ALL(a), 0LL) < accumulate(ALL(b), 0LL)) {
    cout << -1 << endl;
    return 0;
  }
  
  vector<lint> c(n);
  lint need = 0;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    c[i] = a[i] - b[i];
    need += max(b[i] - a[i], 0LL);
    if(b[i] - a[i] > 0) ans++;
      
  }
  
  sort(RALL(c));
  for(int i = 0; i < n; i++) {
    if(need <= 0) break;
    ans++;
    need -= c[i];
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 2560
module AOJ_Volume0102;

import std.stdio,std.string,std.conv;

int main()
{
	int a[101][101];
	while(true)
	{
		int n = readln.chomp.to!int;
		if(n == 0) break;

		foreach(i;0..n)
		{
			string[] s = readln.chomp.split(" ");
			foreach(j;0..s.length)
			{
				a[i][j] = s[j].to!int;
			}
		}

		int sum_n = 0;
		foreach(i;0..n)
		{
			int sum = 0;
			int sum_2 = 0;
			foreach(j;0..n)
			{
				sum += a[i][j];
				sum_2 += a[j][i];
			}
			a[i][n] = sum;
			a[n][i] = sum_2;

			sum_n += a[i][n];
		}

		a[n][n] = sum_n;

		foreach(i;0..n+1)
		{
			foreach(j;0..n+1)
			{
				writef("%5d",a[i][j]);
			}
			writeln;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
#include<stdio.h>
#include<string.h>
int main(void){
int n,h,m;
char mozi[200],cmozi[200],hmozi[200];
while(1){
scanf("%s",mozi);
if(mozi[0]=='-')break;
n=strlen(mozi);
scanf("%d",&m);
for(int a=0;a<m;a++){
scanf("%d",&h);
strncpy(cmozi,mozi,h);
cmozi[h]='\0';
for(int b=h,c=0;b<=n;b++,c++)hmozi[c]=mozi[b];
strcat(hmozi,cmozi);
strcpy(mozi,hmozi);
}
printf("%s\n",mozi);
}
return 0;
}


Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
int a[100002][2];
int main()
{
	fastio();
	int x, y;
	int n, cnt[4] = { 0, }, val[2] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;
		if (cnt[i & 1] < ++a[t][i & 1])cnt[i & 1] = a[t][i & 1],val[i&1]=t;
		else if (cnt[(i & 1) + 2] < a[t][i & 1])cnt[(i & 1) + 2] = a[t][i & 1];
	}
	if (val[0] != val[1])cout << n - cnt[0] - cnt[1];
	else cout <<n- max(cnt[0]+cnt[3],cnt[1]+cnt[2]);
	return 0;
}

Measured memory_bytes: 1024
from itertools import*
from bisect import*
(n, m, k), a, b = [list(map(int, o.split())) for o in open(0)]
*a, = accumulate([0] + a)
*b, = accumulate([0] + b)
c = 0
for i in range(n + 1):
    if a[i] > k:
        break
    c = max(c, i + bisect(b, k - a[i]) - 1)
print(c)

Measured memory_bytes: 41348
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokenizer = null;
    int totalCases, testNum;

    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    void solve() throws IOException {

    }

    void execute() throws IOException {
        int h = ni();
        int w = ni();
        int[][] dp = new int[h + 1][w + 1];
        dp[1][1] = 1;
        for (int i = 1; i <= h; i++) {
            String s = ns();
            for (int j = 1; j <= w; j++) {
                if (i == 1 && j == 1) {
                    continue;
                }
                char c = s.charAt(j-1);
                if (c == '#') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
                }
            }
        }

        out.print(dp[h][w]);

        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().execute();
    }

    void debug(Object... os) {
        System.out.println(Arrays.deepToString(os));
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String ns() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(br.readLine());
        }
        return tokenizer.nextToken();
    }

    String nline() throws IOException {
        tokenizer = null;
        return br.readLine();
    }

    boolean input() throws IOException {
        return true;
    }

}


Measured memory_bytes: 34812
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int j = 0; j < 5; j++)
            {
                var nm = ReadInts();
                if (nm[0] == 0 && nm[1] == 0)
                {
                    return;
                }

                var sugoroku = new List<int>();
                var saikoro = new List<int>();
                var now_position = 0;

                for (int i = 0; i < nm[0]; i++)
                {
                    sugoroku.Add(ReadInt());
                }
                for (int i = 0; i < nm[1]; i++)
                {
                    saikoro.Add(ReadInt());
                }
                for (int i = 1; i <= nm[1]; i++)
                {
                    now_position += saikoro[i - 1];
                    if (now_position >= nm[0] - 1)
                    {
                        WriteLine(i);
                        break;
                    }
                    else
                    {
                        now_position += sugoroku[now_position];
                        if (now_position >= nm[0] - 1)
                        {
                            WriteLine(i);
                            break;
                        }
                    }

                }
            }
        }
        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}



Measured memory_bytes: 15944
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

def nasu(x, L):
  t = 1000
  a = -1
  for i in range(len(L)):
    if i == x: continue
    if L[i] < t:
      t = L[i]
      a = i
  return a

L = []
to = nasu(-1, a)
fr = -1
for i in range(K + 1):
  for j in range(N):
    if j == to: continue
    if j == fr: continue
    a[j] -= 1
    L.append(j + 1)
  if a[to] == 0:
    print(-1)
    exit()
  a[to] -= 1
  L.append(to + 1)
  fr = to
  to = nasu(to, a)

print(len(L))
for i in L:
  print(i, end = " ")
print("")

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

int main(void) {
	char c;
	string ans;

	cin >> c;

	ans = "vowel";
	switch (c) {
		case 'a' :
			break;
		case 'i' :
			break;
		case 'u' :
			break;
		case 'e' :
			break;
		case 'o' :
			break;
		default :
			ans = "consonant";
			break;
	}

	cout << ans << '\n';
	return 0;
}


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

int n, a;
int main() {
	cin >> n;
	while(n--) {
		cin >> a;
		if(a%2==0 && a%3 && a%5) return puts("DENIED")*0;
	}
	return puts("APPROVED")*0;
}

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

int main(){
    int X,A;
    cin>>X>>A;
    if(X<A){
        cout<<"0"<<endl;
    }else{
        cout<<"10"<<endl;
    }
}

Measured memory_bytes: 256