akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            c[i] = 1;
        }

        Arrays.sort(a);
        int count = 1;
        int[] b = new int[n];
        int k = 0;

        for (int i = 0; i < n - 1; i++) {
            if (a[i] != a[i + 1]) {
                b[k] = a[i];
                k++;
            } else {
                c[k]++;
            }
        }
        if(k>=1) {
            b[k] = a[n - 1];
            k++;
        }
        int countmax  = 1;
        int countmax1 = 1;
        int countmax2 = 1;
        int countmax3 = 1;
        if (k == 0) countmax = c[k];
        else if (k == 1) {
            if ((Math.abs((b[0] - b[1]))) <= 2) {
                countmax = c[0] + c[1];
            } else {
                if (c[0] > c[1]) countmax = c[0];
                else countmax = c[1];
            }
        } else {
            for (int i = 0; i < k -1; i++) {
                if (countmax1<c[i]) countmax1 = c[i];
                if (Math.abs(b[i] - b[i+1])<=2) {
                    if (countmax2 <= c[i] + c[i + 1]) countmax2 = c[i] + c[i + 1];
                }
                if (i > 0) {
                    if ((b[i - 1] + b[i] + b[i + 1])  == 3*b[i]) {
                        count = c[i - 1] + c[i] + c[i + 1];
                        if (countmax3 <= count) countmax3 = count;
                    }
                }
            }
            if(countmax1<c[k-1]) countmax1 = c[k-1];
            countmax = countmax1;
            if (countmax < countmax2) {
                countmax = countmax2;
            }
            if (countmax < countmax3) {
                countmax = countmax3;
            }
        }
        System.out.println(countmax);

    }
}


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

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double dbl;
typedef pair<int, int> pii;

#define F(i, l, r) for(int i = (l); i < (r); i++)
#define DF(i, l, r) for(int i = (l); i >= (r); i--)
#define I(x, a) for(auto x : (a))
#define mp make_pair
#define X first
#define Y second
#define clean(x) memset((x), 0, sizeof(x))
#define ret return
#define cont continue
#define brk break
#define ins insert
#define all(x) (x).begin(),(x).end()
#define sync ios_base::sync_with_stdio(false);cin.tie(0)
#define pb push_back
#define y1 fjfg

const int maxn = 1e3 + 3;

int a[maxn];
int n;

signed main(){
	sync;
	cin >> n;
	F(i, 0, n)cin >> a[i];
	bool isp = false;
	F(i, 0, n)if(a[i] > 0)isp = true;
	if(!isp){
		int kek = a[0];
		int pos;
		F(i, 1, n)kek = max(kek, a[i]);
		F(i, 0, n)if(kek == a[i])pos = i;
		cout << kek << '\n';
		cout << n - 1 << '\n';
		F(i, 0, pos)cout << 1 << '\n';
		int huy = n - pos;
		F(i, pos + 1, n)cout << huy-- << '\n';
		ret 0;
	}
	ll ans = -1e18;
	int al, ar;
	F(l, 0, n){
		ll kek = 0;
		if(a[l] <= 0)continue;
		for(int r = l; r < n; r += 2){
			if(a[r] > 0)kek += a[r];
			if(kek > ans){ans = kek; al = l; ar = r;}
		}
	}
	cout << ans << '\n';
	vector<int> out;
	F(i, 0, al)out.pb(1);
	int podliva = n - al;
	F(i, ar + 1, n){out.pb(podliva--);}
	int cyka = 0;
	int tot = 0;
	for(int i = ar; i >= al; i -= 2){
		++tot;
		if(a[i] <= 0){
			++cyka;
			out.pb(i - al + 1);
		}
	}
	tot -= cyka;
	F(i, 0, tot - 1)out.pb(2);
	cout << out.size() << '\n';
	I(c, out)cout << c << '\n';
	ret 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;

class Main {
    // returns x! / (y! * z!)
    static String permutation(int x, int y, int z) {
        // make y bigger than z
        if (z > y) {
            int tmp = y;
            y = z;
            z = tmp;
        }

        BigDecimal result = BigDecimal.ONE;

        int counter = 1;

        for (int i = y + 1; i <= x; i++) {
            result = result.multiply(new BigDecimal(String.valueOf(i)));
            if (counter <= z) {
                result = result.divide(new BigDecimal(String.valueOf(counter)));
                counter++;
            }
        }

        for (int i = counter; i <= z; i++) {
            result = result.divide(new BigDecimal(String.valueOf(counter)));
        }

        return result.toString();
    }

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

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int r = Integer.parseInt(input[2]);

        /* 一応ACだが、遅い.
        int nm = n*m;
        
        if(r < nm){
            System.out.println("0");
            return;
        }
        
        int beads = r - nm;
        System.out.println(permutation(beads+n-1, beads, n-1));
        */

        // 以下、他の方のコードを参考にして実装.圧倒的に速い
        r -= n * m;
        if (r < 0) {
            System.out.println("0");
            return;
        }

        BigDecimal result = BigDecimal.ONE;

        for (int i = 0; i < Math.min(r, n - 1); i++) {
            result = result.multiply(new BigDecimal(r + n - 1 - i)).divide(new BigDecimal(i + 1));
        }

        System.out.println(result.toString());
    }
}


