akhauriyash/Code-Regression huggingface dataset:
void main() {
	auto S = rs.to!(dchar[]);
	auto N = S.length;
	bool isParin(dchar[] s) {
		debug writefln(s);
		return s == s.retro.array;
	}
	bool f1 = isParin(S);
	bool f2 = isParin(S[0..(N-1)/2]);
	bool f3 = isParin(S[(N+3)/2 - 1..$]);
	if(f1 && f2 && f3) writeln("Yes");
	else writeln("No");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

int main()
{
	vector<string> vec(2); cin >> vec[0] >> vec[1];

	vector<char> s(vec[0].size());
	for (int i = 0; i < vec[0].size(); i++) s[i] = vec[0].at(i);
	sort(s.begin(), s.end());
	
	vector<char> t(vec[1].size());
	for (int i = 0; i < vec[1].size(); i++) t[i] = vec[1].at(i);
	sort(t.begin(), t.end(), greater<int>());

	vector<string> w(2);

	for (int i = 0; i < s.size(); i++) w[0] += s[i];
	for (int i = 0; i < t.size(); i++) w[1] += t[i];

	string ans = "No";

	if (w[0] < w[1]) ans = "Yes";

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

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    char str[5];
    int a[26] = {0};
    int count = 0;

    scanf("%s", str);

    a[str[0] - 'A']++;
    a[str[1] - 'A']++;
    a[str[2] - 'A']++;
    a[str[3] - 'A']++;

    for (int i = 0; i < 26; i++) {
        if (a[i] == 2) {
            count++;
        }
    }

    if (count == 2) {
        printf("Yes");
    } else {
        printf("No");
    }
    
    

    return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
const int MOD=1e9+7;
const int INF=1e18;
void io(string s="file"){freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}


signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int x;cin>>x;
    if(x==0)cout<<1;
    else if(x==1) cout<<0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(void)
{
    ll n, k;
    cin >> n >> k;
    vector<ll> p(n);
    REP(i,n){
        cin >> p[i];
    }

    ll sum = 0;
    REP(i,k){
        sum += p[i];
    }

    ll sum_max = sum;
    REP(i,n-k){
        sum = sum - p[i] + p[i + k];
        if (sum >= sum_max)
        {
            sum_max = sum;
        }
    }

    printf("%.8lf\n", (double)(sum_max + k) / 2);

    return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
using ll = long long;
using P = pair<int, int>;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a.rbegin(), a.rend());
  int alice = 0;
  int bob = 0;
  rep(i,n){
    if(i%2 == 0) alice += a[i];
    if(i%2 == 1) bob += a[i];
  }
  int ans;
  ans = alice - bob;
  cout << ans << endl;
}

Measured memory_bytes: 3572
L = input()
X = input()
L = L.split()
X = X.split()
for i, val in enumerate(L):
    L[i] = int(val)
for i, val in enumerate(X):
    X[i] = int(val)
times = 0
N = L[0]
M = L[1]
if N >= M:
    times = 0
    print(times)
else:
    #count distance between Xi
    X.sort()
    dis = []
    for i in range(M-1): # M>1
        distance = X[i+1]-X[i]
        dis.append(distance)
    dis.sort()
    times = 0
    for i in range(M-N):
        times += dis[i]
    print(times)

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std;

// int prime[1000001];
// vector<ll> primes;

// void soe() {
//     int i,j;
//     for(i=2;i<1000001;i++) prime[i] = 1;
//     for(i=2;i<=sqrt(1000001);i++) {
//         if(prime[i] == 1) {
//             for(j=i*i;j<1000001;j+=i) {
//                 prime[j] = 0;
//             }
//         }
//     }
//     for(i=2;i<1000001;i++) {
//         if(prime[i]) primes.pb(i);
//     }
// }

int d[10];

bool valid(int n) {
    while(n) {
        if(d[n%10]) return false;
        n/=10;
    }
    return true;
}

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

    ll n,i,sum=0,cost1=0,cost2 = 0;
    cin >> n;
    ll a[n];
    for(i=0;i<n;i++) {
        cin >> a[i];
        sum+=a[i];
    }
    ll d = sum/n, d2 = sum/n;
    if(sum%n) d++;
    for(i=0;i<n;i++) {
        cost1 += (a[i]-d)*(a[i]-d);
        cost2 += (a[i]-d2)*(a[i]-d2);
    }
    cout << min(cost1,cost2) << "\n";
    return 0;
}




Measured memory_bytes: 256
s_origin = input()
s_copy = s_origin[:]
for i in range(1,len(s_origin)+1):
    s_copy = s_copy[:-1]
    if len(s_copy)%2 == 1:
        continue
    else:
        s_left = s_copy[:int(len(s_copy)/2)]
        s_right = s_copy[int(len(s_copy)/2):]
        if s_left == s_right:
            print(len(s_copy))
            break

