akhauriyash/Code-Regression huggingface dataset:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    b = LI()
    ans = []
    d = max(b)
    i = 0
    while b:
        j = len(b)-1
        while j >= 0:
            if b[j] > j+1:
                print(-1)
                quit()
            elif b[j] == j+1:
                ans.append(b[j])
                b.pop(j)
                break
            j -= 1
    for i in ans[::-1]:
        print(i)
#B
def B():
    n = I()
    if n%2:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
    else:
        ans = []
        for i in range(1,n+1):
            for j in range(1,n+1):
                if j != n+1-i and j != i:
                    ans.append((min(i,j),max(i,j)))
        ans = list(set(ans))
        print(len(ans))
        ans.sort()
        for i in ans:
            print(*i)
#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    A()


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

int main(){

  string s;
  int cnt=0;
  int max=0;
  cin >> s;

  for(int i=0;i<3;i++){
    if(s[i] == 'R'){
      cnt++;
    }
    else{
      if(cnt > max){
        max = cnt;
        cnt = 0;
      }
    }
  }

  if(cnt > max)
    max = cnt;
    
  cout << max;
  return 0;
}

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

int A,B;

int main()
{
    cin>>A>>B;
    int cnt=0;
    for (int i=0; i<=B-A; i++){
        int x=A+i;
        if (x/10000==x%10 && x/1000%10==x%100/10) cnt++;
    }
    cout <<cnt;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int ctoi(char);

struct btn{
    int next;
    int flag;
};

int main()
{
    int N;
    cin >> N;
    vector<btn> btns(N+1);
    rep2(i, 1, N+1)
    {
        cin >> btns.at(i).next;
    }
    int index = 1;
    int count = 0;
    while(true)
    {
        if(index == 2)
        {
            cout << count << endl;
            return 0;
        }
        if(btns.at(index).flag == 1)
        {
            cout << "-1" << endl;
            return 0;
        }
        count++;
        btns.at(index).flag = 1;
        index = btns.at(index).next;

    }
    
}


int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c -'0';
    }
    return -1;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int k,n,a[601][601];
int main()
{
	cin>>k;
	if(k==1)return cout<<"1\n1\n",0;
	n=(k+1)/2;
	if(n&1)n++;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)a[i][j]=(i+j)%n+(i&1)*n;
	for(int x=2*n;x>k;x--)
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				if(a[i][j]==x-1)a[i][j]-=n;
	cout<<n<<'\n';
	for(int i=0;i<n;i++,cout<<'\n')
		for(int j=0;j<n;j++)cout<<a[i][j]+1<<' ';
}


Measured memory_bytes: 2432
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    val as = Array.fill(n)(sc.nextLong())

    val absArray = as.map(math.abs)
    val absMin = absArray.min
    val amountOfNegative = as.count(_ < 0)

    val ans = if (amountOfNegative % 2 == 0) {
      absArray.sum
    } else {
      absArray.sum - absMin * 2
    }

    println(ans)
  }

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<ll,ll> pll;

#define reps(i,f,n) for(int i = int(f); i <= int(n); i++)
#define rep(i,n) reps(i,0,int(n)-1)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)

#define all(x) (x).begin(),(x).end()
#define X first
#define Y second

#define sz size()
#define eb emplace_back
#define pb push_back

int memo[32];

int main(void){
  int w, h;
  int ok = false;

  cin >> h >> w;
  string str;
  rep(i,h){
    cin >> str;
    rep(j, w){
      memo[str[j]-'a']++;
    }
  }

  if(h < w) swap(h,w);
  if(w == 1){
    int o = 0;
    if(h%2 == 1){
      o = 1;
    }
    rep(i, 26){
      if(memo[i] %2 == 1){
        o--;
      }
    }
    if(o == 0){
      ok = true;
    }
  }else{
    int o = 0;
    int to = 0;
    if(h%2 == 1 && w %2 == 1){
      //2 -> 2, 1->1
      o = 1;
      to = h/2 + w/2;
    }else if(h%2 == 1 || w%2 ==1){
      if(h%2 == 1) to = w/2;
      else to = h/2;
    }
    rep(i, 26){
      if(memo[i] %4 != 0){
        if(memo[i] %2 == 1){
          o--;
        }else{
          to--;
        }
      }
    }
    if( o == 0 && to == 0){
      ok = true;
    }
  }
  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = getInt(sc);
		int[] d = getIntArray(sc);

		Arrays.sort(d);

		int ARCMax = d[n / 2 - 1];
		int ABCMin = d[n / 2];

		System.out.println(ABCMin - ARCMax);
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}
}