Measured memory_bytes: 504544
#include<bits/stdc++.h>
using namespace std;
int dsum(int nn)
{
  int ret=0;
  int n=nn;
  while(n>0)
  {
     ret+= n%10;
     n/=10;
 }
return ret;
}
int main()
{
  int n,a,b,sum=0;
 cin>>n>>a>>b;
 for(int i=1;i<=n;i++)
{
    if(dsum(i)>=a&&dsum(i)<=b)
      sum+=i;
}
cout<<sum<<endl;
return 0;
}

Measured memory_bytes: 256
#[warn(unused_imports)]
use itertools::*;
use proconio::*;

fn main() {
    input! {
        _: usize,
        s: String,
    }
    let chars: Vec<char> = s.chars().collect();

    let cnt = |c| s.chars().filter(|&x| x == c).count();
    let mut ans = cnt('R') * cnt('G') * cnt('B');

    for i in 0..chars.len() {
        let first = chars[i];
        let second_max = (chars.len() + i + 1) / 2;
        for j in i + 1..second_max {
            let second = chars[j];
            if first != second {
                let third = chars[2 * j - i];
                if third != second && first != third {
                    ans -= 1;
                }
            }
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 2152
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        while (n != 0) {
            int top = 0;
            int longest = 0;
            for (int i = 0; i < n; i++) {

                int kanja = scan.nextInt();

                int d1 = scan.nextInt();
                int d2 = scan.nextInt();
                int kyori;
                kyori = d1 + d2;
                if (i == 0) {
                    longest = kyori;
                    top = kanja;

                } else if (kyori > longest) {
                    longest = kyori;
                    top = kanja;

                }

            }
            System.out.println(top + " " + longest);
            n = scan.nextInt();
        }

    }
}



Measured memory_bytes: 162360
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
mt19937 rnd;


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            s[i] = 'D';
        }
    }
    cout << s << "\n";

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
int main(){
  char c;
  string A="aiueo";
  int a=0;
  cin>>c;
  for(int i=0;i<5;i++){
    if(c==A[i]) a=1;
  }
  if(a==1) cout<<"vowel"<<endl;
  else cout<<"consonant"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*"lcm"   MIN*/                      int lcm(ll a,ll b){return a*b/gcd(a,b);}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}

int main(){
    int n,m;
    cin >> n >> m;
    vector<int>za(m);
    for(int i=0;i<m;i++){
        cin >> za.at(i);
    }
    sort(za.begin(),za.end());
    ll ans = za.at(m-1)-za.at(0);
    if(m==1){
        cout<<ans<<endl;
        return 0;
    }
    vector<int>kyori(m-1);
    ll sum = 0;
    for(int i=1;i<m;i++){
        kyori.at(i-1)=abs(za.at(i-1)-za.at(i));
        sum+=kyori.at(i-1);
    }

    sort(kyori.begin(),kyori.end());
    reverse(kyori.begin(),kyori.end());
    for(int i=1;i<n;i++){
        if(m<=i)continue;
        sum-=kyori.at(i-1);
    }
    ans = min(ans,sum);
    cout<<ans<<endl;
}



Measured memory_bytes: 1024
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long q = sc.nextLong();
    long h = sc.nextLong();
    long s = sc.nextLong();
    long d = sc.nextLong();
    long N = sc.nextLong();
    long two = N / 2;
    long one = N - 2 * two;
    long d2 = Math.min(d, 8 * q);
    d2 = Math.min(d2, 4 * h);
    d2 = Math.min(d2, 2 * s);
    long d1 = Math.min(4 * q, 2 * h);
    d1 = Math.min(d1, s);
    long ans = two * d2 + one * d1;
    System.out.println(ans);
  }
}

