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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(r) (r).begin(), (r).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

const int MAX_L = 3010;
string S, T, R = "";
int x, y;
int dp[MAX_L][MAX_L] = {0};

int main() {
    cin >> S >> T;
    x = S.size(), y = T.size();

    rep(i, x) {
        rep(j, y) {
            if (S[i] == T[j]) chmax(dp[i+1][j+1], dp[i][j] + 1);
            chmax(dp[i+1][j+1], dp[i+1][j]);
            chmax(dp[i+1][j+1], dp[i][j+1]);
        }
    }
    // cout << dp[x][y] << endl;
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x-1][y]) x--;
        else if (dp[x][y] == dp[x][y-1]) y--;
        else {
            R.push_back(S[x-1]);
            x--; y--;
        }
    }
    reverse(ALL(R));
    cout << R << endl;
}


Measured memory_bytes: 38784
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define PB push_back
#define REP(i,a,b) for (int i = a ; i <= b ; i++)
#define REPI(i,a,b) for (int i = a ; i >= b ; i--)
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int OO = 1e9+7;
const int MOD = 1e9+7;
const int N = 1e5+7;

int mem[N];
int n;
int h[N];
int dp(int i)
{
    int &ret = mem[i];
    if (ret != -1) return ret;
    if (i == n-1) return 0;
    else if (i >= n) return OO;
    ret = min(dp(i+1)+abs(h[i]-h[i+1]),dp(i+2)+abs(h[i]-h[i+2]));
    cerr << i << ' ' << ret << endl;
    return ret;
}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    //freopen("teleport.in","r",stdin);
    //freopen("teleport.out","w",stdout);
    memset(mem,-1,sizeof mem);
    scanf("%d",&n);
    REP(i,0,n-1) scanf("%d",&h[i]);
    printf("%d\n",dp(0));

    return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
char s[maxn];
int len;
bool flag = true;

int main() {
#ifdef __AiR_H
    freopen("in.txt", "r", stdin);
#endif
    scanf("%s", s); len = strlen(s);
    int l = 0, r = len - 1, ans = 0;
    while (l < r) {
        if (s[l] == s[r]) { ++l; --r; continue; }
        if (s[l] == 'x') { ++l; ++ans; continue; }
        if (s[r] == 'x') { --r; ++ans; continue; }
        flag = false; break;
    }
    if (!flag) { printf("-1\n"); }
    else { printf("%d\n", ans); }
    return 0;
}


Measured memory_bytes: 384
import javax.xml.crypto.Data;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{

        //入力
        /*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        */
        Scanner sc = new Scanner(System.in);
        String str = sc.next();


        // 出力
        int n = str.length();
        System.out.println(str.substring(0, n - 8));
    }
}

Measured memory_bytes: 21076
#define rep(i,N) for(int i=0;i<(int)N;i++)
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N,loop=1;
  double x,y,sum=0.0;
  cin>>N;
  vector<int> a(N),b(N),A;
  rep(i,N){cin>>a.at(i)>>b.at(i);}
  rep(i,N){A.push_back(i+1);}
  rep(i,N){loop*=(i+1);}
  rep(i,loop)
  {
    rep(i,N-1)
    {
      x=pow((float)(a.at(A.at(i+1)-1)-a.at(A.at(i)-1)),2.0);
      y=pow((float)(b.at(A.at(i+1)-1)-b.at(A.at(i)-1)),2.0);
      sum+=pow((float)(x+y),0.5);
    }
    next_permutation(A.begin(),A.end());
  }
  cout<<fixed<<setprecision(10)<<(sum/loop)<<endl;
}

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

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

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n, ll mod)
{ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0) {
        if(n & 1) {
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b, ll mod)
{
    if(a == 0 && b == 0) return 1;
    if(a < b || a < 0) return 0;
    ll tmp = ifac[a - b] * ifac[b] % mod;
    return tmp * fac[a] % mod;
}

int main()
{
    int N, K;
    cin >> N >> K;
    ll mod = 1000000007;

    //大した量ではないので，先にfax[i]とifax[i]を全て計算しておく
    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i < 300000; i++){
        fac[i + 1] = fac[i] * (i + 1) % mod; // n!(mod M)
        ifac[i + 1] = ifac[i] * mpow(i + 1, mod - 2, mod) % mod; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }

    rep(i, K) {
        ll ans = 0;
        // (N-K+1)C(i+1)
        IFD cout << "i: " << i << endl << N - K + 1 << " " << i + 1 << " " << K - 1 << endl;
        ans = comb(N - K + 1, i + 1, mod);
        if(i != 0) {
            ans = ans * comb(K - 1, i, mod) % mod;
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long init = 100;
		int y = 0;
		while(init < X){
			long a = init / 100;
			init += a;
			++y;
		}
		System.out.println(y);
	}
}


Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long,long long>
#define ii pair<int,int>
#define mod 1000000007
#define endl '\n'
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

ll power(ll a,ll b){
	ll ans=1;
	while(b>0){
		if(b%2!=0){
			ans=(ans*a)%mod;
		}
		a=((a%mod)*(a%mod))%mod;
		b>>=1;
	}
	return ans;
}

void sieve(int n){
	bool prime[n+1];
	memset(prime,true,sizeof(prime));
	for(int p=2;p*p<=n;p++){
		if(prime[p]){
			for(int i=p*p;i<=n;i+=p)
				prime[i]=false;
		}
	}
	for(int p=2;p<=n;p++){
		if(prime[p])
			cout<<p<<" ";
	}
}

int main() {
	IOS;
	int t=1;
	//cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll ans=((power(10,n)+power(8,n))%mod-(2*power(9,n))%mod)%mod;
		if(ans<0)
			ans+=mod;
		ans%=mod;
		cout<<ans;
	}
	return 0;
}