Measured memory_bytes: 48232
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int A[3][3];
    for (int i = 0; i < 3; ++i) {
        cin >> A[i][0] >> A[i][1] >> A[i][2];
    }

    int n;
    cin >> n;
    vector<vector<int>> b(3, vector<int>(3, 0));
    for (int k = 0; k < n; ++k) {
        int tmp;
        cin >> tmp;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (A[i][j] == tmp) b[i][j]++;
            }
        }

    }
    bool ans = false;
    if (b[0][0] > 0 && b[1][1] > 0 && b[2][2] > 0) ans = true;
    if (b[0][2] > 0 && b[1][1] > 0 && b[2][0] > 0) ans = true;
    if (b[0][2] > 0 && b[1][1] > 0 && b[2][0] > 0) ans = true;
    if (b[0][0] > 0 && b[0][1] > 0 && b[0][2] > 0) ans = true;
    if (b[1][0] > 0 && b[1][1] > 0 && b[1][2] > 0) ans = true;
    if (b[2][0] > 0 && b[2][1] > 0 && b[2][2] > 0) ans = true;
    if (b[0][0] > 0 && b[1][0] > 0 && b[2][0] > 0) ans = true;
    if (b[0][1] > 0 && b[1][1] > 0 && b[2][1] > 0) ans = true;
    if (b[0][2] > 0 && b[1][2] > 0 && b[2][2] > 0) ans = true;

    cout << (ans ? "Yes" : "No") << endl;

}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	ll n,k;
	cin>>n>>k;
	vi a(n),b(n);
	rep(i,n)cin>>a[i]>>b[i];
	
	ll sum=0;
	rep(i,n)if(((~k)&a[i])==0)sum+=b[i];
	ll out=sum;
	while(k){
		ll t=k;
		k--;
		sum=0;
		rep(i,n)if(((~k)&a[i])==0)sum+=b[i];
		out=max(out,sum);
		k=t&k;
	}
	cout<<out<<endl;
}








Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 998244353;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd_calc(T a, T b){ if(b){ return gcd_calc(b, a % b); }else{ return a; }}
template<class T> T gcd(T a, T b){ if(a < b) swap(a, b); return gcd_calc(a, b); }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
inline int at(int x, int k){ return (x >> k) & 1; }
random_device rnd;

int main(){
    int N, M, C;
    cin >> N >> M >> C;
    int B[M];
    cins(B, B + M);
    int ans = 0;
    for(int i = 0; i < N; i++){
        int A[M];
        cins(A, A + M);
        int sum = C;
        for(int j = 0; j < M; j++){
            sum += A[j] * B[j];
        }
        ans += (sum > 0);
    }
    cout << ans << endl;
}


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

using namespace std;

typedef long long LL;

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




	}
	sort(a, a+n);
	cout << a[n-1] - a[0]<<endl;
	return 0;
}


Measured memory_bytes: 256
X = int(input())
import math
def isprime(x):
    if x < 2:
        return False
    elif x == 2:
        return True
    elif x%2 == 0:
        return False
    for i in range(3,math.floor(math.sqrt(x)+1),2):
        if x%i == 0:
            return False
    return True

for x in range(X,100004):
    if isprime(x):
        print(x)
        exit()


Measured memory_bytes: 3060
N = int(input())
A = list(map(int,input().split()))

sum_A = sum(A) % (10 ** 9 + 7)
ans = 0

for i in range(len(A)):
  if sum_A - A[i] < 0:
    sum_A = sum_A - A[i] + (10 ** 9 + 7)
  else:
    sum_A -= A[i]
  ans += A[i] * sum_A % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))

Measured memory_bytes: 105208
#include <stdio.h>

int main() {
	unsigned long N, A, B;
	unsigned long x, y;
	scanf("%lu %lu %lu", &N, &A, &B);
	x = N / (A + B);
	y = N % (A + B);
	if (A < y) {
		y = A;
	}
	x = x * A;
	printf("%ld\n", x + y);
	return 0;
}


Measured memory_bytes: 128
fun main(args: Array<String>) {
    val (n ,m, x) = readLine()!!.split(' ').map { it.toInt() }

    var min = Int.MAX_VALUE
    val arr = Array(n) {listOf<Int>()}
    repeat(n) {
        arr[it] = readLine()!!.split(' ').map { it.toInt() }
    }

    fun chk(buy: BooleanArray) {
        var plice = 0
        val exp = IntArray(m) {0}
        val fin = BooleanArray(m) {false}
        var clear = 0
        repeat(n) {
            if (buy[it]) {
                plice += arr[it][0]
                for (i in 1 .. m) {
                    exp[i-1] += arr[it][i]
                    if (!fin[i-1] && exp[i-1] >= x) {
                        fin[i-1] = true
                        clear++
                    }
                }
            }
        }
        if (clear == m) min = Math.min(min, plice)
    }

    val buyList = BooleanArray(n) { false }
    fun create(d:Int) {
        arrayOf(true,false).forEach {
            buyList[d] = it
            if (d+1 == n) {
                chk(buyList)
            } else {
                create(d+1)
            }
        }
    }

    create(0)
    if (min == Int.MAX_VALUE) println(-1)
    else println(min)
}


