akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,w;
	cin>>n>>w;
	ll weight[n];
	ll value[n];
	ll ans[n+1][w+1];
	for(int i=0;i<n;i++)
	{
		cin>>weight[i]>>value[i];
	}
	for(int i=0;i<=n;i++)
	{
		ans[i][0]=0;
	}
	for(int i=0;i<=w;i++){
		ans[0][i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(weight[i-1]>j){
				ans[i][j]=max(ans[i-1][j],ans[i][j-1]);
				//cout<<ans[i][j]<<endl;
			}
			else
			{
				ans[i][j]=max(ans[i-1][j],max(ans[i][j-1],ans[i-1][j-weight[i-1]]+value[i-1]));
				//cout<<ans[i][j]<<endl;
			}
		}
	}
	cout<<ans[n][w]<<endl;
	return 0;
}

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

typedef long long ll;
const ll MAX_N=200000;

int main() {
        ll n, t;
        cin >> n >> t;

        ll each_time[MAX_N];
        for (ll i=0; i<n; ++i) {
                cin >> each_time[i];
        }

        ll emit_time = 0;
        for (ll i=1; i<n; ++i) {
                ll using_time = each_time[i]-each_time[i-1];
                if (using_time>t) {
                        emit_time += t;
                } else {
                        emit_time += using_time;
                }
        }
        emit_time += t;

        cout << emit_time << endl;
}


Measured memory_bytes: 1792
# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()


Measured memory_bytes: 64400
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
/*
for(i=0;i<N;++i)
{
	
}
*/
int main()
{
	ll i,j,k;
	ll N,M,K;
	string S;
	ll H,W,A,B;
	cin>>H>>W>>A>>B;
	int a = (2*A-W);
	int b = (2*B-H);
	int c = (A*H-B*W);
	int w,h,ch=0;
	for(w=0;w<=W;++w)
	{
		for(h=0;h<=H;++h)
		{
			if(a*h-b*w==c)
			{
				ch=1;
				break;
			}
		}
		if(ch)
			break;
	}
	if(!ch)
		cout << "No" << endl;
	else
	{
		int ww[1024]={0};
		for(i=0;i<W;++i)
		{
			if(i<w)
				ww[i]=B;
			else
				ww[i]=H-B;
		}
		int hh[1024]={0};
		for(i=0;i<H;++i)
		{
			if(i<h)
				hh[i]=A;
			else
				hh[i]=W-A;
		}
		for(i=0;i<H;++i)
		{
			for(j=0;j<W;++j)
			{
				if(ww[j]&&hh[i])
				{
					ww[j]--;
					hh[i]--;
					cout << 1;
				}
				else
				{
					cout << 0;
				}
			}
			cout << endl;
		}
	}

	return 0;
}




















Measured memory_bytes: 1280
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>

using namespace std;

