akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

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

        final int A = Integer.parseInt(sc.next());
        final int B = Integer.parseInt(sc.next());

        out.println(A * B - (A + B) + 1);

        out.flush();
    }
}

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

using namespace std;

int MAX_N = 100;

int main()
{
    long long N,K;
    long long up=0,btm=0;
    long long tmp;
    long long ans=0;

    cin >> N >> K;

    for (int i = 0; i < K; i++)
    {
        btm += i;
        up += N-i;
    }
    long long btm_num = K-1, up_num = N-K+1;

    while (btm!=up)
    {
        ans += up - btm + 1;


        btm_num++;
        up_num--;

        btm += btm_num;
        up += up_num;
    }

    ans++;

    cout << ans%(1000000000+7) << endl;


    return 0;
}

Measured memory_bytes: 3636
n = int(input())
li = []
for _ in range(n):
    a, b = map(float, input().split())
    li.append((a,b))
    
sum_ = 0
for i in range(n):
    for j in range(n):
        if i > j:
            sum_ += ((li[i][0]-li[j][0])**2 + (li[i][1]-li[j][1])**2)**0.5

print((2*sum_)/float(n))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
typedef long long ll;
#define vstroku() to_string()
#define vchislo() to_ulong()
#define gcd(x,y) __builtin_gcd(x,y)
#define numberof1(x) __builtin_popcount(x)
#define povsemelementam(i,mnozh) for(auto i: mnozh)
#define podotrezok(i,j) substr(i-1,j) // like prefix sum, (i,j)=s[j]-s[i-1]
#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back 
#define pii pair <int, int>
#define F first
#define S second
#define mipletsplay ios_base::sync_with_stdio(0); cin.tie(0); 


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 3e5;
const ll INF = 1e9;
const ll kek=998244353;

int main() {
mipletsplay;
int n;
cin>>n;
cout<<n*n*n;}

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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> bool chmax(T& a,const T& b){return a < b ? (a = b,true) : false;}
template<typename T> bool chmin(T& a,const T& b){return b < a ? (a = b,true) : false;}
typedef long long ll;

ll N,K;
const ll MOD = 11;

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

	cin >> N >> K;
	if(N < 3){
		cout << 0 << endl;
		return 0;
	}
	N = (N - 2) * 7;

	ll ans = 0;
	for(ll i = 1;i <= 5;i++){
		vector<ll> A(MOD);
		FOR(j,0,MOD){
			A [j] = (9 * (i + 8 + j * 7)) % MOD;
		}
		ans += (N - i) / 77;
		FOR(j,0,MOD) if(j * 7 <= (N - i) % 77){
			ans += A [j] == K;
		}
	}
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
def selectionSort(A, N):
    c = 0
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j] < A[minj]:
                minj = j
        if A[i] != A[minj]:
            A[i],A[minj] = A[minj],A[i]
            c += 1
    return A,c