Measured memory_bytes: 3060
#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;
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 kt(ll a){
  int sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
int ks(ll a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
int main(void){
  char s[7];
  scanf("%s",s);
  if(s[0]=='S'){
    PRS("Cloudy");
  }else if(s[0]=='C'){
    PRS("Rainy");
  }else{
    PRS("Sunny");
  }
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e16+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

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

    string s;
    cin>>s;
    ll ans = 0;
    rep(i,s.size()/2){
        if(s[i]!=s[s.size()-1-i]){
            ans++;
        }

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


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

int main(){
  int n, i;
  unsigned long long li=1, l1=1, l0 = 2;
  cin >> n;
  for(i=1;i<n;i++){
    li = l1 + l0;
    l0 = l1;
    l1 = li;
  }
  cout << li << endl;
}

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

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long a;
	string sb;
	cin >> a >> sb;
	sb.erase(sb.begin() + sb.size() - 3);
	int b = stoi(sb);
	cout << a * b/100;
}



Measured memory_bytes: 3656
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(final String[] args) {
        final FastScanner scanner = new FastScanner(System.in);
        final String s = scanner.next();
        final String t = scanner.next();

        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= s.length() - t.length(); i++) {
            int tmp = 0;
            for (int j = 0; j < t.length(); j++) {
                if (t.charAt(j) != s.charAt(i + j)) {
                    tmp++;
                }
            }
            min = Math.min(min, tmp);
        }

        System.out.println(min);
    }

    private static class FastScanner {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(final InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

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

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }
    }
}


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

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s;
	cin>>s;
	set<char> se;
	for(int i=0;i<s.length();i++)
	{
		se.insert(s[i]);
	}
	if(se.size()==2)
	{
		cout<<"Second"<<'\n';
	}
	else
	{
		int n=s.length();
		if(n==3)
		{
			cout<<"First"<<'\n';
		}
		else
		{
			if(s[0]==s[s.length()-1])
			{
				n-=3;
			}
			else
			{
				n-=2;
			}
			n--;
			if(n%2==0)
			{
				cout<<"First"<<'\n';
			}
			else
			{
				cout<<"Second"<<'\n';
			}
		}
	}
}

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

int main(){
  int N,D,X;
  cin >> N;
  cin >> D >> X;
  vector<int> A(N);

  for(int i = 0; i < N; i++){
   cin >> A[i]; 
  }
  int sum = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < 10000; j++){
      if(j * A[i] + 1 <= D){ sum++; }
    }
  }

  cout << X + sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int dp[4*300000+5];
