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

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<string> v(n);

  for (int i = 0; i < n; i++) {
    cin >> v[i];
    sort(v[i].begin(), v[i].end());
  }

  sort(v.begin(), v.end());

  long same_cnt = 1;
  long result = 0;

  auto tmp = v[0];
  for (int i = 1; i < n; i++) {
    if (v[i] == tmp) {
      same_cnt++;
    } else {
      if (same_cnt > 0) {
        result += same_cnt * (same_cnt - 1) / 2;
      }
      same_cnt = 1;
    }

    tmp = v[i];
  }
  if (same_cnt > 0) {
    result += same_cnt * (same_cnt - 1) / 2;
  }

  cout << result << endl;

  return 0;
}



Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

const int M_N=200001;

struct UnionFind{
    int par[M_N];
    int rank[M_N];

    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }

    int find(int x){
        if(par[x]==x){
            return x;
        }
        else{
            return par[x]=find(par[x]);
        }
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};

int main(){
    int N,K,L;
    cin >> N >> K >> L;
    UnionFind a,b;
    a.init(N);
    b.init(N);
    for(int i=0;i<K;i++){
        int u,v;
        cin >> u >> v;
        a.unite(u-1,v-1);
    }
    for(int i=0;i<L;i++){
        int u,v;
        cin >> u >> v;
        b.unite(u-1,v-1);
    }
    map<P,int> mp;
    for(int i=0;i<N;i++){
        mp[make_pair(a.find(i),b.find(i))]++;
    }
    for(int i=0;i<N;i++){
        cout << mp[make_pair(a.find(i),b.find(i))] << ((i==N-1)?"\n":" ");
    }
    return 0;
}

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

int main(){
  int n ,m;
  while( true ){
    cin >> n >> m;
    if( n == 0 && m == 0 ){
      break;
    }
    string tail[n];
    int mass[n][m];
    for( int i=0 ; i<n ; i++ ){ 
      for( int j=0 ; j<m ; j++ ){
	mass[i][j] = 0;
      }
    }

    for( int i=0 ; i<n ; i++ ){
      cin >> tail[i];
    }
    
    n = 0; m = 0;
    
    while( true ){
      if( mass[n][m] == 1 ){
	cout << "LOOP" << endl;
	break;
      }
      else if( tail[n][m] == '>' ){
	mass[n][m] = 1;
	m++;
      }
      else if( tail[n][m] == '<' ){
     	mass[n][m] = 1;
	m--;
      }
      else if( tail[n][m] == '^' ){
	mass[n][m] = 1;
	n--;
      }
      else if( tail[n][m] == 'v' ){
       	mass[n][m] = 1;
	n++;
      }
      else if( tail[n][m] == '.' ){
	cout << m << ' ' << n << endl;
	break;
      }
    }
  }
}

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

#define F first 
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 1010;