num = int(input())
li1 = [int(e) for e in input().split()]
li2 = selectionSort(li1,num)
print(*li2[0],sep=" ")
print(li2[1])


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int M;
int A[101010],B[101010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<101010> uf;
ll ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll cur=1LL*N*(N-1)/2;
	FOR(i,M) {
		cin>>A[i]>>B[i];
	}
	
	for(i=M-1;i>=0;i--) {
		ret[i]=cur;
		if(uf[A[i]]!=uf[B[i]]) {
			cur-=1LL*uf.count(A[i])*uf.count(B[i]);
			uf(A[i],B[i]);
		}
	}
	FOR(i,M) cout<<ret[i]<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main() {
	char n[4];
	for (int i = 0; i < 4; i++) cin >> n[i];

	if (n[0] == n[1] && n[1] == n[2]) cout << "Yes" << endl;
	else if (n[1] == n[2] && n[2] == n[3]) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

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

int n, h, a, ma, ans, b[100005];
int main() {
	int i;
	scanf("%d%d", &n, &h);
	for(i=0; i<n; i++) {
		scanf("%d%d", &a, &b[i]);
		ma = max(ma, a);
	}
	sort(b, b+n);
	for(i=n-1; i>=0 && h>0; i--) {
		ans++;
		h -= max(b[i], ma);
	}
	if(h>0) ans += (h+ma-1) / ma;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define SZ(X) ((int)(X).size())
#define endl "\n";
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	string s;
	cin>>s;
	bool easy=0;
	for (int i = 0; i <SZ(s); ++i)
		{
			bool x = (i%2==0);


			if(x&&s[i]=='L') {
				puts("No");
				return 0;
			} 
			if(!x&&s[i]=='R'){
				puts("No");
				return 0;
				
			}

		}	
    puts("Yes");
   return 0;
}


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

int main(){
    int n; cin>>n;
    set<int> s;
    rep(i, n){
        int x; cin >> x;
        s.insert(x);
    }
    if(n == s.size()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 12932
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	var t string
	fmt.Scan(&s)
	fmt.Scan(&t)
	sliceS := strings.Split(s, "")
	sliceT := strings.Split(t, "")

	i := 0
	ans := len(sliceT)
	count := 0
	for {
		count = 0
		for j := 0; j < len(sliceT); j++ {
			if sliceS[j+i] != sliceT[j] {
				count++
			}
		}
		if ans > count {
			ans = count
		}
		i++
		if len(sliceS)-(len(sliceT)+i) < 0 {
			break
		}
	}
	fmt.Print(ans)

}


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

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

using namespace std;

struct UnionFind {
  vector<int> parent;
  UnionFind (int n) : parent(n, -1) {}
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};

int main() {
  int w,h;
  cin>>w>>h;
  vector<string> t(h);
  REP(i,h) cin>>t[i];
  UnionFind uf(w*h);
  REP(i,h)REP(j,w-1) {
    if (t[i][j] != '#' && t[i][j+1] != '#')
      uf.merge(i*w+j, i*w+j+1);
  }
  REP(i,h-1)REP(j,w) {
    if (t[i][j] != '#' && t[i+1][j] != '#')
      uf.merge(i*w+j, (i+1)*w+j);
  }
  int ti=0,tj=0;
  REP(i,h)REP(j,w) {
    if(t[i][j] == 't') {
      ti=i;tj=j;
    }
  }
  int n;
  cin>>n;
  bool ok = false;
  REP(i,n) {
    if (uf.root(0) == uf.root(ti*w+tj)) {
      cout << i << endl;
      ok = true;
      break;
    }
    int x,y;
    cin>>x>>y;
    t[y][x] = '.';
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};
    REP(j,4) {
      int nx=x+dx[j], ny=y+dy[j];
      if(nx<0||nx>=w||ny<0||ny>=h)continue;
      if(t[ny][nx] != '#')
        uf.merge(y*w+x, ny*w+nx);
    }
  }
  if (!ok) {
    if (uf.root(0) == uf.root(ti*w+tj)) {
      cout << n << endl;
    } else {
      cout << -1 << endl;
    }
  }
  return 0;
}

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

using namespace std;

vector<int> dx = {0,-1,0,1};
vector<int> dy = {1,0,-1,0};

int main(void){
    int h, w;
    cin >> h >> w;
    
    vector<vector<char>> grid(h, vector<char>(w));
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            cin >> grid[i][j];
        }
    }
    
    
    bool check = true;
    
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            
            if (grid[i][j] == '.') continue;
            
            bool temp_check = false;
            
            for (int k = 0; k < 4; k++){
                int nx = i + dx[k];
                int ny = j + dy[k];
                
                if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;
                if (grid[nx][ny] == '#') temp_check = true;
            }
            
            if (temp_check) continue;
            else check = false;
            
        }
    }
    
    if (check){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int L,N,sum;
main()
{
	cin>>L>>N;
	for(int i=0;i<N;i++)
	{
		int x,w;cin>>x>>w;
		sum-=x*w;
	}
	if(sum)cout<<"1\n"<<(sum>0?1:-1)<<" "<<(sum>0?sum:-sum)<<endl;
	else cout<<0<<endl;
}



Measured memory_bytes: 3092
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;
#define lol long long

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using piii = pair<int, pair<int, int>>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;

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

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        sum += A[i];
    }

    auto func = [&](int g) {
        priority_queue<int> que;
        ll res = 0;
        for (int i = 0; i < N; ++i) {
            res += g - A[i] % g;
            que.push(g - A[i] % g);
        }
        int cnt = res / g;
        for (int i = 0; i < cnt; ++i) {
            res -= que.top();
            que.pop();
        }
        return res;
    };

    int ans = 0;
    for (int i = 1; i * i <= sum; ++i) {
        if (sum % i)
            continue;
        if (func(i) <= K)
            ans = max(ans, i);
        if (func(sum / i) <= K)
            ans = max(ans, sum / i);
    }

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


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

using namespace std;

int main() {
	int n, W;
	char dummy;
	int count = 1;

	while( true ) {

		cin >> W;
		if(W == 0) {
			break;
		}
		cin >> n;

		vector< int > item_val(n);
		vector< int > item_wei(n);
		vector< vector< int > > nap(n + 1, vector< int >(W + 1, 0));

		for(int i = 0; i < n; i++) {
			cin >> item_val[i] >> dummy >> item_wei[i];
		}

		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= W; j++) {
				if(j + item_wei[i] <= W) {
					nap[i + 1][j + item_wei[i]] = max(nap[i + 1][j + item_wei[i]], nap[i][j] + item_val[i]);
				}
				nap[i + 1][j] = max(nap[i + 1][j], nap[i][j]);
			}
		}

		int max_weight = W;
		int max_value = 0;
		for(int j = 0; j <= W; j++) {
			if(max_value < nap[n][j]) {
				max_value = nap[n][j];
				max_weight = j;
			}
		}

		cout << "Case " << count << ":" << endl;
		cout << max_value << "\n" << max_weight << endl;
		count++;

	}
}