Measured memory_bytes: 38892
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
using namespace std;
const int N = 1e6 + 5;
const ll inf = -1e18;
const int MOD = 1e9 + 7;


ll calc(ll n){
   ll ans = 0;
   while(n){
      ans += n % 10;
      n = n / 10;
   }
   return ans;
}
int main(){
   fast;
   ll n, t, ans = 1e12;
   cin >> n;
   for(int i = 1; i < n; i += 1){
      t = calc(abs(i)) + calc(abs(n - i));
      ans = min(ans, t);
   }
   cout << ans;



   return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define int long long int
#define float double
#define pb push_back
#define FF first
#define SS second
#define N 100005
#define MOD 1000000007
#define fn(i,n) for(int i=0;i<n;i++)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pii pair<int,int>
#define mp make_pair
#define INF 9223372036854775807
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

signed main() 
{
    speed;
    //freopen("input.tXt","r",stdin);
    //freopen("output.tXt","w",stdout);

    int n,k;
    cin>>n>>k;
    int A[n+1];
    fn(i,n) cin>>A[i+1];
    A[0]=A[1];
    int dp[n+1];
    fill_n(dp,n+1,INF);
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i-j>=0) dp[i]=min(dp[i],dp[i-j]+abs(A[i]-A[i-j]));
        }
    }
    cout<<dp[n];
}   