Measured memory_bytes: 3652
n = int(input())
ans = 1
c=list(map(int, input().split()))

if 0 in c:
  print(0)
  
else:
  for i in range(n):
    ans *= c[i]
    if ans>10**18:
      print(-1)
      break
    
  if ans<=10**18:
    print(ans)

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

int main() {
	string s,t;
	cin >> s >> t;
	string ans = "Yes";
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] != t[i]) {
			ans = "No";
		}
	} 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define mod 1000000007
typedef long long int ll;
ll dp[100001];
int u(const void *a, const void *b){
    return *(ll*)a-*(ll*)b;
}
int d(const void *a, const void *b){
    return *(ll*)b-*(ll*)a;
}
int z(int a){
  if(a<1)a*=-1;
  return a;
}
int min(int a,int b){
  if(a>b)return b;
  return a;
}
int max(int a,int b){
  if(a>b)return a;
  return b;
}
int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}
int main(void) {
  int a,b;
  scanf("%d %d",&a,&b);
  if(b==1){
    PRN(0);
    return 0;
  }
  b-=a;
  int ans=1;
  while(b>0){
    b-=a-1;
    ans++;
  }
  PRN(ans);
  return 0;
}

Measured memory_bytes: 128
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define db double
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define mem(x,val) memset(x,val,sizeof x)
#define Swap(a,b,n) for(int I=0;I<=n;I++) swap(a[I],b[I])
#define PC __builtin_popcountll
#ifdef DEBUG
	#define debug(A,args...) fprintf(stderr,A,##args)
#else
	#define debug(A,args...) 
#endif
namespace mine
{
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
	template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
	ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
	bool IN(ll x,ll l,ll r){return l<=x and x<=r;}
	void GG(){puts("NO");exit(0);}
	
	const db eps=1e-8;
	const int INF=0x3f3f3f3f;
	const int MOD=1e9+7;
	int mm(const int x){return x>=MOD?x-MOD:x;}
	template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
	ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int M=5e6+10;
	ll fac[M],facinv[M],Inv[M];ll C(int n,int m){return n<0 or n<m?0:fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
	void PRE()
	{
		fac[0]=1;fo(i,1,M-1) fac[i]=fac[i-1]*i%MOD;
		facinv[M-1]=invm(fac[M-1]);fd(i,M-1,1) facinv[i-1]=facinv[i]*i%MOD;
		Inv[1]=1;fo(i,2,M-1) Inv[i]=(MOD-MOD/i)*Inv[MOD%i]%MOD;
	}
	const int N=1e6+10;
	//------------------FIXED------------------
	int a[N],rk[N];vc<int> to[N];bool win[N];
	void main()
	{
		int n=qread();fo(i,1,n) a[i]=qread(),rk[i]=i;sort(rk+1,rk+n+1,[&](int x,int y){return a[x]<a[y];});
		fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x); }
		fo(i,1,n) if(!win[rk[i]]) for(auto y:to[rk[i]]) if(a[y]>a[rk[i]]) win[y]=1;fo(i,1,n) if(win[i]) write1(i);
	}
};//����������
signed main()
{
	#ifdef DEBUG
	freopen("a.in","r",stdin);
	//freopen("z.txt","r",stdin);
	freopen("a.out","w",stdout);
	#endif
	srand(time(0));
	mine::PRE();//����Ԥ����ģ����
	mine::main();
	debug("\n---------------------Zory---------------------\nTime: %.2lf s",1.0*clock()/CLOCKS_PER_SEC);
}

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

int bubbleSort(int A[], int N) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = N - 1; j >= i + 1; j--) {
			if (A[j] < A[j - 1]) {
				swap(A[j], A[j - 1]);
				flag = 1;
				sw++;
			}                                                                                                                                                                                              
		}
	}
	return sw;
}

int main(void) {
	int A[100], N, sw;
	cin >> N;
	for (int i = 0; i < N; i++)cin >> A[i];

	sw = bubbleSort(A, N);

	for (int i = 0; i < N; i++) {
		if (i)cout << " ";
		cout << A[i];
	}
	cout << endl;
	cout << sw << endl;
	
	return 0;
}

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

using namespace std;
typedef long long ll;


int main()
{
    int n, z = 0;
    cin >> n;

    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i]==0)
            z++;
    }

    ll p = 1;
    if (z)
        cout << 0;
    else {
        for (int i = 0; i < n; i++) {
            if (a[i] <= 1000000000000000000/p) {
                p *= a[i];
            }
            else {
                p = -1;
                break;
            }
        }

        cout << p;
    }


    return 0;
}