Measured memory_bytes: 5028
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0)
#define int int64_t
#define ii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>
#define F first
#define S second
#define pb push_back
#define FOR(i,l,r) for(int i=l; i<r; ++i)
#define ROF(i,r,l) for(int i=r; i>l; --i)
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define test int t; cin >> t; while(t--) solve();

using namespace std;
typedef long long ll;

const int MAXN = 2000005;
const int MAXINT = 2147483098;
const int MAXLL = 9223372036854775258LL;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;



int pref[MAXN];



int32_t main()
{
    //freopen("holiday.in", "r", stdin);
    fast;
    //test;

   int n;
   cin >> n;
   vi a(n);
   cin >> a[0];
   pref[0] = a[0];
   FOR(i,1,n) cin >> a[i], pref[i] = (pref[i-1]+a[i])%MOD;
   int ans = 0;
   FOR(i,0,n){
        ans  = (ans+(a[i]*(pref[n-1]-pref[i]+MOD))%MOD)%MOD;
   }
   cout << ans;


   return 0;
}


Measured memory_bytes: 6344
#include<bits/stdc++.h>
using namespace std;
int d,n,x,y,ans;
int main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y;
		double t=sqrt(double(x)*double(x)+double(y)*double(y));
		if(t<=double(d))
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n) for (int i=1; i < (int)(n); i++)
#define rrep(i, n) for (int i=((int)(n)-1); i>=0; i--)
#define rreps(i, n) for (int i=((int)(n)-1); i>0; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using lint = long long;
using p = pair<int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
  lint a, b, n; cin >> a >> b >> n;
  lint ans = floor(a * min((b-1), n) / b);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
s = input()
k = int(input())
subs = []
lens = len(s)
prev = ''
cnt = 0

for i in range(lens):
  for j in range(1,k+1):
    subs.append(s[i:i+j])
subs.sort()
for m in subs:
  if prev != m:
    cnt += 1
  if cnt == k:
    print(m)
    exit()
  prev = m

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

int main() {
  int N;
  int i, j, n, aa;
  vector<int> a(100);
  cin >> N;
  for (i=0; i<N; i++) cin >> a.at(i);
  n = N/2;
  while ( n > 0 ) {
    for (i=n; i<N; i++)
      for (j=i-n; j>=0; j-=n)
        if ( a.at(j) > a.at(j+n) ) {
          aa=a.at(j);
          a.at(j)=a.at(j+n);
          a.at(j+n)=aa;
        }
    n/=2;
  }
  //for (i=0; i<N; i++) cout <<i <<':' <<a.at(i) <<endl;//////////////
  for (aa=0, i=N-1; i>=0; i-=2) aa+=a.at(i);
  //cout <<aa <<endl;
  if (N>1) for (i=N-2; i>=0; i-=2) aa-=a.at(i);
  cout << aa << endl;
}


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

using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;

int dp[maxn][4],a[maxn][4],n;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) for(int j=1;j<=3;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a[i][1];
		dp[i][2]=max(dp[i-1][1],dp[i-1][3])+a[i][2];
		dp[i][3]=max(dp[i-1][1],dp[i-1][2])+a[i][3];
	}
	printf("%d\n",max(dp[n][1],max(dp[n][2],dp[n][3])));
}

Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main(){
  int a,b;
  cin >> a >> b;
  if (a <= 8 && b <= 8){
    cout << "Yay!\n";
  }
  else{
    cout << ":(\n";
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll N,A[200007],sum=0,B=0,C=0,D=0;
  cin >> N;
  rep(i,N){
    cin >> A[i];
    A[i]-=i+1;
  }
  sort(A,A+N);
  ll X,Y;
  if(N%2==1){
    X=A[N/2];
    Y=X;
  }
  else{
    X=(A[N/2]+A[N/2-1])/2;
    Y=X+1;
  }
  rep(i,N){
    B+=abs(X-A[i]);
    C+=abs(Y-A[i]);
  }
  cout << min(B,C) << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
  int n,i,j,k,v,x,cnt=0,m=0;
  int A[1000000];
  int G[1000000];
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    }
  
  G[0]=1;
  for(i=1;G[i-1]<=n;i++){
    m++;
    G[i]=G[i-1]*3+1;
    if(m>100)break;
  }
  for(i=0;i<m/2;i++){
    x=G[i];
    G[i]=G[m-i-1];
    G[m-i-1]=x;
  }
  
  
  for(i=0;i<m;i++){
    for(j=G[i];j<n;j++){
      v=A[j];
      k=j-G[i];
      while(k>=0&&A[k]>v){
	A[k+G[i]]=A[k];
        k=k-G[i];
	cnt++;
      }
      A[k+G[i]]=v;
    }
  }
  
  printf("\n%d\n",m);
  for(i=0;i<m;i++){
    printf("%d ",G[i]);
  }
  printf("\n%d\n",cnt);
  for(i=0;i<n;i++){
    printf("%d\n",A[i]);
    }
  return 0;
}
   