Measured memory_bytes: 22100
#include<iostream>
using namespace std;
int main(){
	int H, W, i, j, k;
	while (true){
		cin >> H >> W;
		if (H == 0 && W == 0){ break; }
		for (i = 0; i < H; i++){
			if (i % 2 == 0){
				for (j = 0; j < W; j++){
					if (j % 2 == 0){
						cout << "#";
					}
					else{
						cout << ".";
					}
				}
				cout << endl;
			}
			else{
				for (k = 0; k < W; k++){
					if (k % 2 == 0){
						cout << ".";
					}
					else{
						cout << "#";
					}
				}
				cout << endl;
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3104
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x) - 1 * 100);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>

using namespace std;
int n, m;
ll x[100];
ll y[100];
int main(void) {
	string s;
	cin >> s;
	int a, b, c, d;
	a = int(s[0] - '0');
	b = int(s[1] - '0');
	c = int(s[2] - '0');
	d = int(s[3] - '0');
	rep(i, 1 << 3) {
		int sum = a;
		char ans[3];
		rep(j, 3) {
			if (i >> j & 1) {
				sum += int(s[j + 1] - '0');
				ans[j] = '+';
			}
			else {
				sum -= int(s[j + 1] - '0');
				ans[j] = '-';
			}
		}
		if (sum == 7) {
			rep(j, 4) {
				if (j)
					cout << ans[j-1];
				cout << s[j];
			}
			cout << "=7" << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import sys
import copy
import math
import itertools
import numpy as np

A=int(input())
B=int(input())
C=int(input())
X=int(input())
cnt = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if a*500+b*100+c*50==X:
                cnt+=1
print(cnt)

Measured memory_bytes: 27184
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    int c = Integer.parseInt(sc.next());
    if(a <= c && b >= c){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}
      

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int,int>
#define endl "\n"
#define MAXN 100005
using namespace std;

void solve()
{
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
    }
    sort(a, a+n);
    ll ans = a[n-1];
    ll players = n - 2;
    ll i = n - 2;
    while (players)
    {
        /* code */
        ans += a[i];
        players -= 1;
        if(players==0)
            break;
        ans += a[i];
        i -=1;
        if(i<0)
            break;
        players -= 1;
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 5204
s = raw_input()
l = len(s)
dp = [0]*(l+1)
dp[0] = 1
for i in xrange(l):
    if dp[i] == 0: continue

    if i+5 <= l and s[i:i+5] in ["dream", "erase"]:
        dp[i+5] = 1
    if i+6 <= l and s[i:i+6] == "eraser":
        dp[i+6] = 1
    if i+7 <= l and s[i:i+7] == "dreamer":
        dp[i+7] = 1
print "YES"*dp[l]or"NO"


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

int main(){
  uint64_t Ns, Nc;
  cin >> Ns >> Nc;
  cout << (Nc <= 2*Ns ? (Nc / 2) : (Ns + (Nc - 2 * Ns) / 4)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define mm(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define pf(a) printf("%d\n",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define p_f(a) printf("%d ",a)
#define pyn(a) if(a)puts("Yes");else puts("No");
#define fi first
#define se second
#define db double
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const db eps=1e-9;
const int P=2019;
int l,r,ans;
int main()
{
    cin>>l>>r;
    ans=inf;
    if(r-l+1>=P)ans=0;
    int begin=l%P,end=r%P;
    for(int i=begin;(i)%P!=r%P;i++){
        for(int j=i+1;j%P!=(r+1)%P;j++)ans=min(ans,i*j%P);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include <stdio.h>

int main(){
	using namespace std;
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
		if(a<b&&b<c)
			printf("Yes\n");
		else
			printf("No\n");
	return 0;
}

Measured memory_bytes: 1168
import scala.io.StdIn.readInt

object Main {

  def insertionSort(a:Array[Int],n:Int,g:Int):Int = {
    var cnt = 0
    for(i <- g until n) {
      val v = a(i)
      var j = i-g
      while( j>=0 && a(j) > v ) {
        a(j+g) = a(j)
        j = j-g
        cnt += 1
      }
      a(j+g) = v
    }
    cnt
  }

  def getG(g:List[Int],x:Double,n:Double):List[Int] = {
    val y = x*2.25+1
    if(y > n) g
    else
      getG(Math.ceil(y).toInt::g,y,n)
  }

  def main(args:Array[String]) = {
    val n = readInt
    val a = (for(i <- 0 until n) yield readInt).toArray
    val g = getG(List(),0,n.toDouble)
    val m = g.length
    var ct = 0

    for(i <- g) {
      ct += insertionSort(a,n,i)
    }
    println(m)
    println(g.mkString(" "))
    println(ct)
    println(a.mkString("\n"))
  }
}

Measured memory_bytes: 321524
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
 
#define int long long 
#define pb push_back
#define all(s) s.begin(),s.end()
#define pii pair<int,int>
#define fr first
#define sc second
#define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"

using namespace std;

const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7;
const double pi = acos(-1);

int vis[N];

void solve() {
	//soln
	int n, m, x;
	cin >> n >> m >> x;
	int pr[n], a[n][m];
	for(int i = 0; i < n; i++) {
		cin >> pr[i];
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int res = inf;
	for(int mask = 0; mask < (1 << n); mask++) {
		int tmp = 0;
		int row[m] = {0};
		for(int i = 0; i < n; i++) {
			if(mask & (1 << i)) {
				tmp += pr[i];
				for(int j = 0; j < m; j++) {
					row[j] += a[i][j];					
				}
			}
		}
		bool ok = 1;
		for(int i = 0; i < m; i++) {
			ok &= (row[i] >= x);
		}
		if(ok) res = min(res, tmp);
	}
	cout << (res == inf ? -1 : res) << endl;
}
main() {
	bst;
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}


Measured memory_bytes: 3648
K,S = gets.split.map(&:to_i)
a = Array.new
if K < S
    for i in 0..K
        if K >= S-i && 2 * K >= S-i
        a[i] = S-i+1
        elsif K < S-i && 2 * K >= S-i
        a[i] = (S-(2 * K)-i).abs+1
        else
        a[i] = 0
        end
    end
elsif S <= K
    for i in 0..S
        a[i] = S-i+1
    end
end
puts a.inject(:+)

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define mod 1000000007

using namespace std;

//ll cnt;

int main()
{
	IOS;
	int n,k;
    cin>>n>>k;
    int cnt=0;
    for(int y=1;y<=n;y++)
    {
        cnt++;
        if(y+k>n)
            break;
    }
    cout<<cnt<<"\n";
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
char s[200], S[10], f=0, b=0;
int main()
{
	scanf( "%s", s ); 
	S[0]='k';
	S[1]='e';
	S[2]='y';
	S[3]='e';
	S[4]='n';
	S[5]='c';
	S[6]='e';
	int l1=strlen(S), l2=strlen(s);
	for ( int i=0; i<=6; i++  )
	  if ( s[i]==S[i] ) ++f; 
	  else break;
	for ( int i=1; i<=7; i++ )
	  if ( s[l2-i]==S[l1-i] ) ++b;
	  else break;
	if ( f+b>=7 ) printf( "YES" );
	else printf( "NO" );
	return 0;
}

Measured memory_bytes: 128
import numpy as np
P = np.array([list(map(int,input().split())) for _ in [0]*3],dtype=float)

def f(r):
    R = 0+P
    for i in range(3):
        c = r / (1 - e[i].dot(e[i-1])**2)**0.5
        R[i] += c*(e[i]-e[i-1])
    return R

def g(p):
    r = 0
    n = np.linalg.norm
    for i in range(3):
        r = max(r,n(p[i]-p[i-1]))
    return r

def h(r):return g(f(r))<2*r

def binary_search_float(l,r,func,d):
    if func(l):return l
    if not func(r):return r
    while (r-l)>=d:
        i = (l+r)/2
        if func(i):
            r = i
        else:
            l = i
    return l

e = -P
for i in range(3):
    e[i] += P[(i+1)%3]
l = np.linalg.norm(e,axis=1)
L = np.sum(l)
S2 = np.abs(e[0,0]*e[-1,1]-e[-1,0]*e[0,1])
M = S2/L
e = e/(l*np.ones((2,3))).T

print(binary_search_float(0,M,h,1e-10))

Measured memory_bytes: 12496
N = int(input())
cnt = [0]*(10**5)
ans = 0
for i in list(map(int,input().split())):
  cnt[i-1] += 1
for i in range(10**5):
  ans += (i+1)*cnt[i]
Q = int(input())
for i in range(Q):
  a,b = map(int,input().split())
  ans += (b-a)*cnt[a-1]
  cnt[b-1] += cnt[a-1]
  cnt[a-1] = 0
  print(ans)

Measured memory_bytes: 21796
#include<bits/stdc++.h>
using namespace std;
const int M=3e5+5,P=1e9+7;
int n,A[M],S,L,R,ans,mark[M];
int inv[M],ifac[M],fac[M];
void init(){
	fac[0]=ifac[0]=inv[1]=1;
	for(int i=1;i<M;++i)fac[i]=1ll*i*fac[i-1]%P;
	for(int i=2;i<M;++i)inv[i]=1ll*(P-P/i)*inv[P%i]%P;
	for(int i=1;i<M;++i)ifac[i]=1ll*inv[i]*ifac[i-1]%P;
}
int C(int n,int m){
	if(m<0||n<m)return 0;
	return (1ll*fac[n]*ifac[n-m]%P)*ifac[m]%P;
}
void Add(int x,int y){
	ans=(1ll*ans+C(x,y))%P;
}void Del(int x,int y){
	ans=(1ll*ans-C(x,y)+P)%P;
}
int main(){
	scanf("%d",&n);
	init();
	for(int i=1;i<=n+1;i++){
		scanf("%d",&A[i]);
		if(mark[A[i]])L=mark[A[i]],S=A[i],R=i;
		else mark[A[i]]=i;
	}
	int a=L-1,c=n+1-R;
	for(int i=1;i<=n+1;i++){
		if(i==n+1){puts("1");continue;}
		if(i==1){printf("%d\n",n);continue;}
		ans=0;
		Add(n+1,i);
		Del(a+c,i-1);
		while(ans<0)ans+=P;
		printf("%d\n",ans);
	}
	return 0;
}
	


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

using namespace std;

int main() {
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    double hr, mr, dr;
    hr = 30 * h + m * 0.5;
    mr = 6 * m;

    if (hr > mr) dr = hr - mr;
    else dr = mr - hr;

    long double ans;
    if (dr == 0) {
        if (a > b) ans = a - b;
        else ans = b - a;
    } else if (dr == 180) {
        ans = a + b;
    } else {
        if (dr > 180) dr = 360 - dr;
        ans = sqrt(((a * a) + (b * b)) - ((2 * a * b) * cos(dr * M_PI / 180)));
    }

    printf("%.20Lf\n", ans);
    return 0;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX;
//const int INF = INT_MAX  ;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

const int mod = 1000000007;

int dp[101][4][4][4];

int main() {

    int n, m, c;
    cin >> n >> m >> c;

    vector<int> bs(m);

    rep(i, m) {
        int b;
        cin >> b;
        bs[i] = b;
    }

    vector<vector<int>> as(n, vector<int>(m));
    rep(i, n) {
        rep(j, m) {
            int a;
            cin >> a;
            as[i][j] = a;
        }
    }

    int count = 0;
    rep(i, n) {
        int now = 0;
        rep(j, m) {
            now += as[i][j] * bs[j];
        }
        now += c;
        if (now > 0) {
            count++;
        }
    }

    cout << count << endl;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll n;
    cin>>n;
    double sum = 0;
    vector<ll> a(n);
    for (ll i =0; i<n; i++){
        ll a;
        cin>>a;
        sum += 1.0/a;
    }
    double ans = 1/sum;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i = 0; i < (n) ;i++)
  
int vec1[] = {0,1,-1,1,-1,0};
int vec2[] = {1,1,0,0,-1,-1};
  
int t,n;
int table[200][200];
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
queue<piii> q1;
  
int ans;
  
int solve(int y,int x){
    queue <piii> q1;
    q1.push(make_pair(0,make_pair(y,x)));
    while(!q1.empty()){
        if(t <= q1.front().first)
            return 0;
        REP(i,6){
            int n_y = q1.front().second.first + vec1[i];
            int n_x = q1.front().second.second + vec2[i];
            if(table[n_y][n_x] == 0){
                ans++;
                table[n_y][n_x] = 1;
                q1.push(make_pair(q1.front().first + 1,make_pair(n_y,n_x)));
            }
        }
        q1.pop();
    }
    return 0;
}
  
int main(){
    while(cin >> t  >> n , t+n){
        ans = 0;
        fill_n(table[0],200*200,0);
        REP(i,n){
            int x,y;
            cin >> x >> y;
            table[100 + y][100 + x] = 1;
        }
        int x,y;
        cin >> x >> y;
        table[100+y][100+x] = 1;
        solve(100+y,100+x);
        cout << ans + 1<< endl;
    }
    return 0;
}
 

Measured memory_bytes: 3240
#include <bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int,int>
#define eps 1e-3
inline int lowbit(int x){ return x & -x; }
const int N = 2e6 + 10;
const int mod = (int) 1e9 +7;
const int INF = 0x3f3f3f3f;
const long long LINF = (1LL << 62);
typedef long long LL;
typedef unsigned long long ULL;
const double PI = acos(-1.0);
using namespace std;

char buf[100000],*p1=buf,*p2=buf;
inline char nc(){
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline bool read(int & x){
  char c=nc();x=0;
  if(c==EOF) return false;
  bool flag = false;
  for(;!isdigit(c);c=nc()) flag = true;
  for(;isdigit(c);x=x*10+c-'0',c=nc());
  if(flag) x *= -1;
  return true;
}
inline bool readL(LL & x){
  char c=nc();x=0;
  if(c==EOF) return false;
  bool flag = false;
  for(;!isdigit(c);c=nc()) flag = true;
  for(;isdigit(c);x=x*10+c-'0',c=nc());
  if(flag) x *= -1;
  return true;
}



int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
  int n; scanf("%d", &n);
  int ans = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(i % 2 == 0 && j % 2) ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
//#include <string.h>

int main(void){
  char s[4];
  scanf("%s", s);
  for(int i=0;i<3;i++){
  	if(s[i]=='1'){
      s[i]='9';
    }
    else if(s[i]=='9'){
      s[i]='1';
    }
  }
  printf("%s", s); 
  return 0;
}

  


Measured memory_bytes: 1696
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i;
	cin>>n;
	int a[n];
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int y=a[0];
	for(i=1;i<n;i++)
	{
		y=y^a[i];
	}
	for(i=0;i<n;i++)
	{
		int x=y^a[i];
		cout<<x<<" ";
	}
}

Measured memory_bytes: 4260
package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if a%3 == 0 || b%3 == 0 || (a+b)%3 == 0 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define printjudge(cond) {if(cond) printf("Yes\n"); else printf("No\n");}
#define printans(ans) {printf("%d\n",(ans));}
typedef int* intarray;
typedef char* string;

int main(){
    int N, judge = 1;
    scanf("%d", &N);
    string* W = new string[N];
    for(int i=0; i<N; i++){
        W[i] = new char[11];
        scanf("%s", W[i]);
    }
    for(int i=0; i<N; i++){
        if(i>0 && W[i][0]!=W[i-1][strlen(W[i-1])-1]) judge = 0;
        else{
            for(int j=0; j<i; j++){
                if(strcmp(W[i],W[j])==0) {judge = 0; break;}
            }
        }
        if(judge==0) break;
    }
    printjudge(judge);
    return 0; 
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return a % 1000000007;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll bombcount(ll a,ll b,vector<vector<char>> bomb){
  return 0 ;
}

int main(){
  ll h,w; cin >> h >> w;
  vvl count (h+2,vl(w+2,0)); 
  vector<vector<char>> ans(h,vector<char>(w));
  
  for(ll i=1; i <= h; i++){
    string s; cin >> s;
    for(ll j=1; j <= w; j++){
      if(s[j-1] == '#'){
        count[i][j] = -100;
        count[i-1][j-1]++; count[i][j-1]++; count[i+1][j-1]++;
        count[i-1][j]++; count[i+1][j]++;
        count[i-1][j+1]++; count[i][j+1]++; count[i+1][j+1]++;
      }
    }
  }
  
  for(ll i=1; i <= h; i++){
    for(ll j=1; j <= w; j++){
	  if(count[i][j] < 0) cout << '#';
      else cout << count[i][j];
    }
    cout << endl;
  }
}
                            

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

#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

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

typedef long long int lli;
typedef pair<lli, lli> P;

lli dp[100002][2]; // i 桁目までで a+b==a xor b となる場合の数(jはsafeかどうか)
lli mod = 1000000007;

int main() {
    string l;
    cin >> l;
    l = "0" + l;
    bool safe = true;
    dp[0][safe] = 0;
    dp[0][!safe] = 1;
    lli len = l.length()-1;
    REP(i, 0, len) {
        // danger
        if (l[i+1] == '0') {
            dp[i+1][!safe] = dp[i][!safe];
        }
        else {
            dp[i+1][!safe] = (dp[i][!safe] * 2) % mod;
            dp[i+1][safe] = dp[i][!safe];
        }

        // safe
        dp[i+1][safe] = (dp[i+1][safe] + (dp[i][safe] * 3) % mod) % mod;

    }
    //REPE(i, 1, len) {
    //    cout << "dp[" << i << "][!safe]: " << dp[i][!safe] << ", ";
    //    cout << "dp[" << i << "][safe]: " << dp[i][safe];
    //    cout << endl;
    //}
    cout << (dp[len][0] + dp[len][1]) % mod << endl;
}


Measured memory_bytes: 2044
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
 
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define C(i) cin>>i
#define C2(i,j) cin>>i>>j
#define C3(i,j,k) cin>>i>>j>>k
#define C4(i,j,k,m) cin>>i>>j>>k>>m
////////////////////////////////////////////////////////////


int main(){
	const long MAX_A = 100001;
	long n,k;
	cin >> n >> k;
	vector<long> v(MAX_A,0);
	rep(i,0,n){
		int a,b;
		cin >> a >> b;
		v[a]+=b;
	}
	
	long cnt = 0;
	long idx = 0;
	while( cnt < k ){
		cnt += v[idx];	
		idx++;
	}
	
	idx--;
	P(idx);

	ret 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef TEST
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define ins insert
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define pp pop
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, H[100005];
vector<int> adj[100005];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> H[i];
	for (int i = 1, u, v; i <= M; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		bool v = 1;
		for (int j : adj[i])
			if (H[j] >= H[i]) v = 0;
		cnt += v;
	}
	cout << cnt << '\n';
}


Measured memory_bytes: 10272
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>
#include <iterator>
#include <functional>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,M;
  cin>>N>>M;
  vector<pair<int,int>> BA(N);
  set<int> times;
  REP(i,N){
    int a,b;
    cin>>a>>b;
    BA[i]=make_pair(-b,-a);
  }
  REP(i,M)times.insert(i);
  sort(ALL(BA));
  ll now=0ll,ans=0ll;
  for(auto e:BA){
    int value=-e.first;
    int time=-e.second;
    auto it=times.lower_bound(time-1);
    if(it!=times.end()){
      ans+=value;
      times.erase(it);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5760
n = int(input())
r = []
for i in range(n):
    r.append(int(input()))

rmin = r[0]
dmax = -10**9

for i in range(1, n):
    d = r[i] - rmin
    if (d > dmax):
        dmax = d
    if (r[i]<rmin):
        rmin = r[i]

print(dmax)



Measured memory_bytes: 13584
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


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

		List<List<Integer>> A = new ArrayList<>();
		for(int i = 0 ;i<n;i++) {
			List<Integer> a = new ArrayList<>();
			A.add(a);
		}
		int q = sc.nextInt();
		for(int i = 0; i<q;i++) {
			int sentaku = sc.nextInt();
			int t = sc.nextInt();
			if(sentaku==0) {
				int x = sc.nextInt();
				List<Integer> a=A.get(t);
				a.add(x);
				
			}
			else if (sentaku == 1) {
				List<Integer> a=A.get(t);
                for(int j=0;j<a.size();j++){
                    System.out.print(a.get(j));
                    if(a.size()-j!=1)
                        System.out.print(" ");
                }
			
            System.out.println();
            }
			else if(sentaku==2){
				List<Integer> a=A.get(t);
				a.clear();
				
			}
			
		}

				sc.close();
	}
}


Measured memory_bytes: 310080
n = int(input())
a = sorted(map(int, input().split()))
cs = [0]
for i in range(n):
    cs.append(cs[i]+a[i])

# print(cs)
ans = 1
for i in range(n-1)[::-1]:
    if 2*cs[i+1] >= a[i+1]:
        ans += 1
    else:
        break
        # print(i)

print(ans)

Measured memory_bytes: 20624
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

int selectionSort(int *num, int n) {
    int minj = 0;
    int count = 0;
    int i, j;
    for(i=0; i<n; i++) {
        minj = i;
        for(j=i; j<n; j++) {
            if(num[j]<num[minj]) {
                minj = j;
            }
        }
        swap(num[i], num[minj]);
        if(minj!=i) {
            count++;
        }    
    }
    return count;
}

int main() {
    int n;
    int count = 0;
    cin >> n;
    
    int num[n];
    for(int i=0; i<n; i++) {
        cin >> num[i];
    }
    
    count = selectionSort(num, n);
    for(int i=0; i<n; i++) {
        printf("%d", num[i]);
        if(i!=n-1) {
            printf(" ");
        }
    }
    printf("\n");
    printf("%d\n", count);
    
   return 0;
}


Measured memory_bytes: 3208
package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func max(l, r int) int {
	if l > r {
		return l
	}
	return r
}

func main() {
	scanner := makeWordScanner()
	n := eGetInt(scanner)
	maxval := 0
	prev := 0
	count := 0
	for i := 0; i < n; i++ {
		h := eGetInt(scanner)
		if h <= prev {
			count++
		} else {
			// 終了
			maxval = max(count, maxval)
			count = 0
		}
		prev = h
	}
	maxval = max(count, maxval)
	fmt.Println(maxval)
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
long Gcd(unsigned long long m, unsigned long long n){
	long temp;
	while (m % n != 0){
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}
int main(){
    int n;
    cin>>n;
    unsigned long long rt=0,gcd=0;
    for(int i = 0; i < n; i++){
        long t;
        cin>>t;
        if(rt != 0){
            gcd = Gcd(rt,t);
            rt = (rt/gcd)*t;
        }
        else
            rt = t;
   }
   cout<<rt;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>


#define	ll_int	long long int


int main()
{
	int n, m;
	ll_int *A, *B;
	int count;
	int i, j, k;

	scanf("%d", &n);
	A = (ll_int *)malloc(sizeof(ll_int) * n);
	for(i = 0; i < n; i++)
		scanf("%lld", &A[i]);

	scanf("%d", &m);
	B = (ll_int *)malloc(sizeof(ll_int) * m);
	for(i = 0; i < m; i++)
		scanf("%lld", &B[i]);


	// A, Bの要素を比較していく
	j = k = count = 0;
	for(i = 0; i < n + m - count; i++){
		if(A[j] == B[k]){
			printf("%lld\n", A[j]);
			j++;
			k++;
			count++;
		}else if(A[j] < B[k])
			j++;
		else if(B[k] < A[j])
			k++;
	}

	return 0;
}


Measured memory_bytes: 4872
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define Max 1000005
#define mem(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define mp make_pair
#define input ios::sync_with_stdio(false);cin.tie(0);
#define debug printf("debug!!!\n");
const LL mod=1e9+7;
const ULL base=131;
const LL LL_MAX=9223372036854775807;
using namespace std;
int main()
{
    LL a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b)
        swap(a,b);
    LL ans=-a-b;
    if(ans%2)
        printf("IMPOSSIBLE\n");
    else
        printf("%lld",-ans/2);
    return 0;
}


Measured memory_bytes: 256
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in'_'*n]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
s=[0]
f=s+[-1]*~-n
while s:
  v=s.pop()
  p=f[v]^1
  for w in e[v]:
    if-1<f[w]:
      if f[w]!=p:
        print(n*~-n//2-m)
        exit()
    else:
      f[w]=p
      s+=w,
r=sum(f)
print(r*(n-r)-m)

Measured memory_bytes: 30680
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    graph = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0

    for _ in range(m):
        s, t, d = map(int, input().split())
        graph[s][t] = d

    dp = [[f_inf] * n for _ in range(1 << n)]
    dp[0][0] = 0

    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if ((1 << v) & S) == 0:
                    if v != u:
                        idx = S | (1 << v)
                        dp[idx][v] = min(dp[idx][v], dp[S][u] + graph[u][v])

    print(dp[-1][0] if dp[-1][0] != f_inf else -1)


if __name__ == '__main__':
    resolve()



Measured memory_bytes: 19816
#include <iostream>
#include <vector>
#include <algorithm>
#include <ios>
using namespace std;

const int SENTINEL = 1000000005;

long long merge(vector<int> & a, int left, int mid, int right){
    auto n1 = mid - left;
    auto n2 = right - mid;
    vector<int> L(n1);
    vector<int> R(n2);
    copy(a.begin()+left, a.begin()+mid, L.begin());
    copy(a.begin()+mid, a.begin()+right, R.begin());
    L.push_back(SENTINEL);
    R.push_back(SENTINEL);
    long long counts = 0;
    int iL = 0;
    int iR = 0;
    for (int i = left; i != right; ++i){
        if (L[iL] > R[iR]){
            a[i] = R[iR];
            ++iR;
            counts += n1 - iL;
        }else{
            a[i] = L[iL];
            ++iL;
        }
    }
    return counts;
}


long long count_inversion(vector<int> & a, int left, int right){
    long long counts = 0;
    if (left + 1 < right){
        int mid = (left + right) / 2;
        counts += count_inversion(a, left, mid);
        counts += count_inversion(a, mid, right);
        counts += merge(a, left, mid, right);
    }
    return counts;
}


int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto & elem : a) cin >> elem;
    cout << count_inversion(a, 0, n) << endl;
    return 0;
}

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

int main(){
    int n, q, ans = 0;
	cin >> n;
	vector<int> s(n);
	for(int i = 0; i < n; i++){
		cin >> s[i];
	}
	cin >> q;
	vector<int> t(q);
	for(int i = 0; i < q; i++){
		cin >> t[i];
	}
	for(int i = 0; i < q; i++){
		for(int j = 0; j < n; j++){
			if(t[i] == s[j]){
				ans++;
				break;
			}
		}
	}
	cout << ans << endl;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int N = 55;
int n, k, res;
int a[N];

int solve(int l, int r) {
    int b[N];
    int cnt = 0;
    int t = l + r;
    int remain = k - t;
    int sum = 0;
    for (int i = 0; i < l; ++i) {
        b[cnt++] = a[i];
        sum += a[i];
    }
    for (int i = 0; i < r; ++i) {
        b[cnt++] = a[n - 1 - i];
        sum += a[n - 1 - i];
    }
    sort(b, b + t);
    int ri = 0;
    while (remain && ri < t && b[ri] < 0) {
        sum -= b[ri++];
        --remain;
    }
    // cout << l << ' ' << r << ' ' << sum << endl;
    return sum;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int l = 0; l <= min(n, k); ++l) {
        int rmax = min(n - l, k - l);
        for (int r = 0; r <= rmax; ++r) {
            res = max(res, solve(l, r));
        }
    }
    cout << res << endl;
    return 0;
}


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

int main() {
  int n, a, b;
  cin >> n >> a >> b;

  vector<int> s;
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    int sumt = 0;
    int t    = i;
    while (t) {
      sumt += t % 10;
      t /= 10;
    }
    if (sumt >= a && sumt <= b) { sum += i; }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int sum = 0;
        int min = 0;
        for(int i = 0; i < N;i++){
            int x = sc.nextInt();
            int distance1 = Math.abs(0 - x);
            int distance2 = Math.abs(K - x);
            if(distance1 > distance2){
                min = 2 * distance2;
            }else{
                min = 2 * distance1;
            }
            sum = sum + min;
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1e9;
const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

int main()
{
    int h, w;
    cin >> h >> w;
    int si, sj;
    cin >> si >> sj;
    si--;sj--;
    int gi, gj;
    cin >> gi >> gj;
    gi--;gj--;
    vector<vector<char>> mp(h, vector<char>(w));
    rep(i, h) rep(j, w) cin>> mp[i][j];
    vector<vector<int>> dist(h, vector<int>(w, inf));
    deque<P> q;
    
    dist[si][sj] = 0;
    q.emplace_back(si, sj);
    while (not q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        int x = dist[i][j];
        q.pop_front();
        rep(v, 4){
            int ni = i + di[v];
            int nj = j + dj[v];
            if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
            if (mp[ni][nj]=='#') continue;
            if (dist[ni][nj] <= x) continue;
            dist[ni][nj] = x;
            q.emplace_front(ni, nj);
        }
        repran(ei, -2, 3){
            repran(ej,-2, 3){
                int ni = i + ei;
                int nj = j + ej;
                // if (abs(ni-i)+abs(nj-j)<=1) continue;
                if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
                if (mp[ni][nj]=='#') continue;
                if (dist[ni][nj] <= x+1) continue;
                dist[ni][nj] = x+1;
                q.emplace_back(ni, nj);
            }
        }
    }
       
    if (dist[gi][gj] == inf) cout << -1 << endl;
    else cout << dist[gi][gj] << endl;
}

Measured memory_bytes: 8624
#include <bits/stdc++.h>
using namespace std;
int main() {
  string A, B, C, X, atoA;
  cin >> A >> B >> C;
  X = "aaa";
  X.at(0) = A.at(0);
  X.at(1) = B.at(0);
  X.at(2) = C.at(0);
  atoA = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  for(int i = 0; i < 26; i++) {
    if(X.at(0) == atoA.at(i)) {
      X.at(0) = atoA.at(i + 26);
      break;
    }
  }
  for(int i = 0; i < 26; i++) {
    if(X.at(1) == atoA.at(i)) {
      X.at(1) = atoA.at(i + 26);
      break;
    }
  }
  for(int i = 0; i < 26; i++) {
    if(X.at(2) == atoA.at(i)) {
      X.at(2) = atoA.at(i + 26);
      break;
    }
  }
  cout << X << endl;
}

Measured memory_bytes: 3628