Measured memory_bytes: 4308
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static PrintWriter out;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));

        int a = nextInt();
        int b = nextInt();
        int c = nextInt();

        System.out.printf("%d %d %d\n", c, a, b);

        out.close();
    }


    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static char nextCharacter() throws IOException {
        return next().charAt(0);
    }

    static String nextLine() throws IOException {
        return br.readLine().trim();
    }
}


Measured memory_bytes: 21204
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int k = scanner.nextInt();
			int result = 1;
			for (int i = 0; i < n; i++) {
				result = Math.min(result * 2, result + k);
			}
			System.out.println(result);
		}
	}
}


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

// global variables
int N;
vector<int> arr;
int ans = 0;

void input(void){
    cin >> N;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        arr.emplace_back(a);
    }
}

void solve(void){
    for(int i = 0; i < N; i++) ans += (arr[i] -1);
    cout << ans << endl;
}

int main(void){

    input();
    solve();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
#include <map>
#include <cstring>

#define dprintf(s,...) printf("%s:%d" s,__func__,__LINE__,__VA_ARGS__)
using namespace std;

typedef pair<int,int> P;

const int N=10000;
long long int a,b;


long long int gcd(long long int x,long long int y){
  if(y==0) return x;
  return gcd(y,x%y);
}

int main(){


  while(1){

    cin>>a>>b;
    if(cin.eof()) break;

    long long int c,d;
    c=gcd(a,b);
    d=a*b/c;
    cout<<c<<" "<<d<<endl;
    
  }

  return 0;
}

Measured memory_bytes: 3064
def f(x1, x2):
  W=[[i,1000] for i in range(n)]
  W[x1]=[x1,0]
  W[x2]=[x2,2000]
  G = range(n)
  while 1:
    A = sorted([W[e] for e in G], key=lambda x: x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1==x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost: W[p2] = [p2, min([w2, w1+cost[way]])]
  return W[x2][1]

def g(): return map(int, raw_input().split(","))

n=int(raw_input())
m=int(raw_input())
cost={}
for _ in [0]*m:
  a,b,c,d=g()
  a-=1
  b-=1
  cost[(a,b)]=c
  cost[(b,a)]=d
x1,x2,y1,y2=g()
x1-=1
x2-=1
print y1-y2-f(x1,x2)-f(x2,x1)

Measured memory_bytes: 4292
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;


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

	int n, m;
	cin >> n >> m;
	long *a = new long[n];
	vector<pair<long, long>> cb;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < m; i++)
	{
		long b, c;
		cin >> b >> c;
		cb.emplace_back(c, b);
	}
	sort(cb.begin(), cb.end());
	sort(a, a + n);

	int index = 0;
	for (int i = m - 1; i >= 0; i--)
	{
		int count = 0;
		bool flag = false;
		while(a[index] < cb[i].first)
		{
			a[index++] = cb[i].first;
			count++;
			if (count >= cb[i].second)
				break;
		}
		if (count <= 0)
			break;
	}

	long long int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
	}

	cout << sum << '\n';

	delete[] a;
	return 0;
}


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////


int main() {
  long long a, v;
  long long b, w;
  long long t;
  cin >> a >> v;
  cin >> b >> w;
  cin >> t;
  int d = abs(a-b);
  if (v <= w) {
    cout << "NO" << endl;
    return 0;
  }
  if ((v - w)*t >= d) {
    cout << "YES" << endl;
  }else {
    cout << "NO" << endl;
  }

  return 0;
}

// EOF