int n;
int a[N], l[N], r[N];

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
	
	for (int i = 1; i <= n; i ++ ) l[i] = gcd(l[i - 1], a[i]);
	for (int i = n; i >= 1; i -- ) r[i] = gcd(r[i + 1], a[i]);
	
	int res = 0;
	for (int i = 1; i <= n; i ++ ) res = max(res, gcd(l[i - 1], r[i + 1]));
	printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 4888
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    string ans = "No";
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            if(i * j == n){
                ans = "Yes";
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import bisect

def main():
	n,k=MI()
	A=LI()
	B=[[] for _ in range(2*10**5+10)]

	for i,v in enumerate(A):
		B[v-1].append(i)

	for li in B:
		if li:
			li.append(li[0])

	#print(A)
	#print(B)

	C=[]

	s=0
	t=-1

	while t<n-1:
		a=A[s]-1
		ti=bisect.bisect_left(B[a][:-1],s)+1
		t=B[a][ti]
		#print(s,t)
		if s>=t:
			C.append(s)
		s=t+1
	#print(C)

	k%=len(C)+1
	#print(k)

	if k==0:
		print()
		exit()

	s=C[k-1]
	#print(s)

	ans=[]

	while s<n:
		a=A[s]-1
		si=bisect.bisect_left(B[a][:-1],s)
		if si+1==len(B[a][:-1]):
			ans.append(a+1)
			s+=1
		else:
			s=B[a][si+1]+1
	print(*ans)



if __name__ == "__main__":
	main()


Measured memory_bytes: 129568
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
void sch(int n, int k, string s, string &s1, string &s2, map<pair<string, string>, ll> &mp) {
  if(n == k) {
    mp[{s1, s2}]++;
  } else {
    s1.push_back(s[k]);
    sch(n, k+1, s, s1, s2, mp);
    s1.pop_back();
    s2.push_back(s[k]);
    sch(n, k+1, s, s1, s2, mp);
    s2.pop_back();
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  string s; cin >> s;
  map<pair<string, string>, ll> mp1, mp2;
  string s1 = "", s2 = "";
  sch(n, 0, s, s1, s2, mp1);
  reverse(s.begin(), s.end());
  sch(n, 0, s, s1, s2, mp2);
  auto it1 = mp1.begin();
  auto it2 = mp2.begin();
  ll ans = 0;
  while(it1 != mp1.end() && it2 != mp2.end()) {
    if(it1->first == it2->first) {
      ans += it1->second * it2->second;
      it1++;
      it2++;
    } else if(it1->first < it2->first) {
      it1++;
    } else {
      it2++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 86272
from fractions import gcd


A, B, C, D = map(int, input().split())
LCM = C * D // gcd(C, D)
print(
    B
    - A
    + 1
    - B // C
    + (A - 1) // C
    - B // D
    + (A - 1) // D
    + B // LCM
    - (A - 1) // LCM
)


Measured memory_bytes: 5048
program view
  implicit none
  integer :: N,i,j,OKn,tfHi
  integer,allocatable :: H(:)

  read(*,*) N
  OKn=0
  allocate(H(N))
  read(*,*) H
  do i=1,N
     tfHi=1
     do j=1,i
!        write(*,*) i,j                                                         
        if(H(j).gt.H(i)) then
           tfHi=0
        endif
     enddo
     OKn=OKn+tfHi
  enddo
  write(*,'(i0)') OKn
  deallocate(H)





end program view


Measured memory_bytes: 640
#include<stdio.h>

int main(void){
    int N;
    scanf("%d",&N);

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

    int ans=0;

    int wa;
    wa=d[0];
    for(i=1;i<N;i++){
        ans+=wa*d[i];
        wa+=d[i];
    }

    printf("%d",ans);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int A,B,C,D;
    cin >> A;
    D = A % 10; A /= 10;
    C = A % 10; A /= 10;
    B = A % 10; A /= 10;
    if (A + B + C + D == 7) {
        printf("%d+%d+%d+%d=7\n", A,B,C,D);
        return 0;
    }
    if (A + B + C - D == 7) {
        printf("%d+%d+%d-%d=7\n", A,B,C,D);
        return 0;
    }
    if (A + B - C + D == 7) {
        printf("%d+%d-%d+%d=7\n", A,B,C,D);
        return 0;
    }
    if (A + B - C - D == 7) {
        printf("%d+%d-%d-%d=7\n", A,B,C,D);
        return 0;
    }
    if (A - B + C + D == 7) {
        printf("%d-%d+%d+%d=7\n", A,B,C,D);
        return 0;
    }
    if (A - B + C - D == 7) {
        printf("%d-%d+%d-%d=7\n", A,B,C,D);
        return 0;
    }
    if (A - B - C + D == 7) {
        printf("%d-%d-%d+%d=7\n", A,B,C,D);
        return 0;
    }
    if (A - B - C - D == 7) {
        printf("%d-%d-%d-%d=7\n", A,B,C,D);
        return 0;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main(){
    int K, N;
    cin >> N >> K;
    int p[N];

    rep(i, N){
        cin >> p[i];
    }

    double e[N];
    rep(i, N){
        e[i] = 0;
        double tmp = (1.0)/ (double)p[i];
        rep(j, p[i]) {
            e[i] += tmp*(double)(j+1);
        }
    }

//    rep(i, N){
//        cout << e[i+1] - e[i] << endl;
//    }
    double ans = 0;
    rep(i, K) {
        ans += e[i];
    }
//    cout << ans << endl;
    double tmp = ans;
    REP(i, K, N) {
        tmp = tmp - e[i-K] + e[i];
        if (tmp > ans) {
            ans = tmp;

        }

//        cout << ans << endl;
    }

    cout << std::setprecision(12) << ans << endl;


}

Measured memory_bytes: 2688
import math
def main():
    ans = float('inf')
    N = int(input())
    for i in range(1, int(math.sqrt(N))+1):
        if N % i == 0:
            ans = min(ans, max(len(str(i)), len(str(N//i))))
    return ans


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3060
#include <bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector <ll>
#define vii vector <int>
#define vpii vector <pii>
#define vpll vector <pll>
#define ff first
#define ss second
#define matrix vector <vll>
#define all(v) v.begin(),v.end()
#define PQ priority_queue
using namespace std;
ll pow(ll a, ll b){
	ll res = 1;
	while(b > 0){
		if(b&1) res*=a;
		b/=2;
		a*=a;
	}
	return res;
}
int main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int h, w;
	cin >> h >> w;
	char arr[h][w];
	for(int i = 0; i < h; i++)
		for(int j = 0; j < w; j++) cin >> arr[i][j];
	vector <vii> dp(h, vii (w));
	dp[0][0] = 1;
	for(int i = 0; i < h; i++){
		if(arr[i][0] == '#') break;
		dp[i][0] = 1;
	}
	for(int j = 0; j < w; j++){
		if(arr[0][j] == '#') break;
		dp[0][j] = 1;
	}
	for(int i = 1; i < h; i++){
		for(int j = 1; j < w; j++){
			if(arr[i][j] == '#') continue;
			dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
		}
	
	}
	cout << dp[h-1][w-1] << "\n";
	return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
void comb(vector<vector <long long> > &v){
  for(int i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(int k = 1;k <v.size();k++){
    for(int j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j])%mod;
    }
  }
}

int main(){
    int  N, K;
    cin >> N >> K;
    vector<vector<long long> > v(2000,vector<long long>(2000,0));
    vector<int> ans(2000);    
    int left = N-K+1, right;
    comb(v);
    for(int i=1; i<K+1; i++){
	ans[i]= (v[left][i]* v[K-1][i-1])%mod;
    }
    for(int i=1; i<K+1; i++){
	cout << ans[i]<<endl;
    }
}



Measured memory_bytes: 31616
#include<stdio.h>
using namespace std;

int a[500005],l[250005],r[250005],x=0;

void s(int a[],int n,int left,int mid,int right){
    int n1=right-mid;
    int n2=mid-left;
    for(int i=0;i<n1;i++) r[i]=a[i+mid];
    for(int i=0;i<n2;i++) l[i]=a[i+left];
    r[n1]=l[n2]=2000000000;
    int i=0,j=0;
    for(int g=left;g<right;g++){
        x++;
        if(l[i]<=r[j]){
            a[g]=l[i++];
        }
        else{
            a[g]=r[j++];
        }
    }
}

void sm(int a[],int n,int left,int right){
    if(left+1<right){
        int mid=(right+left)/2;
        sm(a,n,left,mid);
        sm(a,n,mid,right);
        s(a,n,left,mid,right);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sm(a,n,0,n);
    for(int i=0;i<n;i++){
        if(!i) printf("%d",a[i]);
        else printf(" %d",a[i]);
    }
    printf("\n%d\n",x);
    return 0;
}

Measured memory_bytes: 6472
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,k;

int main(void){
	scanf("%d%d",&n,&k);
	ll ans=0;
	for(int i=k+1;i<=n;i++){
		int s=k;
		int lo=(n-k)/i;
		int ga=lo*i+k;
		ans+=(ll)min(i-k,n-ga+1);
		ans+=(ll)lo*(i-k);
		//printf("%lld\n",ans);
	}
	if(k==0LL)ans-=n;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
    string s;
    cin >> s;
    int a = 0;
    int z = 0;
    for(int i = 0;i<s.length();i++){//前からAを探す
        if(s[i] == 'A'){
            a = i;
            break;
        }
    }
    for(int i = s.length()-1;i>=0;--i){//後ろからZをさがす
        if(s[i] == 'Z'){
            z = i;
            break;
        }
    }
    cout << z - a +1 << endl;
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 640
import numpy as np
 
N = int(input())
 
output = np.zeros(N)
 
for x in range(1,int(np.sqrt(N))+1):
    for y in range(1,x+1):
        if x**2 + y**2 + x*y > N:
            break
        for z in range(1,y+1):
            index = x**2 + y**2 + z**2 + x*y + y*z + z*x
            
            if index > N:
                break
            
            dup = len(set([x,y,z]))
            
            if dup == 3:
                output[index-1] += 6
            elif dup == 2:
                output[index-1] += 3
            elif dup == 1:
                output[index-1] += 1
                
for i in range(N):
    print(int(output[i]))

Measured memory_bytes: 27000
function main(input) {
	let val = 100;
	let a = 1;
	while (true) {
		val += Math.floor(val * 0.01)
		if (val >= input) {
			console.log(a);
			break;
		}
		a += 1;
	}
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29756
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;

int main(){

  ll n;
  cin >> n;

  std::vector<ll> x(n);
  rep(i,n) cin >> x.at(i);
  sort(all(x));

  ll hp=1000000000000000000LL,sum;
    for(ll i=1;i<100;i++){
      sum=0;
      for(ll j=0;j<n;j++){
        sum+=(x.at(j)-i)*(x.at(j)-i);

      }

        hp=min(sum,hp);
    }

  cout << hp << endl;

}


Measured memory_bytes: 3636
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

type MyScanner struct {
	sc *bufio.Scanner
}

type MyWriter struct {
	stdout io.Writer
}

type MyPut interface{}

func getScanner(fp io.Reader) *bufio.Scanner {
	sc := bufio.NewScanner(fp)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 500001), 500000)
	return sc
}

func getHugeScanner(fp io.Reader, size int) *bufio.Scanner {
	sc := bufio.NewScanner(fp)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, size), size)
	return sc
}

func (mysc *MyScanner)String() string {
	mysc.sc.Scan()
	return mysc.sc.Text()
}

func (mysc *MyScanner)Int() int {
	i, _ := strconv.Atoi(mysc.String())
	return i
}

func (mysc *MyScanner)Int64() int64 {
	i, _ := strconv.ParseInt(mysc.String(), 10, 64)
	return i
}

func (mysc *MyScanner)Float64() float64 {
	i, _ := strconv.ParseFloat(mysc.String(), 64)
	return i
}

func (mw MyWriter)Puts(v MyPut) {
	_, _ = fmt.Fprintf(mw.stdout, "%v\n", v)
}

func Solve(stdin io.Reader, stdout io.Writer) {
	sc := MyScanner{getScanner(stdin)}
	mw := MyWriter{stdout}

	a := sc.Int()
	b := sc.Int()

	num := 1
	ans := 0

	for b > num {
		ans++
		num += a - 1
	}

	mw.Puts(ans)
}

func main() {
	Solve(os.Stdin, os.Stdout)
	return
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <string>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;

const ll MAX_W = 20, MAX_H = 20;
int tiles[MAX_H][MAX_W];
int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

void dfs(ll x, ll y, ll w, ll h) {
  tiles[y][x] = 0;

  rep(i, 4) {
      int dx = d[i][0];
      int dy = d[i][1];
      if (x + dx < 0 || x + dx >= w) continue;
      if (y + dy < 0 || y + dy >= h) continue;

      if (tiles[y + dy][x + dx] == -1) {
        dfs(x + dx, y + dy, w, h);
      }
  }
}


int main() {
  while(true) {
    ll w, h;
    cin >> w >> h;
    if (w == 0 && h == 0) break;

    string line;
    int startX;
    int startY;
    rep(i, h) {
      cin >> line;
      rep(j, w) {
        if (line[j] == '.') {
          tiles[i][j] = -1;
        } else if (line[j] == '#') {
          tiles[i][j] = 1;
        } else {
          tiles[i][j] = -1;
          startX = j;
          startY = i;
        }
      }
    }

    dfs(startX, startY, w, h);
    ll cnt = 0;
    rep(i, h) {
      rep(j, w) {
        if (tiles[i][j] == 0) ++cnt;
      }
    }
    cout << cnt << endl;
  }


  return 0;
}

Measured memory_bytes: 3088
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var NMC = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, M, C) = (NMC[0], NMC[1], NMC[2]);
        var B = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var A = new int[N][];
        for (int i = 0; i < N; i++)
            A[i] = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        var ans = 0;

        for (int i = 0; i < N; i++)
        {
            if (A[i].Zip(B, (a, b) => a * b).Sum() + C > 0)
                ans++;
        }

        WriteLine(ans);
    }
}


Measured memory_bytes: 28312
n,k=map(int,input().split())
l=list(map(int,input().split()))
m=max(l)
table=[[0,0]for i in range(m.bit_length())]
now=0
su=0
cor=1<<(m.bit_length()-1)
for i in range(m.bit_length()):
    p=[0,0]
    for j in range(n):
        p[l[j]%2]+=1
        l[j]//=2
    table[i][0]=p[0]
    table[i][1]=p[1]
if k.bit_length()>m.bit_length():
    now+=k>>m.bit_length()<<m.bit_length()
    su+=now*n
for i in range(m.bit_length()-1,-1,-1):
    p=table[i]
    if p[1]<=p[0] and now+cor<=k:
        su+=p[0]*cor
        now+=cor
    else:
        su+=cor*p[1]
    cor//=2
print(su)

Measured memory_bytes: 69008
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//const ll MOD=998244353LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={-1,-1,-1,0,0,1,1,1};
vl dy={1,-1,0,1,-1,1,0,-1};

int main(){
  ll n,k;cin>>n>>k;
  vl a(n);
  rep(i,n)cin>>a[i];
  vl b(n);
  rep(i,n)b[i]=a[i];
  ll ans=0;
  ll total=0;
  rep(i,n)total+=b[i];
  ll ans2=0;
  rep(i,n){
    if(a[i]>0){
      ans+=a[i];
      a[i]=0;
    }
    else {
      ans2+=b[i];
      b[i]=0;
    }
  }
  ll MAX=-INF;
  vl sum(n+1);
  sum[1]=a[0];
  rep(i,n-1)sum[i+2]=sum[i+1]+a[i+1];
  rep(i,n-k+1){
    MAX=max(MAX,sum[i+k]-sum[i]);
  }
  ans+=MAX;
  
  ll MIN=INF;
  vl sum2(n+1);
  sum2[1]=b[0];
  rep(i,n-1)sum2[i+2]=sum2[i+1]+b[i+1];
  rep(i,n-k+1){
    MIN=min(MIN,sum2[i+k]-sum2[i]);
  }
  ans2+=MIN;
  //for(ll i=1;i<=n;i++)cout<<sum2[i]<<" ";
  //cout<<endl;
  //cout<<total<<" "<<ans2<<" "<<MIN<<endl;
  cout<<max(ans,total-ans2)<<endl;
}

Measured memory_bytes: 3328
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int  N;

int main() {

	cin >> N;

	ll ans = 0;
	rep(i, N) {
		ans += ceil(N / (i + 1.0)) - 1;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n;
  long long k;
  cin>>n>>k;
  long long a[n];
  long long f[n];
  REP(i,n){
    cin>>a[i];
  }
  sort(a,a+n);
  REP(i,n){
    cin>>f[i];
  }
  sort(f,f+n);
  
  long long l = -1;
  long long r = a[n-1]*f[n-1];
  
  while(r-l>1){
    long long m = (l+r)/2;
    long long b[n];
    REP(i,n){
      b[i] = m/f[i];
    }
    sort(b,b+n);
    
    long long s = 0;
    REP(i,n){
      s += max(a[i]-b[i], 0LL);
    }
    if(s<=k){
      r = m;
    }else{
      l = m;
    }
  }
  
  long long ans = r;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4992
n, m = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
b = []
for _ in range(m):
    b.append(int(input()))

for i in range(n):
    s = 0
    for j in range(m):
        s += a[i][j] * b[j]
    print(s)



Measured memory_bytes: 6012
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  if(a < b) {
    a += t * v;
    b += t * w;
    if(a >= b)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  } else if(a == b) {
    cout << "YES" << endl;
  } else {
    a -= t * v;
    b -= t * w;
    if(a <= b)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
}

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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000000
#define MOD 1000000007
#define MAXR 100000
#define _GLIBCXX_DEBUG

int threemax(int a, int b, int c) {
	if (a >= b && a >= c) {
		return a;
	}
	else if (b >= a && b >= c) {
		return b;
	}
	else {
		return c;
	}
}

int threemin(int a, int b, int c) {
	if (a <= b && a <= c) {
		return a;
	}
	else if (b <= a && b <= c) {
		return b;
	}
	else {
		return c;
	}
}

void chmaxl(ll &a,ll b){
	if(a<b){
		a=b;
	}
	return;
}

void chminl(ll &a,ll b){
	if(a>b){
		a=b;
	}
	return;
}

void chmaxi(int &a,int b){
	if(a<b){
		a=b;
	}
	return;
}

void chmini(int &a,int b){
	if(a>b){
		a = b;
	}
	return;
}



int main() {
  string S,T;
  cin >> S >> T;
  bool ans=true;
  for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)){
      ans=false;
    }
  }
  if(ans){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}

Measured memory_bytes: 3600
N = int(input())

t0, x0, y0 = map(int, input().split())
if t0 < x0 + y0 or t0 % 2 != (x0 + y0) % 2:
    print("No")
    exit()

for i in range(1, N):
    t1, x1, y1 = map(int, input().split())
    dist_t, dist_x, dist_y = abs(t1-t0), abs(x1-x0), abs(y1-y0)
    # print("dist_t: {}, dist_x: {}, dist_y: {}".format(dist_t, dist_x, dist_y))
    if dist_t < dist_x + dist_y or dist_t % 2 != (dist_x + dist_y) % 2:
        print("No")
        exit()
    t0, x0, y0 = t1, x1, y1
print("Yes")


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

using tpl = tuple<int, int, int>;
typedef pair<int,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

int N, M;
int P[200010];
int Q[200010];
int C[200010];

map<int, vector<int>> G[200010];
bool used[200100];
int costs[200010];
set<int> used_by_col[200010];

void rec(int pos, int col, queue<int> &q, int cost){
    used_by_col[pos].insert(col);
    if(!used[pos]){
        used[pos] = true;
        costs[pos] = cost;
        q.push(pos);
    }
    for(int to : G[pos][col]){
        if(used_by_col[to].count(col)) continue;
        rec(to, col, q, cost);
    }
}

int main(){

    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i] >> C[i]; 
       P[i]--; Q[i]--;
        G[P[i]][C[i]].push_back(Q[i]);
        G[Q[i]][C[i]].push_back(P[i]);
    }

    used[0] = true;
    costs[0] = 0;
    queue<int> q;
    q.push(0);
    for(; q.size() > 0; ){
        int pos = q.front(); q.pop();
        int cost = costs[pos] + 1;
        for(auto p : G[pos]){
            int col = p.first;
            auto &v = p.second;
            used_by_col[pos].insert(col);
            for(auto npos : v){
                if(used_by_col[npos].count(col)) continue;
                rec(npos, col, q, cost);
            }
        }
        // for(int i= 0; i < N; i++){
        //     if(used[i]){
        //         cout << i << " ";
        //     }
        // }
        // cout << endl;
        // return 0;
    }
    if(used[N - 1]){
        cout << costs[N - 1] << endl;
    }
    else{
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 84864
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<cstdlib>
#define INF long long (int)1e18+1
#define MAX 200001
#define rep(i,n,m) for(int i=n;i<m;i++)

using namespace std;
	
vector<int>M[100001];
int main() {
	int n, m;
	cin >> n >> m;
	int x, y;
	vector<bool>isDone(n + 1, 0);
	int ans = 0;
	rep(i, 0, m) {
		cin >> x >> y;
		M[x].push_back(y);
		M[y].push_back(x);
	}
	rep(i, 1, n+1) {
		if (isDone[i])continue;
		isDone[i] = true;
		//cout << i << endl;
		ans++;
		int now;
		queue<int>que;
		for (auto a : M[i]) {
			if (isDone[a])continue;
			que.push(a);
			isDone[a] = true;
		}
		while (!que.empty()) {
			now = que.front();
			for (auto a : M[now]) {
				if (isDone[a])continue;
				que.push(a);
				isDone[a] = true;
			}
			que.pop();
		}
	}
	cout << ans - 1 << endl;
}


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

double dp[3001][3001];

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

    vector<double> p(n);
    rep(i,n) cin >> p[i];

    dp[0][0] = 1.0;

    rep(i,n){
        for(int j=0;j<=i;j++){
            dp[i+1][j+1] += dp[i][j]*p[i];
            dp[i+1][j] += dp[i][j]*(1.0-p[i]);
        }
    }
    double res = 0;
    for(int j = (n+1)/2;j<=n;j++) res+=dp[n][j];
    cout<<fixed <<setprecision(10)<<res<<endl;
    

}

Measured memory_bytes: 68992
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

int main(){

    long long int a,b,k;
    cin >> a >> b >> k;

    if(k<=a) cout << a-k << " " << b << endl;
    else if(k<a+b) cout << 0 << " " << a+b-k << endl;
    else cout << 0 <<" " << 0 << endl; 


}

Measured memory_bytes: 256
#![allow(clippy::many_single_char_names)]
// ngtio {{{
#[allow(dead_code)]
mod ngtio {
    use ::std::collections::VecDeque;

    pub struct Buffer {
        buf: VecDeque<String>,
    }

    impl Buffer {
        pub fn new() -> Self {
            Self {
                buf: VecDeque::new(),
            }
        }

        fn load(&mut self) {
            while self.buf.is_empty() {
                let mut s = String::new();
                let length = ::std::io::stdin().read_line(&mut s).unwrap();
                if length == 0 {
                    break;
                }
                self.buf.extend(s.split_whitespace().map(|s| s.to_owned()));
            }
        }

        pub fn string(&mut self) -> String {
            self.load();
            self.buf
                .pop_front()
                .unwrap_or_else(|| panic!("入力が終了したのですが。"))
        }

        pub fn char(&mut self) -> char {
            let string = self.string();
            let mut chars = string.chars();
            let res = chars.next().unwrap();
            assert!(
                chars.next().is_none(),
                "char で受け取りたいのも山々なのですが、さては 2 文字以上ありますね？"
            );
            res
        }

        pub fn read<T: ::std::str::FromStr>(&mut self) -> T
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            self.string()
                .parse::<T>()
                .expect("Failed to parse the input.")
        }

        pub fn read_vec<T: ::std::str::FromStr>(&mut self, len: usize) -> Vec<T>
        where
            <T as ::std::str::FromStr>::Err: ::std::fmt::Debug,
        {
            (0..len).map(|_| self.read::<T>()).collect()
        }
    }

    macro_rules! define_primitive_reader {
        ($($ty:tt,)*) => {
            impl Buffer {
                $(
#[inline]
                    pub fn $ty(&mut self) -> $ty {
                        self.read::<$ty>()
                    }
                )*
            }
        }
    }

    define_primitive_reader! {
        u8, u16, u32, u64, usize,
        i8, i16, i32, i64, isize,
    }

    impl Default for Buffer {
        fn default() -> Self {
            Self::new()
        }
    }
}
// }}}

fn main() {
    let mut buf = ngtio::Buffer::new();
    let d = buf.u32();
    let t = buf.u32();
    let s = buf.u32();
    if d <= t * s {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2112
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for elem in a:
        counta += 1 if elem[i] == '1' else 0
        check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)


Measured memory_bytes: 18344
N, D = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(N)]
c = 0
for i in range(N - 1):
  for j in range(i+1, N):
    c += (sum((a-b)**2 for a,b in zip(x[i], x[j])) ** 0.5).is_integer()
print(c)

Measured memory_bytes: 3188
a = int(input())
b = int(input())
if a == 1:
    if b == 2:
        print("3")
    else:
        print("2")
if a == 2:
    if b == 1:
        print("3")
    else:
        print("1")
if a == 3:
    if b == 2:
        print("1")
    else:
        print("2")

Measured memory_bytes: 3060
# coding: utf-8
# Your code here!
n = int(input())
tasks = []
for _ in range(n):
    a,b = map(int,input().split())
    tasks.append((b,a))
tasks.sort()

now = 0
for (b,a) in tasks:
    now += a
    if b<now:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 29444
N, M, Q = map(int, input().split())

def dfs(n,i,s,A):
    if n == N:
        A.append(s)
        return

    for j in range(i,M+1):
        tmp = s + [j]
        dfs(n+1,j,tmp,A)

def main():
    a = [0] * Q
    b = [0] * Q
    c = [0] * Q
    d = [0] * Q
    for i in range(Q):
        a[i],b[i],c[i],d[i] = map(int, input().split())
        a[i] -= 1
        b[i] -= 1
    
    A = []
    ans = 0
    dfs(0,1,[],A)
    for B in A:
        tmp = 0
        for j in range(Q):
            if B[b[j]] - B[a[j]] == c[j]:
               tmp += d[j]

        ans = max(ans, tmp)

    print(ans) 



if __name__ == "__main__":
    main()

Measured memory_bytes: 94360
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

vector<set<int>> g;
vector<pair<int, int>> vertexes;
vector<char> used;
int n, m;

int answer = 0;
int cnt;

void dfs(int root) {
	used[root] = true;
	++cnt;
	for (auto to : g[root]) {
		if (!used[to])
			dfs(to);
	}
}

int get_ans() {
	used.assign(n, false);
	cnt = 0;
	dfs(0);
	if (cnt == n)
		return 0;
	else
		return 1;
}

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

	cin >> n >> m;

	g.resize(n);
	vertexes.resize(m);

	for (int i = 0; i < m; ++i) {
		cin >> vertexes[i].first >> vertexes[i].second;
		--vertexes[i].first; --vertexes[i].second;
		g[vertexes[i].first].insert(vertexes[i].second);
		g[vertexes[i].second].insert(vertexes[i].first);
	}

	for (int i = 0; i < m; ++i) {
		int l = vertexes[i].first;
		int r = vertexes[i].second;
		g[l].erase(r);
		g[r].erase(l);
		answer += get_ans();
		g[l].insert(r);
		g[r].insert(l);
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N, i = ni()
    val ans = N - i + 1
    out.println(ans)
  }

  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
  def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
    val A1, A2 = Array.ofDim[Int](n)
    rep(n) { i =>
      A1(i) = ni() + offset
      A2(i) = ni() + offset
    }
    (A1, A2)
  }
  def nm(n: Int, m: Int): Array[Array[Int]] = {
    val A = Array.ofDim[Int](n, m)
    rep(n) { i =>
      rep(m) { j =>
        A(i)(j) = ni()
      }
    }
    A
  }
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def rep(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def rep_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i + offset))
    res
  }


  def sumL(as: Array[Int]): Long = {
    var s = 0L
    rep(as.length)(i => s += as(i))
    s
  }

  def cumSum(as: Array[Int]) = {
    val cum = Array.ofDim[Int](as.length + 1)
    rep(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }
}

Measured memory_bytes: 25288
import numpy as np
import sys

N, M = [int(item) for item in input().split()]

ab = np.zeros((2,N))
for i in range(N):
  ab[0, i], ab[1, i] = [int(item) for item in input().split()]
  
ab = ab[:,np.argsort(ab[0, :])]

num = 0
money = 0
for i, item in enumerate(ab[1,:]):
  num += item
  money += item * ab[0,i]
  if num >= M:
    money -= (num - M) * ab[0,i]
    print(int(money))
    break

Measured memory_bytes: 16372
s = input()
kisu = []
gusu = []
check = 1
judge = True
for i in s:
    if check == 1:
        kisu.append(i)
        check = 0
    else:
        gusu.append(i)
        check = 1
if kisu.count("L") >= 1:
    judge = False
if gusu.count("R") >= 1:
    judge = False

if judge == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
let (n1, n2) = (4, 16)
let n_limit = 100
let mdt = Array.make_matrix n2 n2 0
let path = Array.make n_limit 0
let dx = [| 0; -1; 0; 1 |]
let dy = [| 1; 0; -1; 0 |]

type puzzle = { tbl : int array; space : int; md : int }

let dfs puzzle limit =
  let rec doit depth prev pzl =
    if pzl.md = 0 then true
    else if depth + pzl.md > limit then false
    else begin
      let (sx, sy) = (pzl.space / n1, pzl.space mod n1) in
      let { tbl; md } = pzl in
      let swap tbl i j = let t = tbl.(i) in tbl.(i) <- tbl.(j); tbl.(j) <- t in
      let rec move r =
        if r = 4 then false
        else
          let (tx, ty) = (sx + dx.(r), sy + dy.(r)) in
          if tx < 0 || ty < 0 || tx >= n1 || ty >= n1 then move (r + 1)
          else if max prev r - min prev r = 2 then move (r + 1)
          else begin
            let (space, num) = (tx * n1 + ty, sx * n1 + sy) in
            let md = md - mdt.(space).(tbl.(space) - 1) in
            let md = md + mdt.(num).(tbl.(space) - 1) in
            let tbl = Array.copy tbl in
            swap tbl space num;
            if doit (depth + 1) r { tbl; space; md } then begin
              path.(depth) <- r;
              true
            end else move (r + 1)
          end in
      move 0
    end in
  doit 0 (-n_limit) puzzle

let idastar tbl space =
  let (_, md) =
    Array.fold_left (fun (i, sum) e ->
      (i + 1, if e = n2 then sum else sum + mdt.(i).(e-1)))
      (0, 0) tbl in
  let pzl = { tbl; space; md } in
  let rec doit limit =
    if limit > n_limit then assert false
    else if dfs pzl limit then limit
    else doit (limit + 1) in
  doit pzl.md

let () =
  for i = 0 to n2 - 1 do
    for j = 0 to n2 - 1 do
      mdt.(i).(j) <- abs (i / n1 - j / n1) + abs (i mod n1 - j mod n1)
    done
  done;
  let tbl = Array.make n2 0 in
  let rec doit i space =
    if i = n2 then space
    else begin
      let x = Scanf.scanf "%d " (fun i -> i) in
      let (x, space) = if x = 0 then (n2, i) else (x, space) in
      tbl.(i) <- x;
      doit (i + 1) space
    end in
  doit 0 0 |> idastar tbl |> Printf.printf "%d\n"

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

#define MAXN 110
#define MAXC 100100

long long v[MAXN], w[MAXN], dp[MAXC][MAXN];
//The dimensions of the dp are dp[Weight carrying rn][Last item selected] It'll be in a way that we can only put items that come after the last one selected
//And the value of the dp will be the value that the knapsack is carrying

int main(){
    int n, c;
    long long ans = 0;
    cin >> n >> c;
    for(int i = 1; i <= n; i++){
        cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= c; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] = -1;
        }
    }
    for(int i = 1; i <= n; i++){
        dp[w[i]][i] = v[i];
    }
    for(int i = 1; i <= c; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j] == -1) continue;
            ans = max(ans, dp[i][j]);
            for(int k = j+1; k <= n; k++){
                if(i + w[k] > c) continue;
                dp[w[k]+i][k] = max(dp[w[k]+i][k], dp[i][j] + v[k]);
            }
        }
    }
    cout << ans << endl;
}

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