int n,x,k;
int qry(int ni,int ns,int ne,int nl,int nr)
{
    if(nl<=ns&&ne<=nr)
        return dp[ni];
    if(nr<ns||ne<nl) return 0;
    int mid=ns+(ne-ns)/2;
    int l=ni*2+1,r=ni*2+2;
    int x=qry(l,ns,mid,nl,nr);
    int y=qry(r,mid+1,ne,nl,nr);
    return max(x,y);
}
int upd(int ni,int ns,int ne,int idx,int val)
{
    if(ne<idx||idx<ns) return dp[ni];
    if(ns==ne) return dp[ni]=val;
    int mid=ns+(ne-ns)/2;
    int l=ni*2+1,r=ni*2+2;
    int x=upd(l,ns,mid,idx,val);
    int y=upd(r,mid+1,ne,idx,val);
    return dp[ni]=max(x,y);
}
signed main()
{
   cin>>n>>k;
   int ans=0;
   for(int i=0;i<n;i++)
   {
       cin>>x;
       int q=1+qry(0,0,(int)3e5,max(0,x-k),min((int)3e5,x+k));
        ans=max(ans,q);
       upd(0,0,(int)3e5,x,q);

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



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

struct Node{
    int key;
    Node *right,*left,*parent;
};

Node *root,*NIL;

void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node*)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x!=NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->parent = y;
    if(y==NIL){
        root = z;
    } else {
        if(z->key < y->key){
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u){
    if(u==NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}

void preorder(Node *u){
    if(u==NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
    int n,i,x;
    string com;
    scanf("%d",&n);

    for(i=0;i<n;i++){
        cin >> com;
        if(com=="insert"){
            scanf("%d",&x);
            insert(x);
        } else if(com=="print"){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}

Measured memory_bytes: 26644
#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char s[100], t[100];
    cin.getline(s,100);
    cin.getline(t,100);
    int n=strlen(t);
    strcpy(t+n-1,t+n);
    if(strcmp(s, t)==0)
    {
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main() {
  int h[10];
  for (int i = 0; i < 10; i++) {
    cin >> h[i];
  }
  sort(h, h+10);
  for (int i = 9; i >= 7; i--) {
    cout << h[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3164
import sys
S = input()
n = len(S)
x = int((n-1)/2)
y = int(x/2)
for i in range(x) :
    if S[i] != S[n-i-1] :
        print("No")
        sys.exit()
for j in range(y) :
    if S[j] != S[x-j-1] :
        print("No")
        sys.exit()
    if S[x+j+1] != S[n-j-1] :
        print("No")
        sys.exit()   
print("Yes")

Measured memory_bytes: 9076
#include<stdio.h>
int main()
{
    int ara[1000],a,b,i,j=0,k,n,m,c=0;
    scanf("%d%d",&n,&m);
    long long int s=0;
    for(i=0;i<n;i++)
    {
        scanf("%d",&ara[i]);
        s=s+ara[i];
    }
    double d,f;
     a=(s/(4*m));
    k=(s%(4*m));
    d=k/(4*m);
    if(k>=0.5)
        a++;
    for(i=0;i<n;i++)
    {
        if(ara[i]>=a)
            c++;
    }
    if(c>=m)
    printf("Yes\n");
    else
        printf("No\n");
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[26];
int main() {
	ll n;string s;
	cin>>n>>s;
	for(int i=0;i<n;i++){
		ll now=s[i]-'a';
		a[now]++;
	}
	ll ans=1;
	for(int i=0;i<26;i++){
		ans*=a[i]+1;
		ans%=inf;
	}
	cout << ans-1;
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define debug(x)   cerr<<#x<<" = "<<x<<endl
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
const int inf = 1e18 + 5;
int n,m;
const int nax = 1e5 + 5;
vector<int> adj[nax];
int dp[nax];
int in_degree[nax];
signed main()
{
    IOS
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++)
    {
      cin>>a>>b;
      adj[a].pb(b);
      in_degree[b]++;
    }
    queue<int> Q;
    for(int i=1;i<=n;i++)
    {
      if(in_degree[i] == 0)
      {
        Q.push(i);
        dp[i] = 0;
      }
    }
    while(!Q.empty())
    {
      int tp = Q.front();
      Q.pop();
      for(auto it : adj[tp])
      {
        dp[it] = max(dp[it] , dp[tp] + 1);
        in_degree[it]--;
        if(in_degree[it] == 0) Q.push(it);
      }
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans = max(dp[i],ans);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 7296
import java.util.*;

public class Main 
{
	static long gcd(long a, long b)
	{
		if(a % b == 0)
		{
			return(b);
		}
		else
		{
			return(gcd(b, a % b));
		}
	}
	
	static long lcm(long a, long b)
	{
		return(a * b / gcd(a, b));
	}
	
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		while(stdIn.hasNext())
		{
			long a = stdIn.nextLong();
			long b = stdIn.nextLong();
			if(a < b)
			{
				long temp = a;
				a = b;
				b = temp;
			}
			System.out.println(gcd(a, b) + " " + lcm(a, b));
		}
	}
}

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

using namespace std;
string s;

bool cek(int l, int r) {
	if (l >= r) return 1;
	if (s[l] == s[r]) return cek(l + 1, r - 1);
	else return 0;
}

int main() {
	cin >> s;
	int l1 = s.length();
	if (cek(0, l1 - 1) && cek(0, (l1 - 1) / 2 - 1) && cek(l1 + 3 / 2 - 1, l1 - 1)) cout << "Yes\n";
	else cout << "No\n";
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

const long long int MOD=1e9+7;

long long int modinv(long long int a, long long int m) {
    long long int b = m, u = 1, v = 0;
    while (b) {
        long long int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

long long int comb(long long int i, long long int j) {
    if(i-j<j) j = i-j;
    long long int ret=1;
    for(int k=1; k<=j; k++) {
        ret *= (i-k+1);
        ret %= MOD;
        ret *= modinv(k, MOD);
        ret %= MOD;
    }
    return ret;
}

int main() {
    long long int X, Y;
    cin >> X >> Y;
    if((X+Y)%3) {
        cout << 0 << endl;
    } else {
        if(X<(X+Y)/3 || Y<(X+Y)/3) {
            cout << 0 << endl;
        } else {
            long long int x=(X+Y)/3;
            long long int cnt=0;
            while(X!=x) {
                x++;
                cnt++;
            }
            cout << comb((X+Y)/3, cnt)%MOD << endl;
        }
    }


    return 0;
    
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	
	n=int(input())
	print((n-1)//2)



	

if __name__ == '__main__':
	main()

Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int A = in.nextInt();
		int B = in.nextInt();
		if (A != 1 && B != 1) {
			System.out.println(1);
		} else if (A != 2 && B != 2) {
			System.out.println(2);
		} else if (A != 3 && B != 3) {
			System.out.println(3);
		}
		in.close();
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
char a;
int cnt1=0;
int cnt2=0;
int main(){
  for(int i=0;i<3;i++){
    cin >> a;
    if(a=='5'){
      cnt1++;
    }
    if(a=='7'){
      cnt2++;
    }
  }
  if(cnt1==2 && cnt2 == 1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
def mdc(a, b):
    if b == 0: return a
    return mdc(b, a%b)

def main():
    resp = 0
    k = int(input())
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for w in range(1, k + 1):
                resp += mdc(mdc(i, j), w)

    print(resp)
                
    
main()

Measured memory_bytes: 80320
#include <bits/stdc++.h>
#include <atcoder/dsu>
#include <cstdio>

using namespace std;
using namespace atcoder;

#define ll long long

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
  	int n, m;
  	cin >> n >> m;
  
  	dsu d(n+1);
  
  	long long ans = 0;
  	for(int i = 0; i < m; i++)
    {
     	 ll a, b;
      	 cin >> a >> b;
      	 // if(!d.same(a,b))
         // {
         	// ans++;
           	d.merge(a,b);	
         // }
    }
  	
  	vector<vector<int>> v = d.groups();
  	ans += v.size();
  	
  	cout << ans - 2;
}

Measured memory_bytes: 8852
from collections import defaultdict

V = defaultdict(list)
N = int(input())
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
*c, = map(int, input().split())
c.sort(reverse=True)

root, _ = max(V.items(), key=lambda x:len(x[1]))
visited = [False] * (N+1)
identifier = [0] * (N+1)

p = 0
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    identifier[a] = p

    p+=1

    for i in V[a]:
        if visited[i]:continue
        q.append(i)

cost = 0
visited = [False] * (N+1)
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    p+=1

    for b in V[a]:
        if visited[b]:continue
        cost += min(c[identifier[a]], c[identifier[b]])
        q.append(b)

print(cost)
print(*[c[i] for i in identifier[1:]])

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long N, long long X, long long Y){
    vector<i64> cnt(N + 1);
    rep(i, 1, N + 1){
        rep(j, i + 1, N + 1){
            i64 d = min(j - i, abs(X - i) + abs(Y - j) + 1);
            cnt[d]++;
        }
    }
    rep(i, 1, N){
        cout << cnt[i] << endl;
    }
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long N;
    scanf("%lld",&N);
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    solve(N, X, Y);
    return 0;
}


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

int main(){
	int n;
	scanf(" %d", &n);
	
	for(int i=0; i<n; ++i){
		int k, p;
		scanf(" %d %d", &k, &p);
		
		if(k%p==0) printf("%d\n", p);
		else printf("%d\n", k%p);
	}
	
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

ll n;

int main(){
	while(cin >> n && n){
		vector<ll> v(n);
		rep(i,n)cin >> v[i];
		sort(ALL(v));
		ll ans = 0;
		FOR(i,1,n-1)ans += v[i];
		cout << ans / (n-2) << endl;
	}
}


Measured memory_bytes: 3120
from collections import Counter

def poll(N, S):
  take = []
  counted = Counter(S)
  mode = max(counted.values())
  for i, value in counted.items():
    if value == mode:
      take.append(i)
  newtake = sorted(take)
  for i in range(len(take)):
    print(newtake[i])

N = int(input())
S = []
for i in range(N):
  S.append(input())
poll(N, S)

Measured memory_bytes: 35572
s = input()
n = len(s)

li = [False] * 26

for i in range(n):
    s1 = s[i]
    li[ord(s1) - ord('a')] = True

if n != 26:
    for i in range(26):
        if not li[i]:
            s += chr(ord('a') + i)
            print(s)
            exit()

else:
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
    else:
        for i in range(2,27):
            s2 = s[-i:]
            if not all((s2[j] > s2[j+1] for j in range(i-1))):
                s3 = s2[0]
                s2 = list(s2)
                s2.sort()
                for j in range(i):
                    if s2[j] == s3:
                        print(s[:-i] + s2[j+1])
                        exit()


Measured memory_bytes: 9096
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll a,b;std::cin >> a >> b;
  if(a<=0&&b>=0) std::cout << "Zero" << '\n';
  else if(a>0) std::cout << "Positive" << '\n';
  else{
    // a<0 b<0
    ll num = b - a + 1;
    if(num%2==0) std::cout << "Positive" << '\n';
    else std::cout << "Negative" << '\n';
  }
  return 0;
}


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

using namespace std;
const int MAX=1e5;
int n,arr[MAX+2];
long long dp[MAX+3];

long long solve(int ind){
if(ind>=n) return 1e17;
if(ind==n-1) return 0;
if(dp[ind]!=-1) return dp[ind];
long long ans=1e17;
ans=min(ans,solve(ind+1)+abs(arr[ind]-arr[ind+1]));
ans=min(ans,solve(ind+2)+abs(arr[ind]-arr[ind+2]));
return dp[ind]=ans;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(0);
    return 0;
}


Measured memory_bytes: 4480
a, b = map(int, input().split())
s = input()

ans = 'Yes'

length = len(s)

for x in range(length):
    if x == a:
        if s[x] != '-':
            ans = 'No'
            break
        else:
            continue

    if ('0' > s[x] and s[x] > '9') or s[x] == '-':
        ans = 'No'
        break

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define F(i,a,b) for(int i=a;i<b;i++)
#define RF(i,a,b) for(int i=a;i>b;i--)
#define mp(a,b) make_pair(int a,int b)
#define ll long long
const int mxn=1e5+10,mxm=4e5+10;
const ll modl=998244353;
ll nm,n,m,p,t,k;
int ans,sum;
int a[mxn],b[mxn],h[mxn];
int l,r;
int main(){
    ios_base::sync_with_stdio(false);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    cin>>nm;
//    string s,s1,s2;char c;
    while(cin>>n>>m){
//        priority_queue<dp,vector<dp>,cmp>q;
        n%=m;
        cout<<min(n,m-n);
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int t,flag;
	//freopen("C:\\Users\\国民党\\Desktop\\text.txt", "r", stdin);
	cin >> t;
	while (t--)
	{
		flag = 1;
		int a, b = -1, c = -1;
		for (int i = 1; i <= 10; i++)
		{
			cin >> a;
			if (a > b)
			{
				b = a;
			}
			else if (a > c)
			{
				c = a;
			}
			else
				flag = 0;
		}
		cout << ((flag == 1) ? "YES" : "NO" )<< endl;
	}
	return 0;
}

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

using namespace std;

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

    long result = 0;

    for(int i = 1 ; i <= n ; i++){
        if(i % 3 == 0 || i % 5 == 0){
            
        }else{
            result += i;
        }
    }
    
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long ll;
 
int main() {
  ll n,k;
  cin>>n>>k;
  ll ans=(n/k)*(n/k)*(n/k);
 
  if(k%2==0){
      ll i=0,j=k/2;
      while(n>=j){
           j+=k;
           i++;
      }
     ans+=i*i*i;
  } 
  
  cout<<ans<<endl;
}

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

using namespace std;


using int64 = long long;

int main() {
  int64 T1, T2, A1, A2, B1, B2;
  cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;

  if(A1 < B1) {
    swap(A1, B1);
    swap(A2, B2);
  }

  int64 S = T1 * A1 + T2 * A2;
  int64 T = T1 * B1 + T2 * B2;

  if(S == T) {
    cout << "infinity" << endl;
  } else {
    int64 U = B2 * T2 - A2 * T2;
    if(U % (T - S) == 0) cout << max(U / (T - S) * 2 - 2, 0LL) << endl;
    else cout << max(U / (T - S) * 2 - 1, 0LL) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
const double PI = acos(-1);
const long long INF = (1LL << 60);
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}

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

  ll n;
  cin >> n;
  vector<ll> rate(9);
  for(ll i = 0; i < n; i++){
    ll r;
    cin >> r;
    if(r > 3200) r = 3200;
    rate[r/400]++;
  }

  ll ans = 0;
  for(ll i = 0; i < 8; i++){
    ans += (rate[i] > 0);
  }

  if(ans > 0) cout << ans << ' ' << ans + rate[8] << endl;
  else cout << 1 << ' ' << n << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void) {
  string s;
  cin>>s;
  for(int i = 0 ; i < 4; i++)
    cout <<s[i];
  cout <<" ";
  for (int i = 4; i < 12; i++) {
    cout<<s[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
l, r = map(int, input().split())
min_remaider = 2019

for i in range(l, r):
    for j in range(i + 1, r + 1):
        remaider = (i * j) % 2019
        if remaider < min_remaider:
            min_remaider = remaider
        if min_remaider == 0:
            break
    if min_remaider == 0:
        break

print(min_remaider)


Measured memory_bytes: 2940
#include <stdio.h>

int F[50] = {0};

int fib(int n)
{
    if (F[n] == 0) {    
        return F[n] = fib(n-1) + fib(n-2);
    }
    return F[n];
}

int main()
{
    F[0] = F[1] = 1;
    
    int N;
    scanf("%d", &N);
    printf("%d\n", fib(N));
    
    return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  REP(i, N)
  cin >> A[i];
  vector<int> B(M), C(M);
  REP(i, M)
  cin >> B[i] >> C[i];
  ll ans = 0;
  sort(ALL(A));
  vector<P> CB;
  REP(i, M)
  CB.push_back(P(C[i], B[i]));
  sort(ALL(CB));
  reverse(ALL(CB));
  int pos = 0;
  int cnt = 0;
  int use = 0;
  while (pos < N)
  {
    if (M <= cnt)
    {
      ans += 1ll * A[pos];
      pos++;
      continue;
    }
    if (A[pos] < CB[cnt].first && use < CB[cnt].second)
    {
      ans += 1ll * CB[cnt].first;
      pos++;
      use++;
    }
    else
    {
      ans += 1ll * A[pos];
      pos++;
    }
    if (CB[cnt].second <= use)
    {
      cnt++;
      use = 0;
      continue;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3572
import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    n = int(input())
    XY = [tuple(map(int,input().split())) for i in range(n)]
    XY.sort()
    ans = 0
    SXY = [[0,0,0] for i in range(n)]
    for i in range(n):
        SXY[i][0] = XY[i][0] + XY[i][1] 
        SXY[i][1] = XY[i][0]
        SXY[i][2] = XY[i][1]
    SXY.sort()
    ans = abs(SXY[0][1]-SXY[-1][1])+abs(SXY[0][2]-SXY[-1][2]) 
    SXY = [[0,0,0] for i in range(n)]
    for i in range(n):
        SXY[i][0] = XY[i][1] - XY[i][0] 
        SXY[i][1] = XY[i][0]
        SXY[i][2] = XY[i][1]
    SXY.sort()
    ans = max(ans,abs(SXY[0][1]-SXY[-1][1])+abs(SXY[0][2]-SXY[-1][2])) 
    print(ans)

if __name__=='__main__':
    main()

Measured memory_bytes: 146144
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    int x=0, y=0, t=0;
    for (int i=0; i<N; i++)
    {
        int a, b, ti;
        scanf("%d%d%d", &ti, &a, &b);
        int diff = (ti-t) - (abs(x-a)+abs(y-b));
        if (!(diff >= 0 && diff%2==0 ))
        {
            printf("No\n");
            return 0;
        }
        x = a;
        y = b;
        t = ti;
    }
    printf("Yes\n");
    return 0;
}


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

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().Split();
            var a = int.Parse(s[0]);
            var b = int.Parse(s[1]);

            var sa = new string(Convert.ToChar(a.ToString()), b);
            var sb = new string(Convert.ToChar(b.ToString()), a);
            if(sa.CompareTo(sb) < 0){
                Console.WriteLine(sa);
            }else{
                Console.WriteLine(sb);
            }
        }
    }
}


Measured memory_bytes: 13408
#include <bits/stdc++.h>
#define DIVIDE (1000000000 + 7)

using namespace std;

long long factorial(int n){
	long res = 1;
	for(; n > 0; n--){
		res *= n;	
		res %= DIVIDE;
	}
	return res;
}

int main(){
	int N, M;

	cin >> N >> M;
	if(max(N, M) - min(N, M) > 1){
		cout << 0 << endl;
		return 0;
	}

	long long pattern = factorial(N) * factorial(M) % DIVIDE;
	if(N == M){
		cout << pattern * 2 % DIVIDE << endl;
	}else{
		cout << pattern << endl;
	}

	return 0;
}


Measured memory_bytes: 256
var
  i,j,s,s1,x:longint;
  a:array[1..3] of longint;
begin
  for i:=1 to 3 do for j:=1 to 3 do begin read(x);if i=j then a[i]:=x else s:=s+x;end;
  for i:=1 to 3 do s1:=s1+a[i];
  if s=s1*2 then writeln('Yes') else writeln('No');
end.

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

int main() {
  int s;
  cin >> s;
  int S[4];
  S[0] = s / 1000;
  S[1] = (s - (S[0] * 1000)) / 100;
  S[2] = (s - (S[0] * 1000) - (S[1] * 100)) / 10;
  S[3] = s - (S[0] * 1000) - (S[1] * 100) - (S[2] * 10);
  
  if ((S[0] == 0 && 1 <= S[1] && S[1] <= 9
       || S[0] == 1 && 0 <= S[1] && S[1] <= 2) //S[0]S[1] can be MM
      && (S[2] == 0 && 1 <= S[3] && S[3] <= 9
          || S[2] == 1 && 0 <= S[3] && S[3] <= 2)) //S[2]S[3] can be MM
    cout << "AMBIGUOUS";
  
  else if ((S[0] == 0 && 1 <= S[1] && S[1] <= 9
            || S[0] == 1 && 0 <= S[1] && S[1] <= 2) //S[0]S[1] can be MM
      && (S[2] == 0 && S[3] == 0 || S[2] == 1 && 3 <= S[3] || S[2] >= 2)) //S[2]S[3] can't be MM
    cout << "MMYY";
  
  else if ((S[2] == 0 && 1 <= S[3] && S[3] <= 9
            || S[2] == 1 && 0 <= S[3] && S[3] <= 2) //S[2]S[3] can be MM
      && (S[0] == 0 && S[1] == 0 || S[0] == 1 && 3 <= S[1] || S[0] >= 2)) //S[0]S[1] can't be MM
    cout << "YYMM";
  
  else
    cout << "NA";
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,ans=1000;
    cin>>n;
    long long a[n+1];
    long long min=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n-1;i++){
        if(a[i]<a[i+1]){
            min=ans/a[i];
            ans=ans%a[i];
        }
        ans+=min*a[i+1];
        min=0;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main(){
  int n;
  unsigned long long fib[50];
  
  fib[0] = 1;
  fib[1] = 1;

  cin >> n;

  for(int i = 2;i <= n;i++){
    fib[i] = fib[i-1] + fib[i-2]; 
  }

  cout << fib[n] << endl;

  return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <vector>
#include <list>

using namespace std;


int main() {
	int a;
	string s;
	cin >> a >> s;
	if (a >= 3200)cout << s << endl;
	else cout << "red" << endl;

	return 0;
}

Measured memory_bytes: 256
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define mod 1000000007
#define N 905
//#define int ll
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,num[N],co[N],x,y,g[N][N],vis[N],ans;
inline int ch(int x){
	return x*(x-1)/2;
}
inline void ret(){
	puts("-1");exit(0);
}
int nedge,Next[N*N],head[N],to[N*N];
#define V to[i]
void add(int a,int b){
	Next[++nedge]=head[a];head[a]=nedge;to[nedge]=b;
}
void add_ne(int a,int b){add(a,b);add(b,a);}
bitset <2000> f;
void dfs(int x){
	vis[x]=1;num[co[x]]++;
	go(i,x){
		if (vis[V]){
			if (co[V]==co[x]) ret();
			continue;
		}
		co[V]=co[x]^1;vis[V]=1;dfs(V);
	}
}
signed main(){
	n=read();m=read();
	F(i,1,m){
		x=read();y=read();g[x][y]=g[y][x]=1;
	}
	F(i,1,n){
		F(j,1,n){
			if (i!=j&&g[i][j]==0) add(i,j);
		}
	}
	f[0]=1;
	F(i,1,n){
		if (!vis[i]){
			num[0]=num[1]=0;
			dfs(i);
			f=(f<<num[0])|(f<<num[1]);
		}
	}
	ans=inf;
	F(i,1,n){
		if (f[i]) ans=min(ans,ch(i)+ch(n-i));
	}
	wrn(ans);
	return 0;
}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define mp make_pair 
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define rrep(i,a,b) for(int i = a; i >=b; i--)
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define sq(a) (a)*(a)
#define nl "\n"
#define all(x) (x).begin(),(x).end()
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_set;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using ii = pair<int, int>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using pil = pair<int,ll>;
using vvi = vector<vi>;
using vpi = vector<ii>;

const int N = 100100;
ll mod=1000000007;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	rep(i,0,n-1){
		cin>>a[i];
	}
	//for single loop	
	while(k--){
		vector<int> b(n);
		rep(i,0,n-1){
			int l = max(0, i - a[i]);
			int r = min( n - 1, i + a[i]);
			b[l]++;
			if(r + 1 < n) b[r + 1]--;
		}
		rep(i,1,n-1) b[i] += b[i-1];
		int cnt = 0;
		rep(i,0,n-1) a[i] = b[i];
		rep(i,0,n-1) if(a[i] == n) cnt++;
		if(cnt == n) break;
	}
	rep(i,0,n-1){
		cout<<a[i]<<" ";
	}
	cout<<nl;
	return 0;
}



Measured memory_bytes: 4924
#include<stdio.h>

int binarySearch(int);
int A[1000000], n;

int main(){
  int i,q,k,sum = 0;

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

  scanf("%d", &q);
  for(i=0; i<q; i++){
    scanf("%d", &k);
    if(binarySearch(k)) sum++;
  }
  printf("%d\n", sum);
  return 0;
}

int binarySearch(int key){
  int left = 0, right = n, mid;

  while(left < right){
    mid = (left + right) / 2;
    if(key == A[mid]) return 1;
    if(key > A[mid]) left = mid + 1;
    else if(key < A[mid]) right = mid;
  }
  return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<tuple<int64_t, int64_t, int64_t>> v(n);
    for (int i = 0; i < n; i++) {
        int64_t a, b;
        cin >> a >> b;
        v[i] = {a+b, a, b};
    }
    sort(v.rbegin(), v.rend());
    int64_t ans = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            ans += get<1>(v[i]);
        } else {
            ans -= get<2>(v[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main(){
  long long N;
  cin>>N;
  long long count=0;
  for(long long i=0; i<N; i++){
    long long a;
    cin>>a;
    while(a%2==0){
      a=a/2;
      count++;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
# 15:20 -16:08 giveup
# 21:45 -22:33 review
from collections import Counter

# 3
# acornistnt
# peanutbomb
# constraint
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
# s is ['acinnorstt', 'abbemnoptu', 'acinnorstt']
counter = Counter(s)
# counter is Counter({'acinnorstt': 2, 'abbemnoptu': 1})
# counter.values() is dict_values([3, 2])
ans = sum(x*(x-1)//2 for x in counter.values())
print(ans)

Measured memory_bytes: 19764
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        // 主処理
        char c = 'a';
        for (int i = 0; i < 26; i++) {
            if (!s.contains(String.valueOf(c))) {
                break;
            }
            c += 1;
        }

        boolean judge = c != '{';
        String result = judge ? String.valueOf(c) : "None";

        // 出力
        System.out.println(result);
    }
}


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

#define int int64_t

using namespace std;

#define MAX 200005

int n, a[MAX], dp[MAX];

int f(int i)
{
    if (dp[i] != -1)
        return dp[i];
    if (i == n - 1)
        return 0;
    if (i == n - 2)
        dp[i] = f(i + 1) + abs(a[i + 1] - a[i]);
    else
    {
        dp[i] = min(f(i + 1) + abs(a[i + 1] - a[i]), f(i + 2) + abs(a[i + 2] - a[i]));
    }
    return dp[i];
}

signed main()
{
    scanf("%lld", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", a + i);
        dp[i] = -1;
    }
    printf("%lld\n", f(0));
}


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

int gcd(int a, int b) {
    if(a < b) swap(a,b);
    if(a % b == 0) return b;
    else return (a / b, a % b);
}

int main() {
    string s;
    cin >> s;

    int res = 1001001001;
    for(char c = 'a'; c <= 'z'; ++c) {
        int tmp = 0;
        int cnt = 0;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] != c) {
                ++cnt;
                if(i == s.size()-1) tmp = max(tmp, cnt);
            } else {
                tmp = max(tmp, cnt);
                cnt = 0;
            }
        }
        res = min(res, tmp);
    }
    cout << res << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
#define ii int
#define du double

#define vl vector<ll>
#define pb emplace_back
#define fast                        \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);
#define printv(v)                    \
  for (auto x : v) cout << x << " "; \
  cout << jmp;
#define jmp "\n"
#define vi vector<int>
#define vb vector<bool>
#define SORT(v) sort(v.begin(), v.end())
#define REV(x) reverse(x.begin(), x.end())
#define all(x) x.begin(), x.end()
#define SET(x, a) memset(x, a, sizeof(x))
#define si(x) x.size()
#define ff first
#define ss second
#define iin insert
using namespace std;
bool vis[100005];
// vl g[100005];
void dfs(ll s, vl g[]) {
  vis[s] = 1;
  for (auto x : g[s]) {
    if (!vis[x]) dfs(x, g);
  }
}
void solve() {
  ll n, m, x, y, z, ctr = 0;
  cin >> n >> m;
  vl g[n+1];
  memset(vis, 0, sizeof(vis));
  for (ll i = 0; i < m; i++) {
    cin >> x >> y >> z;
    //x--, y--;
    g[x].pb(y);
    g[y].pb(x);
  }
  for (ll i = 1; i <= n; i++) {
    //ctr++;
    if (!vis[i]) dfs(i, g),ctr++;
  }

  cout << ctr << jmp;
}
int main() {
  ll t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

Measured memory_bytes: 13792
n=int(input())
a=[int(_) for _ in input().split()]
b=[int(_) for _ in input().split()]
c=[int(_) for _ in input().split()]
r=0
for i in range(1,len(a)):
    if a[i]-a[i-1] == 1:
        r+=c[a[i-1]-1]
print(sum(b)+r)

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline

a,b = map(int,input().split())
aa = []
d = []
for i in range(b):
    k,kk = map(int,input().split())
    d.append([k, kk,i+1])

da = sorted(d)

kkk = da[0][0]
ll = 0
for i in range(b):
    kkkk = da[i][0]
    if kkk == kkkk:
        ll += 1
    else:
        kkk = kkkk
        ll = 1
    aa.append([da[i][2],da[i][0],ll])
aa.sort()

for i in aa:
    m = str(i[1])
    n = str(i[2])
    m = "0"*(6-len(m))+m
    n = "0"*(6-len(n))+n
    print(m+n)


Measured memory_bytes: 74460
k,n=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
b=len(a)
diff=max(a)-min(a)
temp1=a[0]
for i in range(1,b):
    temp2=a[i]
    a[i]=a[i]-temp1
    temp1=temp2


la=k-diff
a[0]=la

print(sum(a)-max(a))


Measured memory_bytes: 26444