Measured memory_bytes: 3556
#include <iostream>
#include <map>
using namespace std;
typedef map<int,int> map_y;
typedef map<int,map_y> map_pos;
inline int hyp2( int x, int y ){
	return x * x + y * y;
}
int main(){
	int an, bn, x, y, r, r2, cnt;
	for( ; cin >> an >> bn >> r, an; ){
		map_pos mp;
		r *= 4;
		r2 = r * r;

		for( int i = an; i--; ){
			cin >> x >> y;
			++mp[x][y];
		}
		for( cnt = 0; bn--; ){
			cin >> x >> y;
			map_pos::iterator it1 =
				mp.lower_bound( x - r );
			
			for( ; it1 != mp.end(); ++it1 ){
				if( it1->first > x + r ){	break;	}
				map_y::iterator it2 = it1->second.lower_bound( y - r );
				for( ; it2 != it1->second.end(); ++it2 ){
					if( it2->first > y + r ){	break;	}
					if(	hyp2( it1->first - x, it2->first - y ) <= r2 ){
						cnt += it2->second;
					}
				}
			}
		}
		cout << cnt << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;

int main(){
	//long long n;
	string s;
	cin >>s;
	int legth=s.size();
	//cin >>n;
	//long long bef=n;
	vector<int>position(legth+2,0);
	vector<int> dp(legth + 2, 0); //e,
	
	int bisum=0;
	for(int i=0;i<legth;i++){
		bisum+=s[i]-'0';
	}
	//coectdi+=top;
	//legth--;
	//dp[0][0]=coectdi-1+legth*9;
	
	/*

	147

	axx ->99
	1ax ->139
	14a ->147


	306

	axx ->299
	3ax -> 306
	30x -> 306

	2007

	axxx 1999
	2axx ->2007
	20ax ->2007
	200a -> 2007
	*/
	dp[legth-1]=bisum;
	bisum-=s[legth-1]-'0';
	for(int i=s.size()-2;i>=0;i--){
		if(s[i]=='0'){
			dp[i]=dp[i-1];
		}else{
			dp[i]=bisum-1+9*(s.size()-1-i);
		}
	///	cout<<dp[i]<<endl;
		bisum-=s[i]-'0';
	}
	int ans=0;
	for(int i=0;i<legth;i++){
		chmax(ans,dp[i]);
	}
	cout<<ans;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
   int D, G;
   cin >> D >> G;
   int p[D], c[D];
   for (int i = 0; i < D; i++) {
      cin >> p[i] >> c[i];
   }

   int ans = 1e9;
   for (int mask = 0; mask < (1 << D); mask++) {
      int s = 0, num = 0, rest_max = -1;
      for (int i = 0; i < D; ++i) {
         if ((mask >> i) & 1) {
            s += 100 * (i+1) * p[i] + c[i];
            num += p[i];
         } else {
            rest_max = i;
         }
      }
      if (s < G) {
         int s1 = 100 * (rest_max + 1);
         int need = (G - s + s1 - 1) / s1;
         if (need >= p[rest_max]) {
            continue;
         }
         num += need;
      }
      ans = min(ans, num);
   }
   cout << ans << endl;
}


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

long long cnt=0;
int m=0;
vector<int> G;

void insertionSort(int A[], int n, int g){
    for (int i=g; i<n; i++){
        int v = A[i];
        int j = i - g;
        while(j >= 0 && A[j] > v){
            A[j+g] = A[j];
            j -= g;
            cnt++;
        }
        A[j+g] = v;
    }
}
void shellSort(int A[], int n){
    //G = {1, 4, 13, 40, 121, 364, ...}
    for (int h=1;;){
        if(h > n) break;
        G.push_back(h);
        m++;
        h = h*3 + 1;
    }
    for(int i=m-1; i>=0; i--){
        insertionSort(A, n, G[i]);
    }
}

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){scanf("%d", &a[i]);}

    shellSort(a, n);

    cout << m << endl;
    for(int i=m-1; i>=0; i--){
        if(i != 0)cout << G[i] << ' ';
        else cout << G[i] << endl;
    }
    cout << cnt << endl;
    for(int i=0; i<n; i++){
        cout << a[i] << endl;
    }

    return 0;
}


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

# define rep(i, n) for(int(i)=0;(i)<(n);(i)++)
# define reps(i, n) for(int(i)=1;(i)<=(n);(i)++)
# define rrep(i, n) for(int i=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<typename T> void dump(T e){std::cout << e << std::endl;}
template<typename T> void dump(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void dump(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ dump(v); } }
typedef long long ll;