#define NIL NULL

struct node {
  int key;
  struct node *left;
  struct node *right;
  struct node *parent;
};
struct node *root;

void inorder(struct node *);
void preorder(struct node *);
void insert(int);
struct node *find(int);
void delete(struct node *);
struct node *minimum(struct node *);
struct node *successor(struct node *);


int main()
{
  int i, x, n, key;
  char s[10];

  scanf("%d", &n);
  for(i=0; i<n; i++) {
    scanf("%s", s);
    if(strcmp("insert", s) == 0) {
      scanf("%d", &x);
      insert(x);
    }
    else if(strcmp("print", s) == 0) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(strcmp("find", s) == 0) {
      scanf("%d", &key);
      if(find(key) != NIL)
	printf("yes\n");
      else
	printf("no\n");
    }
    else if(strcmp("delete", s) == 0) {
      scanf("%d", &key);
      delete(find(key));
    }
  }
  return 0;
}

void inorder(struct node *T)
{
  if(T != NIL) {
    if(T->left != NIL)
      inorder(T->left);
    printf(" %d", T->key);
    if(T->right != NIL)
      inorder(T->right);
  }
}

void preorder(struct node *T)
{
  printf(" %d", T->key);
  if(T != NIL) {
    if(T->left != NIL)
      preorder(T->left);
    if(T->right != NIL)
      preorder(T->right);
  }
}