Measured memory_bytes: 5108
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

	ll a, b, d;
	while (true)
	{
		cin >> a >> b >> d;
		if (a == 0 && b == 0 && d == 0)
			break;
		ll x = INF, y = INF;
		for (int i = -100000; i < 100000; i++)
		{
			if ((d - a * i) % b == 0)
			{
				ll xtmp = abs(i), ytmp = abs((d - a * i) / b);
				if (x + y >= xtmp + ytmp && a * x + b * y >= a * xtmp + b * ytmp)
				{
					x = xtmp;
					y = ytmp;
				}
			}
		}
		cout << x << " " << y << endl;
	}
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int A,B,K;cin>>A>>B>>K;

  for(int t=1;t<=K;t++){
    if(t%2==1){
      if(A%2==1)A--;
      int temp=A;
      A/=2;
      B+=temp/2;
    }else{
      if(B%2==1)B--;
      int temp=B;
      B/=2;
      A+=temp/2;
    }
  }

  cout<<A<<" "<<B<<endl;

  return 0;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A,B=[0]*n,[0]*n
    for i in range(n):
        A[i],B[i]=map(int,input().split())
    A.sort()
    B.sort()
    if n%2==1:
        print(B[n//2]-A[n//2]+1)
    else:
        print(int(((B[n//2-1]+B[n//2])/2-(A[n//2-1]+A[n//2])/2)*2)+1)

if __name__=='__main__':
    main()

Measured memory_bytes: 74356
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

const ll mod = 1000000007;
ll fact[200200];
ll invfact[200200];

inline ll take_mod(ll a) { return (a % mod + mod) % mod; }

inline ll add(ll a, ll b) { return take_mod(a + b); }

inline ll sub(ll a, ll b) { return take_mod(a - b); }

inline ll mul(ll a, ll b) { return take_mod(a * b); }

inline ll pow(ll x, ll n) {
  ll res = 1LL;
  while (n > 0) {
    if (n & 1) res = mul(res, x);
    x = mul(x, x);
    n >>= 1;
  }
  return res;
}

ll mod_inv(ll x) { return pow(x, mod - 2); }

void make_fact(ll n) {
  fact[0] = 1;
  ll res = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = res;
    res = mul(res, i + 1);
  }
}

void make_invfact(ll n) {
  invfact[0] = 1;
  invfact[n] = mod_inv(fact[n]);
  for (int i = n - 1; i >= 1; i--) {
    invfact[i] = mul(invfact[i + 1], i + 1);
  }
}

ll perm(ll n, ll k) { return mul(fact[n], invfact[n - k]); }

ll comb(ll n, ll k) { return mul(mul(fact[n], invfact[n - k]), invfact[k]); }

int main() {
  ll N, K;

  cin >> N >> K;
  vector<ll> lst;
  for (int i = 0; i < N; i++) {
    ll tmp;
    cin >> tmp;
    lst.emplace_back(tmp);
  }

  ll ans = 0;

  ll invNum_inN = 0;
  for (int i = 0; i <= N - 2; i++) {
    for (int j = i + 1; j <= N - 1; j++) {
      if (lst[i] > lst[j]){
        invNum_inN++;
      }
    }
  }

  ans += mul(K, invNum_inN);

  ll largerSum = 0;
  for (int i = 0; i <= N - 1; i++) {
    ll largerNum = 0;
    for (int j = 0; j <= N - 1; j++) {
      if (lst[i] < lst[j]) largerNum++;
    }
    largerSum = add(largerSum, largerNum);
  }
  ll coeff = 0;
  coeff = mul(K, K - 1);
  coeff = mul(mod_inv(2), coeff);

  ans += mul(largerSum, coeff);
  ans = take_mod(ans);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,read().split())

d = {}


"""
res = [[0]*100 for _ in range(100)]
for i in range(128):
    for j in range(128):
        u = i^j
        v = i+j
        if u<100 and v<100: res[u][v] = 1

x = 0
for i in range(n+1):
    for j in range(n+1):
        x += res[i][j]

for i in res[:10]:
    print(i[:10])

for i in range(100):
    for j in range(1,100):
        res[i][j] += res[i][j-1]
for i in range(1,100):
    for j in range(100):
        res[i][j] += res[i-1][j]

#for i in res[:10]:
#    print(i[:10])
"""



def f(n,m):
    if (n,m) in d: return d[(n,m)]
    if n<0 or m<0:
        return 0
    if n==0:
        return max(1+n//2,1+m//2)
    if m==0:
        return 1

    nn = n>>1 if n&1 else (n>>1)-1
    mm = m>>1 if m&1 else (m>>1)-1
    
    
    #print(f"({n},{m})", f(nn,mm),f(n>>1,m>>1),f(n>>1,(m>>1)-1))    
    v =  f(nn,mm) + f(n>>1,m>>1) + f(n>>1,(m>>1)-1)
    d[(n,m)] = v
    #assert v == res[n][m]
    return v

ans = f(n,n)
print(ans%(10**9+7))









Measured memory_bytes: 9224
#include <iostream>
#include <string>
#include <vector>


using namespace std;

//Lower
int main(){
	long long int n=0,num=0;
	vector<long long int> h;
	int cnt=0,ans=0;

	cin>>n;

	for(int i=0;i<n;i++){
		cin>>num;
		h.push_back(num);
		if(i==0){}
		else {
			if(h[i-1]>=h[i]){
				cnt++;
				if(ans<cnt){
				ans=cnt;
				}
			}
			else{
				if(ans<cnt){
				ans=cnt;
				}
				cnt=0;
			}
		}
	}
		cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 1400
#![allow(non_snake_case)]
#[allow(unused_imports)]
use std::io::{self, Write};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, char) => {
        read_value!($next, String).chars().collect::<Vec<char>>()[0]
     };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
     };
    ($next:expr, isize1) => {
        read_value!($next, isize) - 1
    };
     ($next:expr, $t:ty) => {
         $next().parse::<$t>().expect("Parse error")
    };
}
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}
#[allow(dead_code)]
const MOD: usize = 1000000007;
#[allow(dead_code)]
fn to_num(c: char) -> i64 {
    c as i64 - 48
}


fn main() {
    input!{
        x: usize,
    }
    println!("{}", if x < 1200 { "ABC" } else { "ARC" });
}

Measured memory_bytes: 4352
/**
    AUTHOR:Jun_SH
    TIME:2019/6/16
    PROBLEM:ABC130_f
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double inf=1e9+10;
double pos[4][3];
double cal(double t){
    double r[4];
    for(ll i=0;i<4;++i){
        r[i]=max({pos[i][0]+t,pos[i][1]-t,pos[i][2]});
    }
    return (r[0]+r[2])*(r[1]+r[3]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    for(ll i=0;i<4;++i)
    for(ll j=0;j<3;++j)
        pos[i][j]=-inf;
    for(ll i=1;i<=n;++i){
        double x,y;
        string d;
        cin>>x>>y>>d;
        if(d=="U"){
            pos[0][2]=max(pos[0][2],x);
            pos[1][1]=max(pos[1][1],-y);
            pos[2][2]=max(pos[2][2],-x);
            pos[3][0]=max(pos[3][0],y);
        }
        else if(d=="D"){
            pos[0][2]=max(pos[0][2],x);
            pos[1][0]=max(pos[1][0],-y);
            pos[2][2]=max(pos[2][2],-x);
            pos[3][1]=max(pos[3][1],y);
        }
        else if(d=="L"){
            pos[0][1]=max(pos[0][1],x);
            pos[1][2]=max(pos[1][2],-y);
            pos[2][0]=max(pos[2][0],-x);
            pos[3][2]=max(pos[3][2],y);
        }
        else {
            pos[0][0]=max(pos[0][0],x);
            pos[1][2]=max(pos[1][2],-y);
            pos[2][1]=max(pos[2][1],-x);
            pos[3][2]=max(pos[3][2],y);
        }
    }
    double ans=cal(0);
    for(ll i=0;i<4;++i){
        if(pos[i][2]-pos[i][0]>0)ans=min(ans,cal(pos[i][2]-pos[i][0]));
        if(pos[i][1]-pos[i][2]>0)ans=min(ans,cal(pos[i][1]-pos[i][2]));
        if(pos[i][1]-pos[i][0]>0)ans=min(ans,cal((pos[i][1]-pos[i][0])/2.0));
    }
    cout<<setprecision(20)<<ans<<endl;
}


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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long min = (long) 1e18;
		for(int t=0;t<2;t++){
		
			for(long x=1;x<=H;x++){
				long[] s = new long[3];
				s[0] = x * W;
				s[1] = (H - x) * (W / 2);
				s[2] = H * W - s[0] - s[1];
				
				Array.Sort(s);
				min = Math.Min(s[2] - s[0], min);
				
				s[0] = x * W;
				s[1] = ((H - x) / 2) * W;
				s[2] = H * W - s[0] - s[1];
				
				Array.Sort(s);
				min = Math.Min(s[2] - s[0], min);
			}
			
			var tmp = H; H = W; W = tmp;
		}
		Console.WriteLine(min);
		
		
	}
	long H,W;
	public Sol(){
		var d = rla();
		H = d[0]; W = d[1];
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 15440
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

int N, Q, ans; char str[200005], tmp[5];
struct Spell {char c; int d;} sp[200005];

inline bool check_l(int pos){
	for(register int i = 1; i <= Q; i++)
		if(sp[i].c == str[pos] && (pos += sp[i].d) < 1) return 1;
	return 0;
}

inline bool check_r(int pos){
	for(register int i = 1; i <= Q; i++)
		if(sp[i].c == str[pos] && (pos += sp[i].d) > N) return 1;
	return 0;
}

int main(){
	getint(N), getint(Q), scanf("%s", str + 1);
	for(register int i = 1; i <= Q; i++){
		scanf("%s", tmp), sp[i].c = *tmp;
		scanf("%s", tmp), sp[i].d = *tmp == 'L' ? -1 : 1;
	}
	int l = 0, r = N;
	while(l < r){
		const int mid = l + r + 1 >> 1;
		if(check_l(mid)) l = mid;
		else r = mid - 1;
	}
	ans = l, l++, r = N + 1;
	while(l < r){
		const int mid = l + r >> 1;
		if(check_r(mid)) r = mid;
		else l = mid + 1;
	}
	ans += N - l + 1;
	return printf("%d\n", N - ans), 0;
}

Measured memory_bytes: 2048
#pragma region
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()
#pragma endregion


int main()
{
	int n; cin >> n;
	vector<ll> a(n); rep(i, n)cin >> a[i];
	vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
	rep(i, n + 1)dp[i][i] = 0;
	for (int l = 1; l <= n; ++l)
	{
		for (int i = 0; i + l <= n; ++i)
		{
			int j = i + l;
			if ((n - l) % 2 == 0)
			{
				dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1]);
			}
			else
			{
				dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1]);
			}
		}
	}
	cout << dp[0][n] << endl;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W;cin>>H>>W;
  vector<string>S(H);
  for(int i=0;i<H;i++)cin>>S[i];
  vector<vector<int>>L(H,vector<int>(W,-1));
  vector<vector<int>>R(H,vector<int>(W,-1));
  vector<vector<int>>U(H,vector<int>(W,-1));
  vector<vector<int>>D(H,vector<int>(W,-1));
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)
    if(S[i][j]=='.')L[i][j]=(j>0?L[i][j-1]:-1)+1;
  for(int i=0;i<H;i++)for(int j=W-1;j>=0;j--)
    if(S[i][j]=='.')R[i][j]=(j<W-1?R[i][j+1]:-1)+1;
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)
    if(S[i][j]=='.')U[i][j]=(i>0?U[i-1][j]:-1)+1;
  for(int i=H-1;i>=0;i--)for(int j=0;j<W;j++)
    if(S[i][j]=='.')D[i][j]=(i<H-1?D[i+1][j]:-1)+1;
  int M=0;
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)
    if(L[i][j]!=-1&&R[i][j]!=-1&&U[i][j]!=-1&&D[i][j]!=-1)
      M=max(M,L[i][j]+R[i][j]+U[i][j]+D[i][j]);
  cout<<M+1<<endl;
}



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

int main() {
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;
	if (b - a > k ||c-a>k||d-a>k||e-a>k||d-b>k||e-b>k||e-c>k|| c - b > k || d - c > k || e - d > k) {
		cout << ":(" << endl;
	}
	else {
		cout << "Yay!"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;
typedef pair<int,int> P;

int main(){
  int n;cin >> n;
  int m; cin >> m;
  bool frag[n];
  int num[n];
  rep(i,n) frag[i] = false;
  rep(i,n) num[i] = 1;
  frag[0] = true;
  rep(i,m){
    int x,y; cin >> x >> y;
    if(num[x-1] > 0){
      if(frag[x-1]){
        if(num[x-1]==1){
          frag[x-1]=false;
          frag[y-1]=true;
        }else{
          frag[y-1]=true;
        }
      }
      num[x-1]--; num[y-1]++;
    }
  }
  int ans = 0;
  rep(i,n){
    if(frag[i]) ans++;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 768
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


n, a, b = MAP()

ans = pow(2, n, mod) - 1


fact = [1] * (2*10**5+1)
for i in range(1, 2*10**5+1):
	fact[i] = (fact[i-1] * i)%mod

def C(n, a):
	tmp = 1
	for i in range(n, n-a, -1):
		tmp = (tmp*i)%mod
	return tmp*pow(fact[a], mod-2, mod)

print((ans - C(n, a) - C(n, b))%mod)

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

int main() {
    int a, b, c; cin >> a >> b >> c;
    int fa = a, fb = b, fc = c;
    int cnt = 0;
    while (a%2 + b%2 + c%2 == 0) {
        int na, nb, nc;
        na = b/2 + c/2;
        nb = c/2 + a/2;
        nc = a/2 + b/2;
        if (na == fa && nb == fb && nc == fc) {
            cout << -1 << endl;
            return 0;
        }
        a = na; b = nb; c = nc;
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

  int n,cnt=0;
  cin>>n;

  int a[101];

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


  for(int i=0;i<n;i++){
    int maxi=i;
    for(int j=i+1;j<n;j++){
      if(a[j]<a[maxi]){
	maxi=j;
      }
    }
    if(maxi!=i){
      cnt++;
      swap(a[maxi],a[i]);
    }
  }

  for(int i=0;i<n;i++){
    if(i==n-1){
      cout<<a[i]<<endl;
    }else{
      cout<<a[i]<<" ";
    }
  }

  cout<<cnt<<endl;
  return 0;

}



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

int main(){
  int a,b;
  cin >> a >> b;
  if (a==0 && 1868 <= b && b <= 1911){
    cout << "M" << 44-(1911-b)<< endl;
  }
  else if (a==0 && 1912 <= b && b <= 1925){
    cout << "T" << 14-(1925-b) << endl;
  }
  else if (a==0 && 1926 <= b && b <= 1988){
    cout << "S" << 63-(1988-b) << endl;
  }
  else if (a==0 && 1989 <= b && b <= 2016){
    cout << "H" << 28-(2016-b) << endl;
  }
  else if (a==1){
    cout << 1911-(44-b) << endl;
  }
  else if (a==2){
    cout << 1925-(14-b) << endl;
  }
  else if (a==3){
    cout << 1988-(63-b) << endl;
  }
  else if (a==4){
    cout << 2016-(28-b) << endl;
  }
    return 0;
}

  

  



Measured memory_bytes: 3116
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())
#define bitcnt(x) __builtin_popcount(x)

typedef long long ll;

const int MAX = 64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;

//パスカルの三角形
ll pas[MAX][MAX];

void pascal(){
    rep(MAX, n) pas[n][0] = 1;
    rep(MAX-1, n) rep(MAX-1, k) {
        pas[n+1][k+1] = pas[n][k] + pas[n][k+1];
    }
}

vector <ll> v;
map <ll, int> mp;

void solve(void){
    int N, A, B;
    cin >> N >> A >> B;
    v.resize(N);
    rep(N, i) {
        scanf("%lld\n", &v[i]);
        mp[-v[i]]++;
    }
    pascal();
    sort(all(v));
    reverse(all(v));
    ll comb = 0LL, sum = 0LL;
    if (v[0] == v[A-1]) {
        int N = mp[-v[0]];
        Rep(A, B, k) comb += pas[N][k];
        printf("%lld\n%lld\n", v[0], comb);
        return;
    }
    int cnt = 0;
    for (auto p : mp) {
        if (p.second + cnt >= A) {
            sum -= (ll)(A-cnt)*p.first;
            comb = pas[p.second][A-cnt];
            printf("%.6lf\n%lld\n", (double)sum/A, comb);
            return;
        }
        sum -= (ll)p.second*p.first;
        cnt += p.second;
    }

    cout << "yui(*-v・)yui" << endl;
}

int main(void){
  solve();
  //cout << "yui(*-v・)yui" << endl;
  return 0;
}


Measured memory_bytes: 256
def gcd(s, t):
  if s < t:
    s, t = t, s
  if t == 0:
    return s
  else:
    return gcd(t, s % t)

R, G, B, N = map(int, input().split())
lcm = (G * B) // gcd(G, B)
r, g, b, ans = 0, 0, 0, 0
while r <= N:
  while r + g <= N:
    if (N - r - g) % B == 0:
      ans += 1
      ans += (N - r - g) // lcm
      break
    g += G
  g = 0
  r += R
print(ans)

Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var n int
	var s string
	fmt.Scan(&n, &s)

	for _, p := range []string{"SS", "SW", "WW", "WS"} {
		t := make([]byte, n)
		t[0] = p[0]
		t[1] = p[1]

		for i := 1; i < n-1; i++ {
			if (t[i] == 'S' && s[i] == 'o') || (t[i] == 'W' && s[i] == 'x') {
				t[i+1] = t[i-1]
			} else {
				if t[i-1] == 'S' {
					t[i+1] = 'W'
				} else {
					t[i+1] = 'S'
				}
			}
		}

		ok := true
		tmp := append([]byte{t[n-1]}, t...)
		tmp = append(tmp, t[0])
		for i := 1; i <= n; i++ {
			l, m, r := tmp[i-1], tmp[i], tmp[i+1]
			if s[i-1] == 'o' && m == 'S' && l == r ||
				s[i-1] == 'o' && m == 'W' && l != r ||
				s[i-1] == 'x' && m == 'S' && l != r ||
				s[i-1] == 'x' && m == 'W' && l == r {
				continue
			}

			ok = false
			break
		}

		if ok {
			fmt.Println(string(t))
			return
		}
	}

	fmt.Println(-1)
}


Measured memory_bytes: 2432
IDENTIFICATION DIVISION.
      PROGRAM-ID. 086A.
      DATA DIVISION.
      WORKING-STORAGE SECTION.
      01 INP PIC X(100).
      01 A PIC 9(5).
      01 B PIC 9(5).
      01 SEKI PIC 9(10).
      01 SHO PIC 9(10).
      01 AMA PIC 9(1).

      PROCEDURE DIVISION.
      ACCEPT INP.
      UNSTRING INP DELIMITED BY " "
      INTO A B.
      COMPUTE SEKI = A * B.
      DIVIDE SEKI BY 2 GIVING SHO REMAINDER AMA.
      IF AMA = 1
         DISPLAY "Odd"
      ELSE
         DISPLAY "Even"
      END-IF.
      STOP RUN.

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<(n); i++)
#define int long long
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;
struct edge{
    long long to;
    long long cost;
};
signed main(void){
    int n;cin>>n;
    vector<edge>G[n];
    int f,t,c,k;
    rep(i,n){
        cin>>f>>k;
        rep(j,k){
            cin>>t>>c;
            G[f].push_back({t,c});
        }
    }
    vector<int>d(n,INF);d[0]=0;
    //rep(i,n){
      //  rep(j,G[i].size()){
        //    cout<<G[i][j].to<<':'<<G[i][j].cost<<' ';
        //}
        //cout<<endl;
    //}
    priority_queue<P,vector<P>,greater<P>>que;
    que.push(P(0,0));
    while(!que.empty()){
        f=que.top().S;c=que.top().F;que.pop();
        if(d[f]<c)continue;
        rep(i,G[f].size()){
            edge e=G[f][i];
            t=e.to;
            if(d[t]>e.cost+c){
                d[t]=e.cost+c;
                que.push(P(d[t],t));
            }
        }
    }
    rep(i,n){
        cout<<i<<' '<<d[i]<<endl;
    }
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int2(n, m);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }

    map<int, int> yui;
    int ans = 0, sum = 0;
    rep(i, n) {
        sum = (sum + data[i]) % m;
        if (!sum) {
            ++ans;
        }
        ans += yui[sum];
        yui[sum]++;
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
    
typedef long long in;
typedef unsigned long long ull;
    
#define MOD 1000000007
#define mi 18446744073709551615


in dp[100001][100];
bool st[100001][100];

in kn(in r,in i,in wt[],in v[],in n)
{
    if(r<=0)
        return 0;
    if(i==n)
        return 10000000000001LL;
    if(st[r][i])
        return dp[r][i];
    st[r][i]=true;
    dp[r][i]=min(kn(r,i+1,wt,v,n),wt[i]+kn(r-v[i],i+1,wt,v,n));
    return dp[r][i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    in n,w;
    cin>>n>>w;
    in wt[n],v[n];
    for(int i=0;i<n;i++)
        cin>>wt[i]>>v[i];
    for (int i=100000;i>=0;i--)
    { 
        if (kn(i,0,wt,v,n) <= w)
        {
            cout<<i;
            return 0;
        } 
    }
    cout<<0; 
    return 0;
}

Measured memory_bytes: 88192
<?php
fscanf(STDIN, "%d %d",$l,$r);
$min = INF;
# lより1大きい数iを取得
for($i=$l;$i<$r;$i++){
	
	#iより大きい数jの取り得る値で判別
	for($j=$l+1;$j<=$r;$j++){
		
		$tmp = ($i * $j) % 2019;
		if($min > $tmp){
			
			$min = $tmp;
		}
		if ($min == 0) {
			echo $min;
			return;
		}
	}
}
echo $min;
?>

Measured memory_bytes: 3700
from math import *

N, D = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        d2 = 0
        for k in range(D):
            d2 += (X[i][k] - X[j][k])**2
        if sqrt(d2)*10%10 == 0:
            ans += 1

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print1(a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=55;
//i_am_noob
int n,a[8],b[8],c[8],k=0,ans1=0,ans2=0;
bool ok;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n;
	rep(n) cin >> a[i];
	rep(n) cin >> b[i];
	rep(n) c[i]=i+1;
	while(1){
		ok=true;
		rep(n) if(a[i]!=c[i]) ok=false;
		if(ok) ans1=k;
		ok=true;
		rep(n) if(b[i]!=c[i]) ok=false;
		if(ok) ans2=k;
		k++;
		if(!next_permutation(c,c+n)) break;
	}
	print1(abs(ans1-ans2));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
#define FOR(i,a,b) for (ll i=(a); i<(b); i++)
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)
int main() {
	ios::sync_with_stdio(false);

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

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;

int pow(int a, int b, int m)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

int fact[N], invfact[N];

int modinv(int k)
{
	return pow(k, MOD-2, MOD);
}

void precompute()
{
	fact[0]=fact[1]=1;
	for(int i=2;i<N;i++)
	{
		fact[i]=fact[i-1]*i;
		fact[i]%=MOD;
	}
	invfact[N-1]=modinv(fact[N-1]);
	for(int i=N-2;i>=0;i--)
	{
		invfact[i]=invfact[i+1]*(i+1);
		invfact[i]%=MOD;
	}
}

int nCr(int x, int y)
{
	if(y>x)
		return 0;
	int num=fact[x];
	num*=invfact[y];
	num%=MOD;
	num*=invfact[x-y];
	num%=MOD;
	return num;
}

int32_t main()
{
	IOS;
	precompute();
	int n, k;
	cin >> n >> k;
	int ans = 0;
	for(int i = k; i <= n + 1; i++)
	{
		int mn = i * (i - 1) / 2;
		int mx = n * (n + 1) / 2 - (n - i) * (n - i + 1) / 2;
		ans += mx - mn + 1;
		ans %= MOD;
	}
	ans %= MOD;
	cout << ans;
	return 0;
}

Measured memory_bytes: 6764
MOD = 10**9+7

n,a,b = map(int,input().split())
x = []
y = []
tmp1 = 1
tmp2 = 1
for i in range(b+1):
    tmp1 *= (n-i)
    tmp1 %= MOD
    tmp2 *= (i+1)
    tmp2 %= MOD
    x.append(tmp1)
    y.append(tmp2)
A = x[a-1]*pow(y[a-1], MOD-2, MOD)%MOD
B = x[b-1]*pow(y[b-1], MOD-2, MOD)%MOD
print((pow(2,n,MOD)-A-B-1)%MOD)


Measured memory_bytes: 18948
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<climits>
#include<cstdlib>
#include<map>
#include<math.h>
#include<utility>
using namespace std;
typedef long long ll;

int main(){
  int n, y;
  cin >> n >> y;
  bool flag=false;
  for(int i=0; i<=n; i++){
    for(int j=0; j<=n-i; j++){
      int k = n - j - i;
      if(10000*i+5000*j+1000*k == y && !flag){
        cout << i << " " << j << " " << k << endl;
        flag = true;
      }
    }
  }
  if(!flag) cout << "-1 -1 -1" << endl;
}



Measured memory_bytes: 256
/*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
ll a[maxn];
ll t;
int n;
void solve() {
    cin >> n >> t;
    for (int i = 0; i < n; i++) cin >> a[i];
    ll p = 0;
    ll mi = a[0];
    for (int i = 1; i < n; i++) {
        p = max(p, a[i] - mi);
        mi = min(mi, a[i]);
    }
    set<ll> tl, tr;
    mi = a[0];
    int last = 0;
    for (int i = 1; i < n; i++) {
        if(a[i] - mi == p) {
            tl.insert(last);
            tr.insert(i);
        }
        if(a[i] <= mi) {
            mi = a[i];
            last = i;
        }
    }
    cout << min(tl.size(), tr.size()) << endl;

}
int main() {
   // freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    solve();
    return 0;
}


Measured memory_bytes: 5760