int main() {
  int R,G,B; cin >> R >> G >> B;
  int T = R*100 + G*10 + B;
  if (T%4 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int val[1000005],wgt[1000005];
vector<vector<int> >adj;
int x[1000005],y[1000005];
const int lim=1e5;
int dp[15][100005];
vector<pair<int ,int> > pp[1000005];
int ans[100005];

void dfs(int ver,int xx)
{
    if(xx<10)
    {
        for(int j=0;j<=lim;j++)
        {
            dp[xx][j]=dp[xx-1][j];
            if(j-wgt[ver]>=0)
                dp[xx][j]=max(dp[xx][j],dp[xx-1][j-wgt[ver]]+val[ver]);            
        }
        for(int j=1;j<=lim;j++)
            dp[xx][j]=max(dp[xx][j],dp[xx][j-1]);
        for(auto i:pp[ver])
        {
            ans[i.second]=dp[xx][i.first];
        }
        for(auto i:adj[ver])
        {
            dfs(i,xx+1);
        }
    }
    else
    {
        int tt=xx-10;
        int z=(1<<tt);
        const int fi=(1<<(tt+1));
        for(int i=z;i<fi;i++)
        {
            x[i]+=wgt[ver]+x[i-z];
            y[i]+=val[ver]+y[i-z];
        }
        
        for(auto i:pp[ver])
        {
            for(int j=0;j<fi;j++)
            {
                if(x[j]<=i.first)
                    ans[i.second]=max(ans[i.second],y[j]+dp[9][i.first-x[j]]);
            }
        }

        for(auto i:adj[ver])
        {
            dfs(i,xx+1);
        }

        for(int i=z;i<fi;i++)
        {
            x[i]=0;
            y[i]=0;
        }
    }
}


signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n;
    cin>>n;
    adj.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>val[i]>>wgt[i];
    for(int i=2;i<=n;i++)
    {
        adj[i/2].push_back(i);
    }

    int q;
    cin>>q;
    int xx,yy;
    for(int i=0;i<q;i++)
    {
        cin>>xx>>yy;
        pp[xx].push_back({yy,i});
    }
    dfs(1,1);
    for(int i=0;i<q;i++)
        cout<<ans[i]<<"\n";    
}    

 

Measured memory_bytes: 52080
# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


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


def read():
    N = II()
    a = ILI()
    return N, a


def solve(N, a):
    n_odd = 0
    n_div_2 = 0
    n_div_4 = 0
    for _a in a:
        if _a % 2 == 1:
            n_odd += 1
        else:
            if _a % 4 == 0:
                n_div_4 += 1
            else:
                n_div_2 += 1

    ans = ""
    if n_div_2 == 0:
        if n_div_4 >= n_odd - 1:
            ans = "Yes"
        else:
            ans = "No"
    else:
        if n_div_4 >= n_odd:
            ans = "Yes"
        else:
            ans = "No"

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


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

using namespace std; 
#define ll long long
#define ld long double
ll power(ll x, ll y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
int main()
{
	ll l,r,d;
	cin >> l >> r >> d;
	ll ans=0;
	for(ll i=l;i<=r;i++)
	{
		if(i%d==0)
			ans++;
	}
	cout << ans << "\n";
}

Measured memory_bytes: 3620
#include <cstdio>
typedef long long ll; 
int main()
{
	ll a,b,c,d;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	ll s1=a*c;
	ll s2=a*d;
	ll s3=b*c;
	ll s4=b*d;
	ll max=s1;
	if(max<s2) max=s2;
	if(max<s3) max=s3;
	if(max<s4) max=s4;
	printf("%lld",max);
    return 0;
}

Measured memory_bytes: 1736
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.second < secondElof.second;
}
ll nod(ll F) { return log10(F) + 1; }
//**定義場所**//
//gcd, isPrime, eratos, modinv, bitSearch, dfs, bfs, dijkstra, UnionFind, COM//
ll i, j, k, l, m, n; ll N, M, K, H, W, L; string S;
ll MOD = 1000000007; ll ans = 0; ll INF = 9999999999999;
vl flag, color; vll path;
//***********//
int main() {
	string S;
	cin >> S;
	cin >> K;
	N = S.length();
	vl A(N);
	for (i = 0; i < N; i++) {
		A[i] = ctoi(S[i]);
	}
	// dp[i][smaller][j]
	// 今調べている桁をi, 未満フラグをsmaller, 0が出た回数をjとする
	vector<vll> dp(N+1, vll(2, vl(K+1, 0)));
	// 0桁目は便宜上0であると考える
	// 0桁目は0しかありえないがこれはsmallerが確定していないのでsmaller=0しかありえない
	// 結局dp[0][0][0]=1, それ以外は全て0で初期化すればよい
	for (i = 0; i < N + 1; i++) {
		for (j = 0; j < 2; j++) {
			for (k = 0; k < K + 1; k++) {
				dp[i][j][k] = 0;
			}
		}
	}
	dp[0][0][0] = 1;
	for (i = 0; i < N; i++) {
		for (ll smaller = 0; smaller < 2; smaller++) {
			for (j = 0; j < K + 1; j++) {
				for (ll x = 0; x <= (smaller ? 9 : A[i]); x++) {
					// j==K で x>0 の時はサイズオーバーで死ぬのでcontinue処理！
					if (j == K && x > 0) { continue; }
					dp[i + 1][smaller || x < A[i]][j + (x > 0)] += dp[i][smaller][j];
				}
			}
		}
	}
	// [smaller || x < A[i]]は以下の寄与条件を反映させたものである。
	// smaller=0 から smaller=0 → x = A[i] のとき寄与
	// smaller=0 から smaller=1 → x < A[i] のとき寄与
	// smaller = 1 から smaller = 0 → 常に寄与なし
	// smaller=1 から smaller=1 → 常に寄与
	// [j + (x > 0)]は以下の寄与条件を反映させたものである。(但しj==Kのときのみ例外処理アリ)
	// j=p から j=p → x=0のとき寄与
	// j=p から j=p+1 → x!=0のとき寄与
	cout << dp[N][0][K] + dp[N][1][K];
}


Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

#define ceil(a,b) (a%b?a/b+1:a/b)

#define dump1(v) for(auto i:v) std::cout << i << ' '; std::cout << "\n";

struct FastIO
{
  FastIO() {
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(0); 
  }
}fastio;

struct ZAlgorithm
{
	std::vector<int> z;
	ZAlgorithm(std::string s) : z(s.size(),0) {
		int l,r;
		// [l,r)
		l=r=0;
		for(int i=1;i<s.size();i++) {
			if(i>=r) {
				l=r=i;
				while(r<s.size() && s[r]==s[r-l]) r++;
				z[i] = r-l;
				continue;
			}
			if(z[i-l]<r-i) {
				z[i] = z[i-l];
				continue;
			}
			l=i;
			while(r<s.size() && s[r]==s[r-l]) r++;
			z[i] = r-l;
			continue;
		}
		z[0] = s.size();
	}
};

int dfs(int i,int c,std::vector<int>&to,std::vector<int>&went) {
	if(to[c]==i) return -1;
	if(to[c]==-1) return 0;
	if(went[c]>0) return went[c];
	int x = dfs(i,to[c],to,went);
	if(x==-1) return -1;
	return went[c]=x+1;
}

signed main() {
	std::string s;
	std::string t;
	std::cin >> s >> t;

	std::string a = "";

	int t_sz = t.size();
	int s_sz = s.size();
	while(a.size()<s_sz+t_sz) a+=s;

	std::string x = t + '$' + a;
	ZAlgorithm z(x);

	std::vector<int> zz(s_sz);
	rep(i,s_sz) zz[i] = z.z[t_sz+1+i];

	std::vector<int> to(s_sz,-1);
	rep(i,s_sz) if(zz[i]==t_sz) to[i] = (i+t_sz)%s_sz;

	std::vector<int> went(s_sz,0);
	rep(i,s_sz) {
		if(zz[i]!=t_sz) continue;

		if(dfs(i,i,to,went)==-1) {
			print(-1);
			return 0;
		}
	}
	int max = 0;
	for(auto i:went) max = std::max(max,i);
	print(max);
	return 0;
}


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

int main() {
  string A, B, C;
  cin >> A >> B >> C;
  map<char, queue<char>> mp;

  for (char x : A) {
    mp['a'].push(x);
  }
  for (char x : B) {
    mp['b'].push(x);
  }
  for (char x : C) {
    mp['c'].push(x);
  }

  char next, p = 'a', ans = 'd';
  while (ans == 'd') {
    next = mp[p].front();
    mp[p].pop();
    p = next;
    if (mp[p].size() == 0) {
      ans = p;
    }
  }
  if (ans == 'a') {
    cout << 'A' << endl;
  } else if (ans == 'b') {
    cout << 'B' << endl;
  } else {
    cout << 'C' << endl;
  }
}

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

using namespace std;

typedef long long ll;

struct D {
	int d, p;

	D() {}
	D(int d, int p) : d(d), p(p) {}
};
bool operator >(const D& d1, const D& d2) {
	return d1.p > d2.p;
}


int main() {
	int N, M;
	while (cin >> N >> M, N || M) {
		vector<D> v;
		for (int i = 0; i < N; ++i) {
			int d, p; cin >> d >> p;
			v.push_back( D(d, p) );
		}
		sort( v.begin(), v.end(), greater<D>() );

		int ans = 0;
		for (int i = 0; i < N; ++i) {
			if (M >= v[i].d) {
				M -= v[i].d;
			}
			else {
				ans += v[i].p * (v[i].d - M);
				M = 0;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1328
import sys
input = sys.stdin.readline
import heapq as hp

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
Xs = sorted(list(set(A)))

ans = 10**14
for x in Xs:
    Ps = []
    tmp = []
    for a in A:
        if a >= x:
            tmp.append(a)
        else:
            if len(tmp) >= K:
                Ps.append(tmp)
            tmp = []
    if len(tmp) >= K:
        Ps.append(tmp)
    q = []
    for P in Ps:
        P.sort()
        for i, p in enumerate(P):
            q.append(p)
            if len(P)-K-i == 0: break
    if len(q) < Q:
        break
    q.sort()
    ans = min(ans, q[Q-1]-x)

print(ans)
    

Measured memory_bytes: 47324
object Main extends App {
  val knInput = scala.io.StdIn.readLine()
  val knArray = knInput.split(" ").map(_.toInt).toSeq
  val k = knArray(0)
  val n = knArray(1)

  val aInput = scala.io.StdIn.readLine()
  val aArray = aInput.split(" ").map(_.toInt).toVector

  val distance = aArray.zipWithIndex.map { a =>
    if (a._2 == 0) {
      a._1 + k - aArray(n - 1)
    } else {
      a._1 - aArray(a._2 - 1)
    }
  }
  val max = distance.max
  println(distance.sum - max)
}

Measured memory_bytes: 61296
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<=(b);++(i))
#define rep(i, n)  FOR(i,0,n-1)
#define FFOR(i, a, b) for(int (i)=a;(i)>(b);--(i))
#define rrep(i,n) FFOR(i,0,n)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define lb long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define int long long
#define double long double
#define mod 1000000007LL
#define INF 123456789012345
typedef pair<ll, ll> P;
typedef pair<int, P> PP;

const int maxn =1e5 + 10;

P battle[maxn];

signed main(){

	int n,m;cin>>n>>m;
	
	rep(i,m) cin>>battle[i].first >> battle[i].second;

	sort(battle,battle+m);
	//cout << endl;
	//rep(i,m) cout << battle[i].first <<" "<<battle[i].second<<endl;
	

	int ans = 0;
	int bunri;
	int checkNo=1;

	rep(i,m)
	{
		if(battle[i].first < checkNo)
		{
			checkNo = min(checkNo,battle[i].second);
			continue;
		}
		
		checkNo = battle[i].second;
		ans++;
	}

	cout << ans << endl;

}

Measured memory_bytes: 1792
n = gets.to_i

d = Array.new(1001){Array.new(1001){0}}
n.times{|i|
  x1,y1,x2,y2 = gets.split.map(&:to_i)
  d[x1][y1] += 1
  d[x1][y2] -= 1
  d[x2][y1] -= 1
  d[x2][y2] += 1
}

max = d[0][0]
1000.times{|i|
  d[0][i+1] += d[0][i]
  max = d[0][i+1] if max < d[0][i+1]
  d[i+1][0] += d[i][0]
  max = d[i+1][0] if max < d[i+1][0]
}
1000.times{|i|
  1000.times{|j|
    d[i+1][j+1] += d[i][j+1]
    d[i+1][j+1] += d[i+1][j]
    d[i+1][j+1] -= d[i][j]
    max = d[i+1][j+1] if max < d[i+1][j+1]
  }
}

p max

Measured memory_bytes: 16984
# Problem C - Subarray Sum

# input
N, K, S = map(int, input().split())

# initialization
ans_list = [0]*(N)

# check
for i in range(K):
    ans_list[i] = S
for i in range(K, N):
    if S==10**9:
        ans_list[i] = S - 1
    else:
        ans_list[i] = S + 1

# output
print(" ".join(list(map(str, ans_list))))


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

int main()
{
 int t;
  cin>>t;
  bool flag=true;
  while(t--)
  {
    int n;
    cin>>n;
    if(flag&&(n&1)==0)
    {
    	//cout<<n;
      if(n%3!=0&&n%5!=0)
      {
        flag=false;
        //cout<<n<<'\n';
      }
    }
  }
  if(flag)
  cout<<"APPROVED\n";
  else
    cout<<"DENIED\n";
  
  return 0;
}


Measured memory_bytes: 256
require "prime"
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
p=Prime.prime_division(N)
if p==[]
    puts 0
    exit
end
#p p
ans=0
p.each do|x,y|
  i=1
  while y-i>=0
    y-=i
    i+=1
  end
  ans+=i-1
end
puts ans

Measured memory_bytes: 14448
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUF_SIZE 13

int get_str(char *str, int size) {
    if(!fgets(str, size, stdin)) return -1;
    return 0;
}

int table[256] = {
    ['A'] = 1,
    ['T'] = 1,
    ['G'] = 1,
    ['C'] = 1,
};

#define max(a, b) ((a) > (b) ? (a) : (b))

int main(void) {
    char str[BUF_SIZE];
    get_str(str, BUF_SIZE);
    size_t len = strlen(str);

    int ans = 0;
    int idx = 0;
    int count = 0;
    while(idx<=len) {
        // skip
        while(table[(int)str[idx++]]) count++;
        // do something
        ans = max(ans, count);
        count = 0;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = inpl()
a.sort()
bc = [inpl() for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse = True)
ind = -1
now = -1
cnt = 0
for i in range(n):
    if cnt == 0:
        ind += 1
        if ind >= m: break
        cnt, now = bc[ind]
    if a[i] >= now:
        break
    a[i] = now
    cnt -= 1
print(sum(a))

Measured memory_bytes: 34336
#include <bits/stdc++.h>
#define rep2(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;
template <typename T>
T sq(T x) {
  return x * x;
}

signed main() {
  int N, K;
  int ans = 0;
  cin >> N >> K;
  rep(i, N) {
    int x;
    cin >> x;
    ans += min(2 * x, 2 * (K - x));
  }

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


Measured memory_bytes: 3608
import sys

input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if self.rank[x] > self.rank[y]:
            self.parent[root_y] = root_x
        elif self.rank[x] < self.rank[y]:
            self.parent[root_x] = root_y
        elif root_x != root_y:
            self.parent[root_y] = root_x
            self.rank[x] += 1
        pass


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uf = UnionFind(n)
for a, b in ab:
    uf.unite(a - 1, b - 1)

roots = [0] * n
for i in range(n):
    roots[uf.root(i)] += 1
ans = max(roots)

print(ans)

Measured memory_bytes: 112472
#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() {
  
  lint n, m; cin >> n >> m;
  lint sum = 0;
  for (int i = 0; i < m; i++) {
    lint a; cin >> a;
    sum += a;
  }
  
  n -= sum;
  if (n >= 0) cout << n << endl;
  else cout << -1 << endl;
  return 0;
}


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

int main() {
  string n;
  ll result = 0;
  ll d;
  cin >> n >> d;
  string ans;
  rep(i, n.length()) {
    result += n[i] - '0';
  }
  if (result % 9 == 0) {
  	cout << "Yes" << endl;
  } else {
  	cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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

int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}



int main(){
  string s;
  cin >> s;
  bool f = true;
  if(s[0] == s[1] && s[1] == s[2]) f = false;
  cans(f);
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    static public int minFallingPathSum(int[][] A) {
        int arr[][] = new int[A.length][A[0].length];
        for (int i = 0 ; i<A[0].length;i++) {
            arr[0][i] = A[0][i];
        }
        for (int i = 1 ; i<A.length;i++) {
            for (int j = 0 ; j<A[i].length;j++) {
                int min = Integer.MIN_VALUE;
                for (int k =0 ; k<A[i].length ;k++) {
                    
                    if(k!=j) {
                        min = Math.max(arr[i-1][k], min);
                    }
                }
                                

                     arr[i][j] = min +A[i][j];
                
            }
        }
     int min = Integer.MIN_VALUE;
        
        for(int i=0 ;i<arr[0].length;i++) {
           // System.out.println(arr[arr.length-1][i]);
            if(min<arr[arr.length-1][i]) {
            min = arr[arr.length-1][i];
            }
        }
        return min;
    }
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    //int  k = s.nextInt();
    int arr[][] = new int[n][3];
    for (int i =0 ; i<n ;i++) {
        for(int j =0 ; j<3 ;j++) {
            arr[i][j] = s.nextInt();
        }
    }
    System.out.println(minFallingPathSum(arr));
  
  }
}

Measured memory_bytes: 99024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int d;
int c[26],s[365][26],last[26],t[365];

int main() {
  cin >> d;
  for(int i=0;i<26;i++) {
    cin >> c[i];
  }
  for(int i=0;i<d;i++) {
    for(int j=0;j<26;j++) {
      cin >> s[i][j];
    }
  }
  int score=0;
  for(int i=0;i<d;i++) {
    for(int j=1;j<26;j++) {
      if(s[i][t[i]]<s[i][j]) t[i]=j;
    }
    score+=s[i][t[i]];
    last[t[i]]=i+1;
    for(int j=0;j<26;j++) {
      score-=c[j]*(i+1-last[j]);
    }
  }
  int cnt=100000;
  while(cnt--) {
    int day=rand()%d;
    int v=rand()%26;
    if(t[day]==v) continue;
    int dscore=0;
    int check[2]={v,t[day]};
    int pscore=0;
    int cscore=0;
    for(int i=0;i<2;i++) last[check[i]]=0;
    for(int i=0;i<d;i++) {
      pscore+=s[i][t[i]];
      last[t[i]]=i+1;
      for(int j=0;j<2;j++) {
        int id=check[j];
        pscore-=c[id]*(i+1-last[id]);
      }
    }
    for(int i=0;i<2;i++) last[check[i]]=0;
    for(int i=0;i<d;i++) {
      if(day==i) {
        cscore+=s[i][v];
        last[v]=i+1;
      }
      else {
        cscore+=s[i][t[i]];
        last[t[i]]=i+1;
      }
      for(int j=0;j<2;j++) {
        int id=check[j];
        cscore-=c[id]*(i+1-last[id]);
      }
    }
    if(pscore<cscore) {
      t[day]=v;
    }
  }
  for(int i=0;i<d;i++) {
    cout << t[i]+1 << endl;
  }
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define mod 1000000007
using ll = long long;
using namespace std; 
const double pi = acos(-1);

int main() {
    string s; cin >> s;
    int d=s.size();
    vector<string> a(d);
    vector<int> aa;
    ll ans=0;
    int ss=d;
    for (int i=0;i<d;i++){
        a[i]=s[i];
    } 
    for (int i=0;i<(1<<d-1);i++){
        for (int j=0;j<d-1;j++){           
            if (i&(1<<j)){
                string f;
                for (int k=d-1-j;k<ss;k++){
                    f+=a[k];
                }
                ll ff=stoll(f);
                ans+=ff;
                ss=d-1-j;
            }
        }
        string g;
        for (int k=0;k<ss;k++){
            g+=a[k];
        }
        ll ff=stoll(g);
        ans+=ff;
        ss=d;
    }
    cout << ans << "\n";
}


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

int Solve(int a,int b,int c){

  if(c*c < a*a+b*b )return 1;
  if(c*c == a*a+b*b)return 0;
  else return 2;

}

int main(){

  int sum[]={0,0,0};
  vector< int > a(3);

  while(cin>>a[0]>>a[1]>>a[2]){
    sort(a.begin(),a.end());

    if(a[0]+a[1] > a[2]){
      sum[ Solve(a[0],a[1],a[2]) ] ++;
    }
    else{
      break;
    }

  }

  cout << sum[0]+sum[1]+sum[2] << ' ' << sum[0] << ' ' << sum[1] << ' ' << sum[2] << endl;

  return 0;
}

Measured memory_bytes: 1208
#include<stdio.h>
#define rep(i, n) for (int i = 0; i <= (int)(n); i++)

int findsum(int n){//入力した値の各和の合計を出す
  int sum = 0;
  while(n > 0){
    sum += n %10;
    n = n/10;
  }
  return sum;
}
int main(){
  int A,B,N;
  scanf("%d %d %d", &N,&A, &B);
  int total = 0;
  rep(i,N){
    int sum = findsum(i);
    if(sum >=A && sum <= B){
      total += i;
    }
  }
  printf("%d\n", total);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>
#include <functional>

typedef long long ll;
using namespace std;


int main(){
    string s, t;
    cin >> s >> t;
    int cnt = 0;
    for(int i = 0; i < s.length() - t.length() + 1; i++){
        int new_cnt = 0;
        for(int j = 0; j < t.length(); j++){
            if(t[j] == s[i + j]) new_cnt++;
        }
        cnt = max(cnt, new_cnt);
    }
    cout << t.length() - cnt << endl;
}

Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
int x,b,t,ans=0,a,i;
scanf("%d%d%d",&x,&b,&t);
for(i=1;i<=20;i++)
{
    a=i*x;
    if(a>=t+1){break;}
    ans=ans+b;

}
printf("%d",ans);
}


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

int main(){
    ll H,W;
    cin >> H >> W;
    ll H1 = ll(H/2.0+0.6);
    ll H2 = ll(H/2.0);
    ll W1 = ll(W/2.0+0.6);
    ll W2 = ll(W/2.0);
    ll cnt = 0;
    if(H == 1 || W == 1){
        //cnt += W1;
        cout << 1 << endl;
        return 0;    
    }

    cout << W1*H1 + W2*H2 << endl;
}


Measured memory_bytes: 256
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    ll N;
    cin >> N;

    vector<ll> A(N);
    FOR(i, 0, N){
        cin >> A.at(i);
    }

    ll min_cost = inf;
    FOR(m, -100, 101){
        ll cost = 0;
        FOR(i, 0, N){
            ll diff = A[i] - m;
            cost += diff * diff;
        }
        min_cost = min(min_cost, cost);
    }
    
    p(min_cost);
    
    return 0;
}

Measured memory_bytes: 256