void insert(int key)
{
  struct node *y = NIL;
  struct node *x = root;
  struct node *z;

  z = (struct node *)malloc(sizeof(struct node));
  z->key = key;
  z->left = NIL;
  z->right = NIL;

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

struct node *find(int key)
{
  struct node *x = root;
  while(x != NIL && key != x->key) {
    if(key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  return x;
}

struct node *minimum(struct node *x)
{
  while(x->left != NIL)
    x = x->left;
  return x;
}

struct node *successor(struct node *x)
{
  if(x->right != NIL)
    return minimum(x->right);
  struct node *y = x->parent;
  while(y != NIL && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

void delete(struct node *z)
{
  struct node *y;
  struct node *x;

  if(z->left == NIL || z->right == NIL)
    y = z;
  else
    y = successor(z);
  if(y->left != NIL)
    x = y->left;
  else
    x = y->right;

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

  free(y);
}

Measured memory_bytes: 19364
#include <bits/stdc++.h>
using namespace std;
//
const int maxn = 1e5, mod = 1e9 + 7;
int n, m, a[maxn + 3], b[maxn + 3], N, M, L[maxn + 3], R[maxn + 3], o[maxn + 3], t[maxn + 3], bit[maxn + 3];

bool comp(int i, int j) {
	return L[i] == L[j] ? R[i] > R[j] : L[i] < L[j];
}

inline int func(int x) {
	return x < mod ? x : x - mod;
}

void add(int x, int y) {
	for (int i = x; i <= maxn; i += i & -i) {
		bit[i] = func(bit[i] + y);
	}
}

int query(int x) {
	int y = 0;
	for (int i = x; i; i ^= i & -i) {
		y = func(y + bit[i]);
	}
	return y;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; i++) {
		int l = lower_bound(b + 1, b + m + 1, a[i]) - (b + 1), r = l + 1;
		if (l == 0 || r == m + 1) continue;
		++N, L[N] = a[i] - b[l], R[N] = b[r] - a[i];
	}
	for (int i = 1; i <= N; i++) {
		o[i] = i;
	}
	sort(o + 1, o + N + 1, comp);
	for (int i = 1; i <= N; i++) {
		t[i] = L[i];
	}
	for (int i = 1; i <= N; i++) {
		L[i] = t[o[i]];
	}
	for (int i = 1; i <= N; i++) {
		t[i] = R[i];
	}
	for (int i = 1; i <= N; i++) {
		R[i] = t[o[i]];
	}
	for (int i = 1; i <= N; i++) {
		t[i] = L[i];
	}
	sort(t + 1, t + N + 1);
	M = unique(t + 1, t + N + 1) - (t + 1);
	for (int i = 1; i <= N; i++) {
		L[i] = lower_bound(t + 1, t + M + 1, L[i]) - t;
	}
	for (int i = 1; i <= N; i++) {
		t[i] = R[i];
	}
	sort(t + 1, t + N + 1);
	M = unique(t + 1, t + N + 1) - (t + 1);
	for (int i = 1; i <= N; i++) {
		R[i] = lower_bound(t + 1, t + M + 1, R[i]) - t;
	}
	int ans = 1;
	for (int i = 1; i <= N; i++) {
		if (L[i] == L[i - 1] && R[i] == R[i - 1]) continue;
		int x = query(R[i] - 1) + 1;
		ans = func(ans + x);
		add(R[i], x);
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;


#define ss second
#define ff first
#define int long long
//#define double long double
#define pb push_back

const int N = 1e6 + 1, MOD = 1e9 + 7, mod = 998244353, INF = 3e18;

mt19937 Flash_new_51(51515);

using vi = vector <int>;
using vp = vector <pair <int, int>>;

int a[N], b[N];

signed main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);
   int n;
   cin >> n;
   vi a(n);
   for (int i = 0; i < n; i++) cin >> a[i];
   int kol = 0;
   for (int i = 0; i < n; i++) {
      if (a[i] % 2) kol++;
   }
   if (kol % 2 == 0)
      cout << "YES";
   else cout << "NO";

}

Measured memory_bytes: 1024
sx, sy, tx, ty = map(int, input().split())
dx = tx - sx
dy = ty - sy

res = ""
for i in range(dy): res += "U"
for i in range(dx): res += "R"
for i in range(dy): res += "D"
for i in range(dx): res += "L"

res += "L"
for i in range(dy+1): res += "U"
for i in range(dx+1): res += "R"
res += "D"
res += "R"
for i in range(dy+1): res += "D"
for i in range(dx+1): res += "L"
res += "U"

print(res)


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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        long[] data = new long[N];
        for(int i = 0; i < N; i++) {
            data[i] = scan.nextLong();
        }
        long[] sum = new long[N];
        sum[0] = data[0];
        for(int i = 1; i < N; i++) {
            sum[i] = sum[i-1] + data[i];
        }
        Arrays.sort(sum);
        long answer = 0;
        long len = 0;
        for(int i = 0; i < N; i++) {
            if (i == 0) {
                if (sum[0] == 0) {
                    len += 1;
                    answer += len;
                }
                continue;
            }
            if (sum[i] != sum[i-1]) {
                len = 0;
            }
            if (sum[i] == 0) {
                len += 1;
                answer += len;
                continue;
            }
            if (sum[i] == sum[i-1]) {
                len += 1;
                answer += len;
                continue;
            }
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 83676