int main(void) {

	int a,b;
	string s;

	cin>>a>>b;
	int num;
	for (int i = 0; i < 2; i++) {
		if(a>b){
			num+=a;
			a--;
		}else{
			num+=b;
			b--;
		}
	}
	cout<<num<<"\n";




	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

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

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

mat mul(mat &A, mat &B){
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++){
        for (int k = 0; k < B.size(); k++){
            for (int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

mat pow(mat A, ll n){
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main(){
    int n, k;
    cin >> n >> k;
    int num = (n-1) * (n-2);
    num /= 2;
    if(num < k){
        cout << -1 << endl;
        return 0;
    }
    vec u[n];
    rep(i, n - 1) u[0].push_back(i + 1);
    // rep(i, n - 1) u[i+1].push_back(0);
    int e = 0;
    int v;
    while(num > k){
        if(u[e].size() == n - e - 1) {
            e++;
            v = e + 1;
        }
        u[e].push_back(v);
        num--;
        v++;
    }
    vector<P> edge;
    rep(i, n){
        rep(j, u[i].size()){
            if(i < u[i][j]){
                edge.push_back(P(i + 1, u[i][j] + 1));
            }
        }
    }
    int ans;
    ans = edge.size();
    cout << ans << endl;
    rep(i, edge.size()){
        cout << edge[i].first << " " << edge[i].second << endl;
    }
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(n<=16/2&&m<=16/2)
	{
		printf("Yay!");
	} 
	else
	{
		printf(":(");
	}
	return 0;
 }

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll n;cin >>n;
    string ans="";
    ll k=2;
    ll t=0;
    if(n==0)ans+='0';
    while(n!=0){
//        cout<<n%2<<endl;
        if(n%2!=0){
            ans+='1';
//            cout<<n%2<<endl;
            if(t%2==0){
                n--;
            }
            else {
                n++;
            }
        }
        else {
            ans+='0';
        }
        n/=2;
        t++;
    }
    reverse(all(ans));
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            string result = "No";
            for(long i = 1; i <= 9; i++)
            {
                if (N % i == 0 && N / i < 10)
                {
                    result = "Yes";
                }
            }
            Console.WriteLine(result);
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

Measured memory_bytes: 11092
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    N, M = mi()
    if N >= M:
        print(0)
        return

    X = lmi()
    X.sort()

    X_dis = []
    for i in range(len(X) - 1):
        X_dis.append(X[i+1] - X[i])
    X_dis.sort()

    if N == 1:
        print(sum(X_dis))
    else:
        print(sum(X_dis[:-N + 1]))

    return

main()


Measured memory_bytes: 20680
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#define int long long
using namespace std;

signed main() {
	int N;
	cin >> N;
	vector<int> vec(N);
	for(int i = 0;i < N;i++) {
		cin >> vec.at(i);
	}
	for(int i = N - 1;i >= 1;i--) {
		if(vec.at(i) < vec.at(i - 1)) {
			vec.at(i - 1)--;
		}
	}
	bool answer = true;
	for(int i = N - 1;i >= 1;i--) {
		if(vec.at(i) < vec.at(i - 1)) {
			answer = false;
			break;
		}
	}
	if(answer == true) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 1024
<?php
list($N) = ints();
$exist = false;
for ($K = 1; $K * ($K - 1) <= 2 * $N; ++$K) {
    if ($K * ($K - 1) === 2 * $N) {
        $exist = true;
        break;
    }
}
if (!$exist) exit('No');
echo 'Yes' . PHP_EOL;
echo $K . PHP_EOL;
$n = 1;
for ($i = 0; $i < $K - 1; ++$i) {
    for ($j = $i + 1; $j < $K; ++$j) {
        $s[$i][] = $n;
        $s[$j][] = $n;
        ++$n;
    }
}
for ($i = 0; $i < $K; ++$i)
    echo count($s[$i]) . ' ' . implode(' ', $s[$i]) . PHP_EOL;
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


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

int main(){
	int N;
	cin >> N;
	int i = 1;
	while(N > i*(i+1)/2){
		i++;
	}
	int k = i+1;
	int ans[k][k-1];
	int num = 1;
	int b;
	if(N == (k*(k-1)/2)){
		cout << "Yes" << endl;
        cout << k << endl;
		for(int a=0;a<k;a++){
			cout << k-1;
			for(b=0;b<a;b++){
				ans[a][b] = ans[b][a-1];
				cout << " " << ans[a][b];
			}	
			while(b<k-1){
				ans[a][b] = num;
				cout << " " << ans[a][b];
				num++;
				b++;
			}
			cout << endl;
		}	
	}else{
		cout << "No" << endl;
	}
	return 0;
}


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

bool judge(int d, char c, int x, int y) {
	if(d==0&&c=='o'&&x==y){return 1;}
	if(d==0&&c=='x'&&x!=y){return 1;}
	if(d==1&&c=='x'&&x==y){return 1;}
	if(d==1&&c=='o'&&x!=y){return 1;}
	return 0;
}

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

  int N; cin >> N;
  string s; cin >> s;

  rep(i, 2) {
    rep(j, 2) {
      int a[N]; // 1 = wolf, 0 = sheep
      a[1] = i;
      a[2] = j;

      for(int i = 3; i <= N; i++) {
				if(a[i - 1] == 0 && s[i - 1] == 'o' || a[i - 1] == 1 && s[i - 1] == 'x') {
				  a[i == N ? 0 : i] = a[i - 2];
        } else {
          a[i == N ? 0 : i] = a[i - 2] ^ 1;
        }
      }

      if(judge(a[1], s[1], a[0], a[2]) && judge(a[0], s[0], a[N-1], a[1])) {
        rep(i, N) {
          if(a[i]) {
            cout << 'W';
          } else {
            cout << 'S';
          }
        }
        cout << endl;
        return 0;
      }
    }
  }

  cout << -1 << endl;
}


Measured memory_bytes: 976
N,M = map(int,input().split())
edges = []
for _ in range(M):
    a,b,c = map(int,input().split())
    edges.append((a,b,c))

cost = [-float("INF")]*(N+1)
cost[1] = 0
cnt = 0
flag = True
for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

tmp = cost[N]

for _ in range(N):
    for a,b,c in edges:
        if cost[a]+c > cost[b]:
            cost[b] = cost[a]+c

if tmp < cost[N]:
    print("inf")
else:
    print(tmp)



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

using namespace std;

int main(){
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N);
    vector<vector<int>> pos(200001);
    for(int i=0;i<N;i++){
        cin >> A[i];
        pos[A[i]].push_back(i);
    }
    vector<int> next(N);
    for(auto& v : pos){
        for(int i=0;i<v.size();i++){
            next[v[i]] = (v[(i+1)%v.size()] + 1) % N;
        }
    }
    vector<int> res;
    long long cycle = 0, p = 0;
    while(cycle < K){
        auto ncycle = cycle;
        if(next[p] == (p+1)%N) ++ncycle;
        if(next[p] <= p) ++ncycle;
        auto npos = next[p];
        if(ncycle >  K || (ncycle == K && npos > 0)){
            res.push_back(A[p]);
            if(p == N-1){
                p = 0;
                ++cycle;
            } else {
                p++;
            }
        } else {
            cycle = ncycle;
            p = npos;
            if(cycle < K && p == 0){
                K %= cycle;
                cycle = 0;
            }
        }
    }
    for(auto& t : res) cout << t << " ";
    cout << endl;
}

Measured memory_bytes: 14968
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(false),cin.tie(0);
using namespace std;
typedef long long ll;
ll a,b,c,sum,t;
const ll maxn=200005;
const ll mod=1e9+7;
ll num;


int prime[2750135];
vector<int> p;
void sieve(){
fill(prime+2,prime+2750135,1);
for(int i=2;i<=2750135;++i){
if(prime[i]==1) p.push_back(i);
for(int j:p){
if(i*j>2750135) break;
prime[i*j]=j;
 if(i%j==0) break;
 }
 }
 }
ll n,k;
int main()
{
    //IOS
    while(cin>>n>>k)
    {
        if(k==1) cout<<"0\n";
        else cout<<n-k<<"\n";
    }


}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long ll;
using namespace std;

int main() {
  int n,m,x;
  cin >> n >> m >> x;
  vector<int> c(n);
  vector<vector<int> > a(n,vector<int> (m));
  rep(i,0,n) {
    cin >> c[i];
    rep(j,0,m) cin >> a[i][j];
  }
  int ans=10000000;
  for (int bit=0; bit<(1<<n); ++bit) {
    bool flag=true;
    int sum=0;
    vector<int> v(m);
    rep(i,0,n) {
      if (bit&1<<i) {
        rep(j,0,m) {
            v[j]+=a[i][j];
        }
        sum+=c[i];
      }
    }
    //cout << sum <<endl;
    rep(i,0,m) {
        if (v[i]<x) flag=false;
    }
    if (flag) ans=min(ans,sum);
  }
  if (ans==10000000) {
      cout << "-1" << endl;
      return 0;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3192
#include <cstdio>
#include <cstdint>

intmax_t res[]={2,1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349,15127,24476,39603,64079,103682,167761,271443,439204,710647,1149851,1860498,3010349,4870847,7881196,12752043,20633239,33385282,54018521,87403803,141422324,228826127,370248451,599074578,969323029,1568397607,2537720636,4106118243,6643838879,10749957122,17393796001,28143753123,45537549124,73681302247,119218851371,192900153618,312119004989,505019158607,817138163596,1322157322203,2139295485799,3461452808002,5600748293801,9062201101803,14662949395604,23725150497407,38388099893011,62113250390418,100501350283429,162614600673847,263115950957276,425730551631123,688846502588399,1114577054219522,1803423556807921,2918000611027443,4721424167835364,7639424778862807,12360848946698171,20000273725560978,32361122672259149,52361396397820127,84722519070079276,137083915467899403,221806434537978679,358890350005878082,580696784543856761,939587134549734843};

int main() {
  int N;
  scanf("%d", &N);
  printf("%jd\n", res[N]);
  return 0;
}


Measured memory_bytes: 128
def e(x, y):
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1

    while c1 != 0:
        m = c0 % c1
        q = c0 // c1

        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)

    return c0, a0, b0

def c(n,r):
    ngo = 1
    ngoo = 1
    for i in range(min(n,r)):
        ngo*=(n-i)
        ngoo*=(i+1)
        ngoo%=(10**9+7)
        ngo%=(10**9+7)
        #ngo %= (10**9+7)
        #ngoo %= (10**9+7)
    return (ngo*e(ngoo,10**9+7)[1])%(10**9+7)
    
def beki(x,y):
    if y == 0:
        return 1
    if y == 1:
        return x
    if y %2 == 0:
        return beki((x**2)%(10**9+7),y//2)%(10**9+7)
    else:
        return x*beki(x,y-1)%(10**9+7)
    
import math
n,a,b = map(int,input().split())
ngo = (beki(2,n)-1)%(10**9+7)
ans = (ngo-c(n,a)-c(n,b))
print(ans%(10**9+7))

Measured memory_bytes: 3064
#include<stdio.h>
#include<tuple>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<vector>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;
typedef tuple<int,int,int> t3;
 
const int MX = 1<<19;
 
vector<int> C[MX];
int rv[MX];
int N;
ll ans[MX], add[MX];
 
int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		rv[i] = i;
		C[i].push_back(i);
	}
	vector<t3> E;
	for(int i = 1; i < N; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		E.emplace_back(c, a, b);
	}
	sort(E.begin(), E.end());
	reverse(E.begin(), E.end());
	for(t3 e : E){
		int a, b, c;
		tie(c, a, b) = e;
		int p = rv[a], q = rv[b];
		if( C[p].size() > C[q].size() ) swap(p, q);
		int x = C[p].size(), y = C[q].size();
		for(int e : C[p]){
			C[q].push_back(e);
			rv[e] = q;
			ans[e] += add[p] + (ll)c * y - (ll)c * x - add[q];
		}
		add[q] += (ll)c * x;
	}
	for(int i = 1; i <= N; i++) printf("%lld\n", ans[i] + add[rv[i]]);
}

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

namespace atcoder
{
    class Program
    {
        static void solve(string input)
        {
            if (input == null || input.Length != 3) return;
            bool validated = input.All(c => c == 'A' || c == 'B');
            if (!validated) return;
            Console.WriteLine((input.Distinct().Count() == 1) ? "No" : "Yes");
        }

        static void Main(string[] args)
        {
            solve(Console.ReadLine());
        }
    }
}

Measured memory_bytes: 13268
#include<stdio.h>
int main(void){
	int a,b,c,x;
	scanf("%d",&a);scanf("%d",&b);scanf("%d",&c);scanf("%d",&x);
	int n=0,i,j,k;
	for(i=0;i<=a;i++)
		for(j=0;j<=b;j++)
			for(k=0;k<=c;k++)
				if(500*i+100*j+50*k==x)n++;
	printf("%d\n",n);
}

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

using namespace std;

bool comp(const vector<int> &a, const vector<int> &b){
  return (a[1] < b[1]);
}


int main(){
  int N, tmp;
  int sub = 1, res = -1;
  vector<int> a, b;
  vector<vector<int>> under, upper;
  cin >> N;
  for (int i=0; i<N; i++){
    cin >> tmp;
    a.push_back(tmp);
  }
  for (int i=0; i<N; i++){
    cin >> tmp;
    sub *= (int)(a[i] - tmp >= 0);
    if(a[i] - tmp > 0) upper.emplace_back(vector<int>({i, a[i] - tmp}));
    else if(a[i] - tmp < 0) under.emplace_back(vector<int>({i, a[i] - tmp}));
  }
  if (sub == 1){
    res = 0;
  }
  else{
    sort(under.begin(), under.end(), comp);
    sort(upper.begin(), upper.end(), comp);
    int upper_res = upper.back()[1], under_res = -under.back()[1];
    upper.pop_back();
    under.pop_back();
    res = 2;
    while (true){
      if (upper_res < under_res){
        if (upper.empty()){
          res = -1;
          break;
        }
        under_res -= upper_res;
        upper_res = upper.back()[1];
        upper.pop_back();
        res++;
      }
      else if (upper_res > under_res){
		if (under.empty()) break;
        upper_res -= under_res;
        under_res = -under.back()[1];
        under.pop_back();
        res++;
      }
      else{
        if (under.empty()) break;
        else if(upper.empty()){
          res = -1;
          break;
        }
        upper_res = upper.back()[1];
        under_res = -under.back()[1];
        upper.pop_back();
        under.pop_back();
        res += 2;
      }
    }
  }

  cout << res << endl;
  return 0;
}

Measured memory_bytes: 6128
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
  ll n,m;
  cin>>n;
  for(ll i=1;i<=(ll)(sqrt(n));i++){
    if(n/i*i==n){
      m=n/i;
    }
  }
  int c=0;
  while(m!=0){
    m/=10;
    c++;
  }
  cout<<c;
}


Measured memory_bytes: 256
import Control.Monad
  
check mass  i j (x,y)
 | mass !! x !! y == '.' = True
 | otherwise =   or$map (\(a,b) -> (mass !! a !! b)=='#')     $ filter (\(a,b) -> (0<=a&&a<i&&0<=b&&b<j)) $ map (\(a,b) -> (x+a,y+b)) pm
  where
   pm = [(0,1),(0,-1),(1,0),(-1,0)]
main = do
 [i,j] <-map read . words <$> getLine
 mass <- replicateM i getLine
 putStrLn  (if (and $ map (check mass i j) [(a,b)|a<-[0..i-1],b<-[0..j-1]]) then "Yes" else "No")



Measured memory_bytes: 1020
import math

n = input()
x = [int(_) for _ in raw_input().split()]
y = [int(_) for _ in raw_input().split()]

for p in range(1,4):
    sum = 0
    for i in range(n):
        sum += math.pow(abs(x[i] - y[i]),p)
    print math.pow(sum,1/float(p))

print max([abs(float(i) - float(j)) for i,j in zip(x,y) ])

Measured memory_bytes: 6660
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
#include<climits>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int p[n + 1]; rrep(i, 1, n + 1) cin >> p[i];
    int c = 0, bc = 0;
    while (1) {
        
        rrep(i, 1, n) if (p[i] == i) {swap(p[i], p[i + 1]); c++;}
        if (p[n] == n) {swap(p[n], p[n - 1]); c++;}
        if (bc == c) break;
        bc = c;
    }
    cout << c << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, M;
  cin >> N >> M;
  vector<int> V(N);
 
  for (int i=0; i<M; i++){
  int a, b;
  cin >>a >>b;
  V.at(a-1) ++;
  V.at(b-1) ++;
  }
  
  for (int i=0; i<N; i++){
  cout << V.at(i) << endl;
  }
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m;

vector<LL> edges[110000];
LL vis[110000];

LL bip;
LL num[2];
LL numv;

LL ans = 0;
void dfs(LL v, LL color){
    if(vis[v] == color) return;
    if(vis[v] == 3-color){
        bip = 0;
        return;
    }
    num[color-1]++;
    numv++;
    vis[v] = color;
    for(LL j = 0; j < edges[v].size(); j++){
        dfs(edges[v][j], 3-color);
    }
}
int main(){
    for(LL i = 0; i < n; i++){
        vis[i] = 0;
    }
    cin >> n >> m;
    for(LL i = 0; i < m; i++){
        LL a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    ans -= m;
    for(LL i = 0; i < n; i++){
        if(vis[i]) continue;
        bip = 1;
        num[0] = num[1] = 0;
        numv = 0;
        dfs(i, 1);
        if(bip){
            ans += num[0] * num[1];
        } else {
            ans += numv*(numv-1)/2;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 7808
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

typedef pair<long long int, bool> P;

int main(){
	
	while(true){
		long long int n, m, p, q, r;
		cin >> n;
		if(n == 0){
			break;
		}
		cin >> m >> p >> q >> r;
		deque<P> v;
		P pp;
		pp.first = r;
		pp.second = true;
		v.push_back(pp);
		pp.first = n - r;
		pp.second = false;
		v.push_back(pp);
		
		for(int i = 0; i < m; i++){
			
			int x, y;
			cin >> x >> y;
			y = n - y;
			
			deque<P> v1, v2;
			
			while(true){
				x -= v[0].first;
				if(x <= 0){
					P p2;
					p2.first = v[0].first + x;
					p2.second = v[0].second;
					v1.push_back(p2);
					v[0].first = -x;
					break;
				}
				v1.push_back(v[0]);
				v.pop_front();
			}
			
			while(true){
				int sz = v.size();
				y -= v[sz - 1].first;
				if(y <= 0){
					P p2;
					p2.first = v[sz - 1].first + y;
					p2.second = v[sz - 1].second;
					v2.push_back(p2);
					v[sz - 1].first = -y;
					break;
				}
				v2.push_back(v[sz - 1]);
				v.pop_back();
			}
			
			for(int i = 0; i < v1.size(); i++){
				v.push_back(v1[i]);
			}
			
			for(int i = 0; i < v2.size(); i++){
				v.push_front(v2[i]);
			}
		}
		
		long long int ans = 0;
		
		for(int i = 0; i < v.size(); i++){
			q -= v[i].first;
			if(q <= 0){
				if(v[i].second){
					ans += v[i].first + q;
				}
				break;
			}
			if(v[i].second){
				ans += v[i].first;
			}
		}
		
		p--;
		for(int i = 0; i < v.size(); i++){
			p -= v[i].first;
			if(p <= 0){
				if(v[i].second){
					ans -= v[i].first + p;
				}
				break;
			}
			if(v[i].second){
				ans -= v[i].first;
			}
		}
		
		cout << ans << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 3316
a, b, c, x, y = map(int, input().split())
out1 = a * x + b * y
if x > y:
    out2 = x*c*2
    out3 = y*c*2 + (x-y)*a
else:
    out2 = y*c*2
    out3 = x*c*2 + (y-x)*b
print(min([out1, out2, out3]))

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

int n, m, num, max1, max2, ans, a[100005];

int main() {
	max1 = max2 = num = ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = n; i; i--) {
		max1 = max(a[i], max1);
		num = max(max1 - a[i], num);
	}
	for (int i = n; i; i--) {
		max2 = max(a[i], max2);
		if (max2 - a[i] == num)ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define M 998244353
//#define M 1000000007
using namespace std;
const int inf=4e18;
const int MX=100;
const int MN=-100;
const double pi=3.14159265358979;
void dfstop(vector<int> DAG[],int s,int z[],vector<int> &topsort,bool &b)
{
	if(b)
		return;
	if(z[s]==1)
		b=1;
	if(z[s])
		return;
	z[s]=1;
	for(auto u:DAG[s])
	{
		dfstop(DAG,u,z,topsort,b);
	}
	z[s]=2;
	topsort.pb(s);
}
vector<int> topological_sort(vector<int> DAG[],int n)
{
	vector<int> topsort;
	int z[n+1]={0},i;
	bool b=0;
	for(i=1;i<=n;i++)
	{
		if(!z[i])
			dfstop(DAG,i,z,topsort,b);
	}
	if(b)
		topsort.clear();
	else
		reverse(topsort.begin(),topsort.end());
	return topsort;
}
void dfs(vector<int> v[],int s,int z[],int dis[])
{
	if(z[s])
		return;
	z[s]=1;
	for(auto u:v[s])
	{
		dfs(v,u,z,dis);
		dis[s]=max(dis[s],dis[u]+1);
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int n,m,i;cin>>n>>m;
	vector<int> graph[n+1];
	for(i=0;i<m;i++)
	{
		int x,y;cin>>x>>y;
		graph[x].pb(y);
	}
	vector<int> top=topological_sort(graph,n);
	int z[n+1]={0},dis[n+1]={0};
	for(i=0;i<n;i++)
	{
		if(!z[top[i]])
			dfs(graph,top[i],z,dis);
	}
	cout<<*max_element(dis,dis+n+1)<<endl;
}

Measured memory_bytes: 15988
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int N;

int main() {
    cin >> N;

    vi H(N);
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }

    int last = -1;
    int ans = 0, now = 0;
    for (int i = 0; i < N; i++) {
        if (last >= H[i])
            now++;
        else
            now = 0;

        ans = max(ans, now);
        last = H[i];
    }

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


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

int main(){
  int N,A=0,B=0;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  
  for(int i=0; i<N; i++){
    if(i%2==0){
      A += vec.at(i);
    }
    else{
      B += vec.at(i);
    }
  }
  
  cout << A-B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int64_t MOD=1000000007;
const long long INF = 1LL<<60;

int main() {
  int64_t K; cin>>K;
  if(K>=30) cout<<"Yes";
  else cout<<"No";
}


Measured memory_bytes: 3628
#include <stdio.h>

	int main(void){

	int yoko,tate,W,H,x,y,r;
	
	scanf("%d" "%d" "%d" "%d" "%d", &yoko, &tate, &x, &y, &r);
	
	W = yoko - x;
	H = tate - y;
	
	if((W + r) <= yoko && (W - r) >= 0){
		if((H + r) <= tate && (H - r) >= 0){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	else{
		printf("No\n");
	}
	
	return 0;
	}

Measured memory_bytes: 580
from collections import deque
h,w = map(int,input().split())
a = deque([])
for i in range(h):
    A = deque(str(input()))
    A.appendleft("#")
    A.append("#")
    a.append(A)
a.appendleft(["#"]*(w+2))
a.append(["#"] * (w+2))
ans = []
for i in range(h+2):
    tmp = "".join(a[i])
    print(tmp)

Measured memory_bytes: 3444
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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


int main() {

	int n, m; cin >> n >> m;
	vector<vector<int>> gr(n + 1);

	vector<int> h(n + 1, 0);
	for (int i = 1; i <= n; i++) cin >> h[i];

	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		bool flg = true;
		for (auto j : gr[i]) {
			if (h[j] >= h[i]) {flg = false; break;}
		}
		ans += (flg);
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 8716
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int H = sc.nextInt();
        int W = sc.nextInt();
        char[][] A = new char[H][W];
        for(int i = 0; i < H; i++){
            String S = sc.next();
            for(int j = 0; j < W; j++)
                A[i][j] = S.charAt(j);
        }
        sc.close();
        int right = 0;
        int down = 0;

        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(A[i][j] == '#'){
                    if(j != W-1){
                        if(A[i][j+1] == '#')
                            right++;
                    }
                    if(i != H-1){
                        if(A[i+1][j] == '#')
                            down++;
                    }
                }
            }
        }
        if(right == W-1 && down == H-1){
            System.out.println("Possible");
        } else {
            System.out.println("Impossible");
        }
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	for (int i=1; i<=5; i++) {
		int x;
		cin >> x;
		if (x != i)
			return cout << i, 0;
	}
	// ll n, b = 26;
	// cin >> n;
	// --n;
	// stack< char > ans;
	// // stack< int > ans;
	// while (n) {
		
		// //ans.push(n % b);
		// n /= b;
	// }
	// while (!ans.empty())
		// cout << ans.top() << ' ', ans.pop();
}


Measured memory_bytes: 3636
//Optional FAST
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
 
//Required Libraries
 

#include <bits/stdc++.h>
//#include<iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
//Required namespaces
 
using namespace std;
using namespace __gnu_pbds;
//typedef
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

//define
#define pb push_back
#define pf push_front
#define fi first
#define se second
//#define endl '\n'
#define forin(i,a,b) for(long long i=a;i<=b;i++)
#define forde(i,a,b) for(long long i=a;i>=b;i--)
#define fio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);

ll power(ll x,ll y)
{
    if (y == 0)
        return 1;
    ll p = power(x, y/2) % MOD;
    p = (p * p) % MOD;

    return (y%2 == 0)? p : (x * p) % MOD;
}
ll modInverse(ll a)
{
   return power(a,MOD-2);
}
vector<ll> pr; 
//ll z[1001][11]={0};
int main()
{
    /*
    #ifndef ONLINE_JUDGE
       freopen ("input.txt" , "r" , stdin);
		// freopen ("OUTPUT.txt" , "w" , stdout);
	#endif
    */
    fio;
    
    ll a;
    cin>>a;
    ll ans=0;
    ll i=0;
    while(a>0)
    {
        ans+=pow((ll)2,i);
        a/=2;
        i++;
    }
    cout<<ans<<endl;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SZ(x) (int)(x).size()
#define mset(a,x) memset(a,x,sizeof(a))
#define dbg(x) cout<<#x<<": "<<(x)<<"\n"
#define OUT(x) cout<<(x)<<"\n"
#define FASTIO cin.tie(0),ios::sync_with_stdio(0)
#define pb push_back
#define mp make_pair

int n;

int main() {
	FASTIO;
	cin >> n;
	vector<ll> a(n+2);
	rep(i,n) cin>>a[i];

	ll even=0, odd=0;
	rep(i,n){
		if(a[i]%2 == 0) ++even;
		else ++odd;
	}

	if(odd % 2 == 0){
		cout<<"YES"<<"\n";
	}
	else{
		cout<<"NO"<<"\n";
	}


    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] S = sc.next().toCharArray();
		sc.close();
		int max = 0;
		int cnt = 0;
		for(int i = 0; i < S.length; i++) {
			if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') {
				cnt++;
			} else {
				max = Math.max(max, cnt);
				cnt = 0;
			}
		}
		max = Math.max(max, cnt);
		System.out.println(max);
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int k,a,b;
  cin >> k >> a >> b;
  int tmp = 1;
  
  while(tmp*k<=b){
    if(tmp*k>=a && tmp*k<=b){
      cout << "OK\n";
      return 0;
    }
    tmp++;
  }
  cout << "NG\n";
  return 0;
}


Measured memory_bytes: 3652
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 262144

const char dn[] = "URDL";
std::pair<int,int> a[4][N];
int na[4];
std::pair<int,int> av[N], ah[N];
int nv, nh;
int ans = INT_MAX;

void find_ud()
{
    std::sort(av,av+nv);
    std::sort(ah,ah+nh);
    for(int i=0,j=0;i<nv;++i)
    {
        while(j<nh && ah[j] < av[i]) ++j;
        if(j==nh || av[i].ft != ah[j].ft) continue;
        ans = std::min(ans, (ah[j].sd-av[i].sd) * 5);
    }
}

void find_ur()
{
    for(int i=0;i<nv;++i)av[i] = {av[i].ft+av[i].sd, av[i].sd};
    for(int i=0;i<nh;++i)ah[i] = {ah[i].ft+ah[i].sd, ah[i].sd};
    std::sort(av,av+nv);
    std::sort(ah,ah+nh);
    for(int i=0,j=0;i<nv;++i)
    {
        while(j<nh && ah[j] < av[i]) ++j;
        if(j==nh || av[i].ft != ah[j].ft) continue;
        ans = std::min(ans, (ah[j].sd-av[i].sd) * 10);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;++i)
    {
        int x, y;
        char u;
        scanf("%d%d %c", &x, &y, &u);
        const char *p = strchr(dn,u);
        assert(p);
        int k = p - dn;
        a[k][na[k]++] = {x,y};
    }
    nv = na[0], nh = na[2];
    for(int i=0;i<nv;++i) av[i] = a[0][i];
    for(int i=0;i<nh;++i) ah[i] = a[2][i];
    find_ud();
    nv = na[1], nh = na[3];
    for(int i=0;i<nv;++i) av[i] = {a[1][i].sd,a[1][i].ft};
    for(int i=0;i<nh;++i) ah[i] = {a[3][i].sd,a[3][i].ft};
    find_ud();
    nv = na[0], nh = na[1];
    for(int i=0;i<nv;++i) av[i] = a[0][i];
    for(int i=0;i<nh;++i) ah[i] = a[1][i];
    find_ur();
    nv = na[0], nh = na[3];
    for(int i=0;i<nv;++i) av[i] = {-a[0][i].ft,a[0][i].sd};
    for(int i=0;i<nh;++i) ah[i] = {-a[3][i].ft,a[3][i].sd};
    find_ur();
    nv = na[2], nh = na[1];
    for(int i=0;i<nv;++i) av[i] = {a[2][i].ft,-a[2][i].sd};
    for(int i=0;i<nh;++i) ah[i] = {a[1][i].ft,-a[1][i].sd};
    find_ur();
    nv = na[2], nh = na[3];
    for(int i=0;i<nv;++i) av[i] = {-a[2][i].ft,-a[2][i].sd};
    for(int i=0;i<nh;++i) ah[i] = {-a[3][i].ft,-a[3][i].sd};
    find_ur();
    if(ans == INT_MAX) return puts("SAFE"), 0;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 6308
n,m=map(int,input().split())
a=[1 for i in range(n+2)]
for i in range(m):
    a[int(input())]=0
dp=[0 for i in range(n+1)]
dp[0]=1
for i in range(n):
    if ((i+1)<(n+1)) and a[i+1]:
        dp[i+1]=(dp[i+1]+dp[i])%1000000007
    if ((i+2)<(n+1)) and a[i+2]:
        dp[i+2]+=(dp[i+2]+dp[i])%1000000007
print(dp[n])


Measured memory_bytes: 7808
#include <stdio.h>

void CountingSort();
int A[2000000],n;

int main()
{

  int i;
  scanf("%d",&n);

  for( i = 0 ; i <n ; i++)scanf("%d",&A[i]);

  CountingSort();
}

void CountingSort()
{

  int C[10001],i,j=0;
  for(i = 0; i < 10001 ; i++) C[i] =0;

  for(i = 0;i<n ; i++)
    {
      C[A[i]]++;
    }
  
  for(i = 0 ; i <= 10000 ; i++)
    {
      while(C[i] > 0)
        {
          if(j == n-1)
            {
              printf("%d",i);
              break;
            }
          printf("%d ",i);
          C[i]--;
          j++;
        }

      //printf("\n");
    }

  printf("\n");
}


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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if(A + B > C + D) cout << "Left" << endl;
    else if(A + B < C + D) cout << "Right" << endl;
    else cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
 ll N;
  cin >>N;
  vl a(N);
  rep(i,N) {
cin >>a.at(i);
  }
  ll c=0;
  rep(i,N) {
    if(a.at(i)==1) {
      c++;
    }
  }
  if(c==0) {
    cout<<-1<<endl;
  }
  
  else if(c!=0) {
    
    ll co=0;
    ll asis=1;
    rep(i,N) {
      if(a.at(i)==asis) {
        co++;
        asis++;
      }
    }
    
    cout<<N-co<<endl;
  }
  
}
      
      


Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>

using namespace std;

int sum(int a, int b) {
	int t = 0;
	while (a > 0) {
		t += a % 10;
		a /= 10;
	}
	
	while (b > 0) {
		t+= b % 10;
		b /= 10;
	}

	return t;
}
int main() {
	int n;
	cin >> n;


	int mn = 1000000000;

	for (int i = 1; i < n; i++) {
		mn = min(mn, sum(i, n - i));
	}

	cout << mn << endl;

	return 0;
}

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

int main() {
  int N ; 
  cin >> N ; 
  vector<int> X(N) ;
  vector<int> Y(N) ;
  int T=0 ; 
  pair<int,int> Z[110] ; 
  
  for(int i = 0 ; i < N ; i++){
    cin >> X.at(i) ; 
  }
  
  for(int j = 1 ; j < 100 ; j++){
    for(int i = 0 ; i < N ; i++){
      Y.at(i) = (X.at(i) - j )*(X.at(i) - j ) ; 
      T = T + Y.at(i) ;
    }
    
    Z[j] = make_pair(T , j) ; 
    sort(Z , Z+j) ; 
    T = 0 ; 
    //cout << Z[1].first << endl ; 
  }
  
	cout << Z[1].first << endl ;
}

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

int main() {
  string s, t = "";
  cin >> s;
  rep(i, s.size()) t += 'x';
  cout << t << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
int vis[100005]={0};
int dp[100005]={0};
vector <int> graph[100005];
int solve(int i){
    if(vis[i]==1){
        return dp[i];
    }
    vis[i]=1;
    int q = 0;
    for(int x:graph[i]){
        q = max(q, 1+ solve(x));
    }
    dp[i] =q;
    return q;
}
int main(){
    int n , e;
    cin>>n>>e;
    for(int i=0; i<e;i++){
        int x, y;
        cin>>x>>y;
        graph[x].push_back(y);
    }
    int dis[n+1]={0};
    int maxm = 0;
    for(int i=1; i<=n;i++){
        if(vis[i]==0){
            maxm = max(maxm, solve(i));
        }
    }
    cout<<maxm<<endl;
}



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

int main() {
  string s;
  cin >> s;
  if(s == "Sunny"){
    cout << "Cloudy" << endl;
  }
  else if(s == "Cloudy"){
    cout << "Rainy" << endl;
  }
  else {
    cout << "Sunny" << endl;
  }
  
  return 0;
}


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

#define FOR(i,a,n) for (int i = a; i < (int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define whole(f,x,...) ([&](decltype((x)) whole) { \
    return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
template<typename T> bool chmin(T &a, const T &b) {if (a > b) { a = b; return true; }return false;}
template<typename T> bool chmax(T &a, const T &b) {if (a < b) { a = b; return true; }return false;}

using ll = int_fast64_t;

constexpr ll lINF = (1e18);
constexpr ll MOD = (1e9+7);

int main() {
  ll n, k; cin >> n >> k;
  vector<ll> a(n); REP(i,n) cin >> a[i];
  vector<ll> b(n+1, 0), d(n+1, 0);
  REP(i,n) {
    b[i+1] += b[i] + max(a[i], 0L);
    d[i+1] += d[i] + a[i];
  }
  ll ans = 0;
  REP(i,n-k+1) {
    ll sum = 0;
    sum += b[i];
    sum += b[n] - b[i+k];
    chmax(ans, sum);
    sum += d[i+k] - d[i];
    chmax(ans, sum);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  map<char, int> s;
  for(int i=0; i<4; i++){
    s[S[i]]++;
  }

  /*
  for(pair<char, int>x: s){
    cout<<x.first<<","<<x.second<<endl;
  }
  */
  bool ans = (s.size()==2 && s[S[0]]==2);

  cout<<(ans? "Yes\n": "No\n");
}

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

int main(){
  string str;
  cin >> str;
  int count = 0;
  while(str.size() > 0){
    int flag = 0;
    for(int i = 0; i < str.size()-1; i++){
      if(str[i] != str[i+1]){
        str = str.substr(0, i) + str.substr(i+2, str.size()-i);
        count += 2;
        flag = 1;
        break;
      }
  	}
    if(flag == 0){
      break;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 724
#include <bits/stdc++.h>
using namespace std;
using lint = int64_t;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    begin(v), end(v)
#define in        []{lint n; cin>>n; return n;}()
 
int main(){
    int N = in;
    vector<int> A(N);
    rep( i, N ) A[i] = in-1;
 
    vector<int> ans(N);
    while( !A.empty() ) {
        for( int i=A.size()-1; i>=0; i-- ) {
            if( A[i] == i ) {
                A.erase( A.begin() +i );
                ans[A.size()] = i;
                goto E;
            }
        }
        cout << "-1\n";
        return 0;
        E:;
    }
 
    rep( i, N ) cout << ans[i]+1 << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>

using namespace std;

int main(){
   int n;
   cin>>n;
   vector<string> s(n);
   for(int i=0;i<n;i++)cin>>s[i];
   int m;
   cin>>m;
   vector<string> t(m);
   for(int i=0;i<m;i++)cin>>t[i];

   int ans=0;
   for(int i=0;i<n;i++){
      int sum=0;
      for(int j=0;j<n;j++){
         if(s[j]==s[i])sum++;
      }
      for(int j=0;j<m;j++){
         if(t[j]==s[i])sum--;
      }
      ans=max(ans,sum);
   }
   cout<<ans<<endl;

   
}

   


Measured memory_bytes: 256