Measured memory_bytes: 5944
h,w=list(map(int,input().split()))
masu=[]
masu.append([])
for i in range(w+2):
  masu[0].append('.')
for i in range(h):
  masu.append([])
  masu[i+1].append('.')
  yoko=input()
  for j in range(w):
    masu[i+1].append(yoko[j])
for i in range(w+2):
  masu[0].append('.')
for i in range(1,h-1):
  for j in range(1,w-1):
    if masu[i][j]=='#':
      if masu[i][j+1]=='.' and masu[i][j-1]=='.' and masu[i+1][j]=='.' and masu[i-1][j]=='.':
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 9252
#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;

class Point {
public:
	double x;
	double y;
};

const double esp = 1e-10;


double Cross(Point p0, Point p1, Point p2) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

int main(void) {
	int n, i;
	double sum;
	Point pointSet[21];
	char c;

	n = 0;
	while (cin >> pointSet[n].x >> c >> pointSet[n].y) {
		n++;
	}

	sum = 0;
	for (i = 1; i < n-1; i++) {
		sum += Cross(pointSet[0], pointSet[i], pointSet[i + 1]);
	}

	cout << fixed << setprecision(6) << sum / 2 << endl;

	return 0;
}




Measured memory_bytes: 3168
#include<iostream>
using namespace std;
int h,w;
long a,ans;
main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>a;
			ans+=a*(i+1)*(j+1)*(h-i)*(w-j);
		}
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 3088
def resolve():
    n = int(input())
    a = list(map(int,input().split()))
    a = sorted(a)
    ans = (a[0]+a[1])/2
    if n==2:
        print(ans)
        exit()
    for i in range(2, n):
        ans = (ans+a[i])/2
    print(ans)
resolve()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#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, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N; cin >> N;
  vector<int> L(N,0);
  REP(i, N) cin >> L[i];
  sort(ALLR(L));
  int sum = 0;
  FOR(i, 1, N) sum += L[i];
  cout << (L[0] < sum ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad
import Control.Monad.Fix
import Data.Int
import Data.List
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: Int -> Int -> Int -> Int
solve !a !b !c = case () of
  () | odd rp && odd rq   -> rp `div` 2 + rq `div` 2 + 1
  () | even rp && even rq -> rp `div` 2 + rq `div` 2
  () | otherwise          -> rp `div` 2 + rq `div` 2 + 2
 where
  [p, q, r] = sort [a, b, c]
  rp        = r - p
  rq        = r - q

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  (a, b, c) <-
    (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2))
    .   VU.unfoldrN 3 readInt
    <$> B.getLine
  print $ solve a b c


Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
int main() {
  string a, b, c;
  cin >> a >> b >> c;
  if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


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

typedef pair<int, int> P;

struct Edge {
  int to, cost;
};

int n;
vector<vector<Edge> > G;

vector<int> dij() {
  priority_queue<P, vector<P>, greater<P> > Q;
  vector<int> d(n, -1);
  Q.push({0, 0});
  while ( !Q.empty() ) {
    P p = Q.top(); Q.pop();
    int v = p.second, c = p.first;

    if ( d[v] >= 0 ) continue;
    d[v] = c;
    
    for ( Edge e: G[v] ) {
      Q.push({c+e.cost, e.to});
    }    
  }

  return d;
}

int main() {
  cin >> n;

  G = vector<vector<Edge> >(n);
  for ( int i = 0; i < n; i++ ) {
    int u, k;
    cin >> u >> k;
    for ( int i = 0; i < k; i++ ) {
      int v, c;
      cin >> v >> c;
      G[u].push_back({v, c});      
    }
  }

  vector<int> d = dij();
  for ( int i = 0; i < n; i++ ) {
    cout << i << " " << d[i] << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3276
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        Integer[] menu = {Integer.parseInt(sc.next()),
                Integer.parseInt(sc.next()),
                Integer.parseInt(sc.next()),
                Integer.parseInt(sc.next()),
                Integer.parseInt(sc.next())};

        int result = 0;
        int onesPlace = 10;
        for (int time : menu) {
            result += (int) Math.ceil(time / 10.0) * 10;
            if (time % 10 != 0) {
                onesPlace = Math.min(onesPlace, time % 10);
            }
        }

        System.out.println(result + onesPlace - 10);
    }
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 112345;
int L[MAX_N];
int R[MAX_N];
ll Lsum[MAX_N];
ll Rsum[MAX_N];

int main2() {
  int N = nextInt();
  REP(i, N) {
    L[i] = nextInt();
    R[i] = nextInt();
  }
  sort(L, L+N); reverse(L, L+N);
  sort(R, R+N);

  Lsum[0] = 0;
  REP(i, N) Lsum[i+1] = Lsum[i] + L[i];
  Rsum[0] = 0;
  REP(i, N) Rsum[i+1] = Rsum[i] + R[i];

  ll ans = 0;
  for (int i = 0; i <= (N+1)/2; i++) {
    for (int j = i-1; j <= i+1; j++) {
      if (0 <= i && i <= N && 0 <= j && j <= N) {
        ll cur = 2*(Lsum[i] - Rsum[j]);
        chmax(ans, cur);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
signed main(void) {
    string s;
    int Q;
    cin >> s >> Q;
    bool judge = true;        //trueで1→先頭に追加
    string s0 = "", s1 = "";  //s0が先頭
    rep(i, Q) {
        int t;
        cin >> t;
        if(t == 1) {
            judge = !judge;
        } else {
            int f;
            char a;
            cin >> f >> a;
            if(judge) {
                if(f == 1)
                    s0 += a;
                else
                    s1 += a;
            } else {
                if(f == 1)
                    s1 += a;
                else
                    s0 += a;
            }
        }
    }
    if(judge) {
        reverse(all(s0));
        cout << s0 + s + s1 << endl;
    } else {
        reverse(all(s));
        reverse(all(s1));
        cout << s1 + s + s0 << endl;
    }
}


Measured memory_bytes: 1348
#include <bits/stdc++.h>
#define rep(i, n) for(ll i=0;i<n;i++)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (b>a) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 2LL << 60;
using ll = long long;
using P = pair<ll, ll>;

int main(int argc, char const *argv[]){
    ll n;
    cin >> n;
    ll ans=0;
    ll w=10;
    ll preans=1;
    if(n%2==1){
        ans=0;
    }else{
        while(preans>0){
            preans=n/w;
            ans+=preans;
            w*=5;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main()
{
    int n;
    cin >> n;
    int A[n][n] = {};
    rep(i, 0, n) {
        int u, k;
        cin >> u >> k;
        rep(j, 0, k) {
            int v;
            cin >> v;
            A[u - 1][v - 1] = 1;
        }
    }
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (j == n - 1) cout << A[i][j] << endl;
            else cout << A[i][j] << " ";
        }
    }
    return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,p[1<<17],r[1<<17],c[1<<17];
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)p[i]=i,r[i]=1;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		c[x]++,c[y]++;
		x=find(x),y=find(y);
		if(x!=y)p[y]=x,r[x]+=r[y];
	}
	for(int i=0;i<k;i++){
		cin>>x>>y;
		if(find(x)==find(y))c[x]++,c[y]++;
	}
	for(int i=1;i<=n;i++)cout<<r[find(i)]-c[i]-1<<" \n"[i==n];
	return 0;
}


Measured memory_bytes: 2560
/*
ID: wangjun30
LANG: C++11
TASK:
*/
#include<iostream>
#include<algorithm>
#include<array>
#include<unordered_map>
#include<map>
#include<set>
#include<list>
#include<stack>
#include<unordered_set>
#include<vector>
#include<bitset>
#include<queue>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
//#include<fstream>
#define int long long
using namespace std;
//ifstream cin(".in");
//ofstream cout(".out");
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int m;
	cin>>m;
	cout<<10-m/200;
	return 0;
}

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    	if(a==b && b==c)
    	{
    		cout<<1<<"\n";
    	}
    	else if(a!=b && a!=c && b!=c)
    	{
    		cout<<3<<"\n";
    	}
    	else
    	{
    	 cout<<2<<"\n";
    	}
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str  = sc.nextLine();
        String[] astr = str.split(" "); //状況に合わせて
        Boolean flag  = true;
        int[] in_data = Stream.of(astr).mapToInt(x->{
            try{
                return Integer.parseInt(x);
            }
            catch(Exception e){
                e.printStackTrace();
            }
            return 0;
        }).toArray();
        sc.close();
        int n = in_data[0];

        for(int i=1;i<10;i++){
            for(int j =0;j<10;j++){
                if(n == i*j){
                    System.out.println("Yes");
                    System.exit(0);
                }
            }
        }
        System.out.println("No");
    }

}

Measured memory_bytes: 28756
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf #-}

import Control.Monad
import qualified Data.ByteString.Char8 as C
import Data.List
import Data.Ord
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

lim = 1000010
main = do
    n <- readLn :: IO Int
    as <- sort<$>r'

    arr <- UM.replicate lim True

    solve arr (-1) as

    arrF <- U.freeze arr

    print =<< count arr as 0


solve :: UM.IOVector Bool -> Int -> [Int] -> IO ()
solve arr lst [] = return ()
solve arr lst (a:as)
    | lst == a  = do
        UM.write arr a False
        solve arr lst (dropWhile (==a) as) 
solve arr lst (a:as) = do
    b <- UM.read arr a
    when b $
        forM_ [a*2,a*3..lim-1] (\i -> UM.write arr i False)
    solve arr a as

count :: UM.IOVector Bool -> [Int] -> Int -> IO Int
count arr [] ac = return ac
count arr (a:as) !ac = do
    b <- UM.read arr a
    if b then count arr as (ac+1)
            else count arr as ac
    




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

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 ll INF = 1LL << 60;

//---main---------------------------------------------
int main(){
    //main
    int L,R,d;
    cin >> L >> R >> d;
    int ans = 0;
    for(int i = L;i<=R; i++) if(i%d == 0) ans++;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3588
#include <iostream>

using namespace std;

long long f(long long n, long long x){
	if (n == -1){
		return 0;
	}
	return n / x + 1;
}

int main(){
	long long a, b, x;
	cin >> a >> b >> x;

	cout << f(b, x) - f(a - 1, x) << endl;
	return 0;
}


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

int main() {
    ll a,b,v,w,t;
    cin>>a>>v>>b>>w>>t;
    ll d1 = abs(a - b);
    ll d2 = (v - w) * t;
    cout<<(d1 <= d2 ? "YES" : "NO")<<"\n";
}

Measured memory_bytes: 3592
#include<iostream>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;

int main()
{
    int a[5];
    rep(i,5){
        cin >> a[i];
        if(a[i] == 0){
            cout << i + 1 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3616
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

typedef long long int int64;
typedef vector<int64> VI64;
typedef vector<pair<int64,int64>> VII64;
typedef vector<string> VS;
typedef vector<vector<int64>> VVI;

int main()
{
    IOS;
    int64 T=1;
    //cin>>T;
    while(T--)
    {
        int64 n;
        cin>>n;
        cout<<((n-1)*(n))/2;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int a , b , c;
    cin >> a >> b >> c;
    if(b >= c) {
        cout << b + c;
    }
    else {
        int ans = b;
        c -= b;
        c --;
        ans += b + 1;
        ans += min(a , c);
        cout << ans;
    }

    return 0;
}


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

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

last_date = []
for i in 1..26 do
  last_date.push(0)
end

for i in 1..D do
  max_satis = - Inf
  best_contest = 0
  for k in 1..26 do
    now_satis = 0
    now_satis += lines[i+1][k-1]
    now_satis += lines[1][k-1] * (i - last_date[k-1])
    if now_satis > max_satis then
      max_satis = now_satis
      best_contest = k
    end
  end
  last_date[best_contest-1] = i
  if i < D then
    puts best_contest
  else
    print best_contest
  end
end

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

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


Measured memory_bytes: 256
import sys
from fractions import gcd

sys_input = sys.stdin.readline

N, X = map(int, sys_input().split())
xxx = list(map(int, sys_input().split()))
xxx = list(map(lambda x: abs(x-X), xxx))

dp = [None] * N
dp[0] = xxx[0]

for i, x in enumerate(xxx):
    if i == 0:
        continue
    dp[i] = gcd(dp[i-1], x)

print(dp[N-1])


Measured memory_bytes: 16276
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


def comb(n, m):
    r = 1
    for i in range(1, n+1):
        r *= i
    for i in range(1, m+1):
        r //= i
    for i in range(1, n-m+1):
        r //= i
    return r


N, P = map(int, input().split())
A = [int(n) % 2 for n in input().split()]
cnt0 = len([a for a in A if a == 0])
cnt1 = len([a for a in A if a == 1])
ans = 0
if odd(P):
    for i in range(cnt1 + 1):
        if odd(i):
            ans += comb(cnt1, i)
else:
    for i in range(cnt1 + 1):
        if even(i):
            ans += comb(cnt1, i)
ans *= pow(2, cnt0)
print(ans)


Measured memory_bytes: 76712
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n,m,ans;
    scanf("%lld%lld",&n,&m);
    ans=m;
    ll mm=sqrt(m);
    for(int i=1;i<=mm;i++)
    if(m%i==0){
        ll tmp=i;
        if(tmp>=n) ans=min(ans,tmp);
        tmp=m/i;
        if(tmp>=n) ans=min(ans,tmp);
    }
    printf("%lld\n",m/ans);
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    private void solve() {
        long n = sc.nextLong();
        long m = n - 1;

        long x = 2;
        long ans = n == 2 ? 1 : 2;
        while (x * x < m) {
            if (m % x == 0) {
                ans += 2;
            }

            ++x;
        }

        if (x * x == m) {
            ++ans;
        }

        x = 2;
        while (x * x <= n) {
            if (n % x == 0) {
                long y = n;
                while (y % x == 0) {
                    y /= x;
                }
                if (y % x == 1) {
                    ++ans;
                }
            }
            ++x;
        }

        out.println(ans);
    }

    private static PrintWriter out;
    private static MyScanner sc;

    private static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        private MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

    public static void main(String[] args) {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        sc = new MyScanner();
        new Main().solve();
        out.close();
    }
}


Measured memory_bytes: 32900
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int N, K, i, j;
    cin >> N >> K;
 
    long long int A[N];
    long long int B[N-K+1];
    for(i=0;i<N;i++)cin>>A[i];

    for(i=0;i<N-K;i++){

      //cout << A[i] << " " << A[K+i] << endl;
      if (A[i]<A[K+i]){
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }
 
}

Measured memory_bytes: 5200
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] arr = new int[n];
      for(int i = 0; i < n; i++)
        arr[i] = sc.nextInt();

      int nextNum = 1;
      for(int i = 0; i < n; i++) {
        if(arr[i] == nextNum)
          nextNum++;
      }
      System.out.println(nextNum == 1 ? -1 : n - nextNum + 1);
  }
}

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

bool beki[1000];

int main()
{
    int N;
    string S;
    int ans = 0;
    int mem = 0;
    cin >> N >> S;
    for (int i = 0; i < N; ++i)
    {
        if (S[i] == 'I')
        {
            ++mem;
        }
        else
        {
            --mem;
        }
        ans = max(ans, mem);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int h,w,n,sr,sc;
string s,t;
int main(){
    cin>>h>>w>>n>>sr>>sc;
    cin>>s>>t;
    int y,x;
    y=sr;
    rep(i,n){
        if(s[i]=='D') ++y;
        if(y>h){
            cout<<"NO"<<endl;
            return 0;
        }
        if(t[i]=='U'&&y>1) --y;
    }
    y=sr;
    rep(i,n){
        if(s[i]=='U') --y;
        if(y<1){
            cout<<"NO"<<endl;
            return 0;
        }
        if(t[i]=='D'&&y<h) ++y;
    }
    x=sc;
    rep(i,n){
        if(s[i]=='R') ++x;
        if(x>w){
            cout<<"NO"<<endl;
            return 0;
        }
        if(t[i]=='L'&&x>1) --x;
    }
    x=sc;
    rep(i,n){
        if(s[i]=='L') --x;
        if(x<1){
            cout<<"NO"<<endl;
            return 0;
        }
        if(t[i]=='R'&&x<w) ++x;
    }
    cout<<"YES"<<endl;
    return 0;
}


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

int main() {
	int N;
	cin >> N;
	vector<vector<int>> cnt(10, vector<int>(10));

	for (int i = 1; i <= N; i++) {
		string S = to_string(i);
		cnt.at(S.at(0) - '0').at(S.back() - '0')++;
	}
	
	int ans = 0;
	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			ans += cnt.at(i).at(j) * cnt.at(j).at(i);
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using P = pair<int,int>;
using ll = long long;
static const int INF = 1000000000;
static const ll MOD = 1000000007;

int main(){
	string s;
	cin >> s;
	vector<char> cube;
	
	ll ans = 0;
	for(char c : s){
		if(cube.size() == 0 || cube.back() == c){
			cube.push_back(c);
		}
		else{
			cube.pop_back();
			ans += 2;
		}
	}
	
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 640
s = input()
#グー、パーを出した回数
count_g, count_p = 0, 0

#勝った回数
vict = 0

for i in range(len(s)):
  if s[i] == "g" and count_p >= count_g:
    #グーを出してあいこ
    count_g += 1
  elif s[i] == "g" and count_p < count_g:
    #パーを出して勝つ
    vict += 1
    count_p += 1
    
  elif s[i] == "p" and count_p >= count_g:
    #グーを出して負ける
    vict -= 1
    count_g += 1
  elif s[i] == "p" and count_p < count_g:
    #パーを出してあいこ
    count_p += 1

print(vict)

Measured memory_bytes: 3316
#!/usr/bin/env python3
#ABC118 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

M = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = list(map(int,input().split()))
A = [[i,M[i]] for i in a]
A.sort(key = itemgetter(1))

#dp[i] := ちょうどマッチi本を使ってできる最大桁数
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(n):
    for j,k in A:
        if i + k < n+1:
            if dp[i] < 0:
                continue
            dp[i+k] = dp[i] + 1
A.sort(key = itemgetter(0),reverse = True)
ans = ''
k = n
while 1:
    for i,j in A:
        if k - j < 0:
            continue
        if dp[k-j] == dp[k]-1:
            ans += str(i)
            k -= j
            break
    else:
        break
print(ans)


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

int main(){
  int N;
  cin >>N;
  vector<int> B(N-1);
  int ans=0;
   for(int i=0;i<N-1;i++){
    cin >>B.at(i);
  }
   int Bf=B.at(0);
   int Be=B.at(N-2);

   for(int i=1;i<N-1;i++){
	   ans+=min(B.at(i),B.at(i-1));
   }

  cout <<Bf+ans+Be<<endl;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
list=[]
for i in range(n):
    a,b=map(int,input().split())
    list.append([a,b])
list.sort()
sum=0
for x in list:
    sum+=x[1]
    if sum >=k:
        print(x[0])
        break
    

Measured memory_bytes: 20104
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))
#define DEBUG 0

void solve()
{
    ll N, K;
    cin >> N >> K;
    //vector<ll> A(N);
    //for1(i,N) cin >> A[i];
    if (K == 1) {
        cout << 0 << endl;
    } else {
        cout << (N-K+1) - 1 << endl;
    }
}

int main()
{
    do {
        solve();
    } while (DEBUG);
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 5000
#define MAX(a, b) ((a)>(b)?(a):(b))

short nail[N+1][N+1];

int main(void) {
    int m, n, a, b, x, i, j;
    int ans = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &x);
        nail[a][b] = x + 1;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            nail[i][j] = MAX(nail[i][j],
                    MAX(nail[i-1][j], nail[i-1][j-1])-1);
            ans += nail[i][j] > 0;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 48276
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
using namespace std;
  
 
  
int main(){
  
    int n; 
	int r[1000],w[1000];
	int sum_r=0,sum_w=0,idx=0;
    while(scanf("%d",&n),n){
 		
		sum_r=sum_w=idx=0;
		for(int i=0;i<n;i++){
			scanf("%d %d",&r[i],&w[i]);
			sum_r+=r[i];
			sum_w+=w[i];
			if(r[idx]<r[i]) idx=i;
		}
 
		int r0=r[idx],r=sum_r-r0;
		w[idx]=0;

        if(r0 <= r){
            cout<<sum_r+sum_w<<endl;
        }else{
 
            int res=2*r0;
            vector<vector<bool> > dp(1001,vector<bool>(1000,false));
 
            dp[0][0]=true;
            for(int i=0;i<n;i++){
                for(int j=0;j<=1000;j++){
                    if(dp[i][j]){
                        dp[i+1][j]=true; 
                        if(j+w[i]<=1000)
                            dp[i+1][j+w[i]]=true; 
                    }
                }
            }
 
            int opt=r0-r;
			while(!dp[n][opt]) opt--;
 
            res+=sum_w-opt;
            printf("%d\n",res);
 
 
 
        }
         
         
    }
}

Measured memory_bytes: 3348
#include <bits/stdc++.h>
#define arep(a,i,n) for(ll i=(a);i<(n);i++)
#define rep(i,n) for(ll i=0;i<(n);i++)
#define cinf(x,n) for(ll i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(ll i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

ll ans;

int main(){
	ll x,k,d;
	cin >> x >> k >> d;
	ll q = x/d;
	ll r = x%d;
	ans = x;
	if(x>0){
		if((k-q)>=0){
			if((k-q)%2==0)
				ans = r;
			else
				ans = r-d;
		}else{
			rep(i,k){
				ans-=d;
			}
		}
	}else{
		if((k+q)>=0){
			if((k-q)%2==0)
				ans = r;
			else
				ans = r+d;
		}else{
			rep(i,k){
				ans+=d;
			}
		}
	}
	cout << abs(ans) << endl;
}

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

int main() {
    int N;
    ll D;

    cin >> N >> D;
    D = D*D;
    int cnt = 0;
    rep(i,N){
        ll x,y;
        cin >> x >> y;
        ll dis = x*x + y*y;
        if(dis <= D){
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3628
//"BISMILLAHIR RAHMANIR RAHIM"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const long long M = 1000000007 ;
ll fact(ll x, ll y){
    ll f=1,i=1;
    while(i<=y){
        f= f * x;
        f %= M;
        i++;
    }
    return f;
}
int main()
{
   ll n,ans=0;
   cin>>n;
   ans = ((fact(10,n) - 2*fact(9,n)) % M + fact(8,n))%M;
   ans= (ans+M)%M;

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

Measured memory_bytes: 3640