akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=3e5+10,mod=1e9+7;
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
typedef long long ll;
int n;
ll a[maxn],num[70],ans;

ll qpow(ll a,ll b)
{
    if(b==0) return 1;
    ll tmp=qpow(a,b/2);
    ll ans=tmp*tmp%mod;
    if(b&1)
        ans=ans*a%mod;
    return ans;
}

int main()
{
    #ifdef __LOCAL__
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    cin>>n;
    _rep(i,1,n) cin>>a[i];
    _rep(i,0,60)
    {
        ll tmp=0;
        for(int j=1;j<=n;j++)
            if(a[j]>>i&1)
                tmp++;
        num[i]=tmp*(n-tmp)%mod;
        ans=(ans+num[i]*qpow(2,i)%mod)%mod;
    }
    cout<<ans<<endl;

    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };

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

	int n;
	cin >> n;

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

	vector<ll> s = x;
	sort(begin(s), end(s));

	for (int i = 0; i < n; i++) {
		int idx = distance(begin(s), lower_bound(begin(s), end(s), x[i]));
		cout << (idx < n / 2 ? s[n / 2] : s[n / 2 - 1]) << endl;
	}

	return 0;
}


Measured memory_bytes: 5376
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
int H[100000] ;
vector<vector<int>>g(100000);
bool vis[100000] ;
void dfs(int ver){
	for(int node : g[ver]){
		if(!vis[node]){
			if(H[node]>H[ver]){
				continue;
			}
			else if(H[node] == H[ver]){
				vis[ver] = true;
				vis[node] = true;
				dfs(node);
			}
			else{
				vis[node] = true ;
				dfs(node) ;
			}
		}
	}
}
void solve()
{
	int n  , m; 
	cin>>n>>m ;
	rep(i , n){
		cin>>H[i] ;
	}
	rep(i , m){
		int a , b;
		cin>>a>>b;
		a--; b--;
		g[a].pb(b) ;
		g[b].pb(a) ;
	}
	
	int ans = 0 ; 
	memset(vis , false ,sizeof(vis));
	rep(i , n){
		if(!vis[i]){
			dfs(i) ; 
		}
	}
	rep(i , n){
		if(!vis[i]){
			ans++;
		}
	}
	cout<<ans;
}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 8636
def gnum(str):
  return ord(str) - 97

S = input()
T = input()

R = [-1] * 26
RR = [-1] * 26

c = 0

for i in range(len(S)):
  if R[gnum(S[i])] < 0:
    R[gnum(S[i])] = gnum(T[i])
  else:
    if R[gnum(S[i])] != gnum(T[i]):
      c = 1

  if RR[gnum(T[i])] < 0:
    RR[gnum(T[i])] = gnum(S[i])
  else:
    if RR[gnum(T[i])] != gnum(S[i]):
      c = 1

if c == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

int main(){
	ll a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	printf("%lld",b/c-(a-1)/c);
}

Measured memory_bytes: 1732
N=int(input())
A=list(map(int,input().split()))
r=0
from collections import defaultdict
d=defaultdict(int)
d[A[0]]=1
for i in range(1,N):
    d2=defaultdict(int)
    for a in d.keys():
        if a&A[i]==0:
            r+=d[a]
            d2[a+A[i]]+=d[a]
    d2[A[i]]+=1
    d=d2
print(r+N)

Measured memory_bytes: 77900
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#define N 511111
#define A 511111
#define BLOCK 714 // ~sqrt(N)
int cnt[A], a[N], ans[N], answer = 0;

struct node {
	int L, R, i;
}q[N];

bool cmp(node x, node y) {
	if(x.L/BLOCK != y.L/BLOCK) {
		// different blocks, so sort by block.
		return x.L/BLOCK < y.L/BLOCK;
	}
	// same block, so sort by R value
	return x.R < y.R;
}

void add(int position) {
	cnt[a[position]]++;
	if(cnt[a[position]] == 1) {
		answer++;
	}
}

void remove(int position) {
	cnt[a[position]]--;
	if(cnt[a[position]] == 0) {
		answer--;
	}
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(NULL);	
	ll n,m;cin>>n>>m;
	for(int i=0; i<n; i++)
		cin>>a[i];

	for(int i=0; i<m; i++) {
		cin>>q[i].L>>q[i].R;
		q[i].L--; q[i].R--;
		q[i].i = i;
	}

	sort(q, q + m, cmp);

	int currentL = 0, currentR = 0;
	for(int i=0; i<m; i++) {
		int L = q[i].L, R = q[i].R;
		while(currentL < L) {
			remove(currentL);
			currentL++;
		}
		while(currentL > L) {
			add(currentL-1);
			currentL--;
		}
		while(currentR <= R) {
			add(currentR);
			currentR++;
		}
		while(currentR > R+1) {
			remove(currentR-1);
			currentR--;
		}
		ans[q[i].i] = answer;
	}

	for(int i=0; i<m; i++)
		printf("%d\n", ans[i]);
}

Measured memory_bytes: 15532
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a>b:
        return b
    else:
        return a
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b
 
 
def gcdl(A):
    if len(A)==2:
        return gcd(A[0],A[1])
    elif len(A)==1:
        return A[0]
    else:
        return gcd(gcdl(A[:len(A)//2]),gcdl(A[len(A)//2:]))


def sieve_of_eratosthenes(n):
    p = 2
    D = [0]*(n+1)
    while p**2<=n:
        if D[p]==0:
            k = p*p
            while k <= n:
                if D[k] == 0:
                    D[k] = p
                k += p
        p+=1
    return D

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    D = sieve_of_eratosthenes(1000000)
    #print(D)
    N = int(input())
    A = list(map(int,input().split()))

    F = set([])
    flag = True
    for a in A:
        b = a
        fact = set([])
        while D[b]>0:
            fact.add(D[b])
            b//=D[b]
        if b!=1:
            fact.add(b)
        for p in fact:
            if p in F:
                flag=False
                break
            else:
                F.add(p)

    if flag:
        print("pairwise coprime")
    else:
        if gcdl(A)==1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == '__main__':
    main()



Measured memory_bytes: 201648
#define _CRT_SECURE_NO_WARNIGNS
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cstring>
using namespace std;
#define sci(n) scanf(“%lld”, &(n))
#define scd(n) scanf(“%Ld”, &(n))
typedef long long LL;

int main(void)
{
	//x meter = Temparature>> T-x * 0.006
	LL n, t;
	double a;
	vector<double> v;
	cin >> n >> t >> a;
	for (int i = 0; i < n; i++) {
		double h; cin >> h;

		h = abs(a - (t - (h*0.006)));
		v.push_back(h);
	}
	double mx = 1e9;
	int mx_idx = -1;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] < mx) {
			mx = v[i];
			mx_idx = i;
		}
	}
	cout << mx_idx + 1;
}

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

int main(void) {
    int N;
    cin >> N;
    int res = N;
    for(int i=0; i<=N; i++) {
        int cc = 0;
        int t = i;
        while(t>0) cc+=t%6, t/=6;
        t = N - i;
        while(t>0) cc+=t%9, t/=9;
        if(res>cc) res = cc;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,a,n) for(int (i)=(n)-1; (i)>=(a);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000000;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};
template<class T> T pow(T a, T b) {
    if (b == 0)return 1;
    if (b % 2) {
        T ret = pow(a, (b - 1) / 2);
        return ((ret * ret) % mod * a) % mod;
    }
    else {
        T ret = pow(a, b / 2);
        return (ret * ret) % mod;
    }
}
int main() {
	init();

    ll n, a, b;
    cin >> n >> a >> b;
    mint ans = pow(2LL, n) - 1;
    vector<ll>N(max(a, b));
    N[0] = n;
    REP(i, 1, max(a, b)) {
        N[i] = (N[i - 1] * (n - i)) % mod;
    }
    vector<ll>ab(max(a, b) + 1);
    ab[0] = 1;
    REP(i, 1, ab.size()) {
        ab[i] = (ab[i - 1] * i) % mod;
    }
    ll nCa = N[a - 1] * pow(ab[a], mod - 2);
    ll nCb = N[b - 1] * pow(ab[b], mod - 2);
    ans -= nCa;
    ans -= nCb;
    cout << ans.x << "\n";



	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const ll mod=1e9+7;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s1,s2;
    cin>>s1>>s2;
    int a,b;
    cin>>a>>b;
    string s;
    cin>>s;
    if(s==s1){
        cout<<a-1<<" "<<b<<endl;
    }
    else cout<<a<<" "<<b-1<<endl;
    return 0;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    int n; cin >> n;
    vi a(n); for(auto& e : a) cin >> e;

    int res = 0;
    rep(i, 1, n-1){
        vi b = {a[i-1], a[i], a[i+1]};
        sort(_all(b));
        if(b[1] == a[i]){
            res++;
        }
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=55;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n;
db a[10005];
db ans;
int main()
{
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	sort(a+1, a+n+1);
	for(int i=2;i<=n;i++){
		a[i]=(a[i]+a[i-1])/2.0;
	}
	printf("%.8Lf\n",a[n]);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

const int MAXN = 1001010;

long long fac[MAXN], finv[MAXN], inv[MAXN];

// 前処理 O(n)
void math_init(){
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(long long i = 2; i < MAXN; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算 O(1)
long long COM(long long n, long long k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


// before your coding, you have to write a line "math_init()"
int main() {
  
  lint n, k; cin >> n >> k;
  math_init();

  if (n - 1 <= k) {
    cout << COM(n + n - 1, n) << endl;
    return 0;
  }
  
  lint ans = 0;
  for(lint i = 0; i <= k; i++) {
    lint rest = n - i;
    ans += COM(i + rest - 1, rest - 1) * COM(n, i) % MOD;
    ans %= MOD;
  }

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


Measured memory_bytes: 23680
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        /*
        System.out.println(ruijou(33));
        System.exit(0);

        */
        Scanner scanner = new Scanner(System.in);
        long x=scanner.nextLong();
        long y=scanner.nextLong();
        long z=y/x;
        System.out.println(ruijou(z)+1);
    }
    public static long ruijou(long n){
        if(n<2){
            return 0;
        }else{
            return ruijou(n/2)+1;
        }
    }
}


Measured memory_bytes: 21972
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	// Scanner sc=new Scanner(System.in);
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	int INF=1<<28;
	double EPS=1e-12;

	int n;
	String[] ss;

	void run(){
		try{
			for(;;){
				n=Integer.parseInt(br.readLine());
				if(n==0){
					break;
				}
				ss=new String[n];
				for(int i=0; i<n; i++){
					ss[i]=br.readLine();
				}
				solve();
			}
		}catch(Exception e){}
	}

	void solve(){
		ArrayList<Mem> list=new ArrayList<Mem>();
		boolean[] removed=new boolean[10010];
		int[] ids=new int[10010];
		HashMap<Integer, Integer> rev=new HashMap<Integer, Integer>();

		list.add(new Mem(0, (int)1e9+10));
		removed[0]=true;
		ids[0]=-1;
		rev.put(-1, 0);

		StringBuilder sb=new StringBuilder();
		for(String s : ss){
			String[] ss=s.split(" ");
			if(ss[0].equals("W")){
				int id=Integer.parseInt(ss[1]), len=Integer.parseInt(ss[2]);
				ids[rev.size()+1]=id;
				rev.put(id, rev.size()+1);
				id=rev.get(id);
				for(int i=0, size=list.size(); i<size; i++){
					Mem m=list.get(i);
					if(removed[m.id]){
						if(len>=m.len){
							m.id=id;
							len-=m.len;
						}else if(len<m.len){
							int right=m.len-len;
							m.id=id;
							m.len=len;
							list.add(i+1, new Mem(0, right));
							len=0;
						}
					}
					if(len==0){
						break;
					}
				}
			}else if(ss[0].equals("D")){
				int id=Integer.parseInt(ss[1]);
				id=rev.get(id);
				removed[id]=true;
			}else{
				int at=Integer.parseInt(ss[1]);
				int tot=0;
				for(int i=0, size=list.size(); i<size; i++){
					Mem m=list.get(i);
					if(tot+m.len>at){
						int id=m.id;
						sb.append(removed[id]?-1:ids[id]).append('\n');
						// sb.append(ids[id]).append('\n');
						break;
					}
					tot+=m.len;
				}
			}
			// debug();
			// for(Mem sec : list){
			// debug(sec.id, sec.len);
			// }
			// debug();
		}
		println(sb.toString());
	}

	class Mem{
		int id, len;

		Mem(int id, int len){
			this.id=id;
			this.len=len;
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 60120
#include <stdio.h>

int main(void){
	int n, m, i, j, d[10000], p[10000], max_i, tmp1, tmp2, sum;
	while(1){
		scanf("%d%d",&n,&m);
		if(n == 0 && m == 0)
			break;
		for(i = 0;i < n;i++)
			scanf("%d%d",&d[i],&p[i]);
		for(i = 0;i < n - 1;i++){
			max_i = i;
			for(j = i + 1;j < n;j++){
				if(p[max_i] < p[j])
					max_i = j;
			}
			if(i != max_i){
				tmp1 = d[max_i];
				tmp2 = p[max_i];
				d[max_i] = d[i];
				p[max_i] = p[i];
				d[i] = tmp1;
				p[i] = tmp2;
			}
		}
		for(i = 0;i < n;i++){
			m -= d[i];
			if(m < 0)
				break;
		}
		sum = 0;
		if(i != n){
			sum += -m * p[i];
			while(++i < n)
				sum += d[i] * p[i];
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 1104
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
//#define ivorysi
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
#define RG register
#define MAXN 200005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar('-');x = -x;}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int N,M,K;
struct node {
    int to,next;
}E[1005];
int head[55],sumE,fac[205],invfac[205],dfn[55],low[55],idx,sta[105],top,col[55],cnt,ans;
vector<int> ver;
int mul(int a,int b) {return 1LL * a * b % MOD;}
int inc(int a,int b) {a = a + b;if(a >= MOD) a -= MOD;return a;}
int fpow(int x,int c) {
    int res = 1,t = x;
    while(c) {
	if(c & 1) res = mul(res,t);
	t = mul(t,t);
	c >>= 1;
    }
    return res;
}
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a % b);
}
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
int C(int n,int m) {
    if(n < m) return 0;
    return mul(mul(fac[n],invfac[m]),invfac[n - m]);
}
void Tarjan(int u,int fa) {
    dfn[u] = low[u] = ++idx;
    sta[++top] = u;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa) {
	    if(dfn[v]) low[u] = min(low[u],dfn[v]);
	    else {
		Tarjan(v,u);
		if(low[v] >= dfn[u]) {
		    ver.clear();
		    ++cnt;
		    col[u] = cnt;
		    ver.pb(u);
		    while(1) {
			int x = sta[top--];
			col[x] = cnt;
			ver.pb(x);
			if(x == v) break;
		    }
		    int tot = 0;
		    for(auto k : ver) {
			for(int j = head[k] ; j ; j = E[j].next) {
			    if(col[E[j].to] == cnt) ++tot;
			}
		    }
		    tot /= 2;
		    if(tot == 1) ans = mul(ans,K);
		    else if(tot == ver.size()) {
			int t = 0;
			for(int j = 1 ; j <= tot ; ++j) {
			    t = inc(t,fpow(K,gcd(tot,j)));
			}
			t = mul(t,fpow(tot,MOD - 2));
			ans = mul(ans,t);
		    }
		    else ans = mul(ans,C(tot + K - 1,K - 1));
		}
		else low[u] = min(low[v],low[u]);
	    }
	}
    }
}
void Solve() {
    read(N);read(M);read(K);
    int u,v;
    for(int i = 1 ;i <= M ; ++i) {
	read(u);read(v);add(u,v);add(v,u);
    }
    fac[0] = 1;
    for(int i = 1 ; i <= 200; ++i) fac[i] = mul(fac[i - 1],i);
    invfac[200] = fpow(fac[200],MOD - 2);
    for(int i = 199 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
    ans = 1;
    for(int i = 1 ; i <= N ; ++i) {
	if(!dfn[i]) Tarjan(i,0);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>	
#define pb push_back
#define mp make_pair
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
typedef long long ll;

const int inf = int(2e9);
const int mod = inf + 7;
using namespace std;

void solve()
{
	int n;
	cin >> n;
	int a[n];
	int pref[n], suff[n];
	rep(i, n) cin >> a[i];
	pref[0] = a[0];
	suff[n - 1] = a[n - 1];
	for(int i = 1; i < n; ++i){
		pref[i] = max(pref[i - 1], a[i]);
	}
	int cnt = 1;
	for(int i = n - 1; i >= 1; --i){
		if(a[i] >= pref[i - 1]) cnt++;
	}
		cout << cnt;

}

int main()
{
	Red;
	solve();
	return 0;
}


Measured memory_bytes: 256
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

A, B = map(int,input().split())

ans = A * B

print(ans)

Measured memory_bytes: 72900
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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; }

ll INF = 1001001001001001001ll;
ll n;
vector<ll> as;
vector<vector<ll>> dp;

ll dfs(int l, int r) {
    if (l == r) return dp[l][r] = as[l];
    if (dp[l][r] != -INF) return dp[l][r];

    chmax(dp[l][r], -dfs(l + 1, r) + as[l]);
    chmax(dp[l][r], -dfs(l, r - 1) + as[r]);
    return dp[l][r];
}

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

    cin>>n;
    as = vector<ll>(n);
    rep(i, n) cin>>as[i];

    dp = vector<vector<ll>>(n + 1, vector<ll>(n + 1, -INF));
    cout<<dfs(0, n - 1)<<endl;
}

Measured memory_bytes: 70912
#coding:utf-8
k = int(input())

lis = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, \
       14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

ans = lis[k - 1]

print("{}".format(ans))

Measured memory_bytes: 3060
def main():
  n = int(input())
  hs = tuple(map(int, input().split()))

  a, b = 0, abs(hs[1] - hs[0])

  for i in range(2, n):
    c = hs[i]
    d1 = a + abs(c - hs[i-2])
    d2 = b + abs(c - hs[i-1])
    a, b = b, d1 if d1 <= d2 else d2

  print(b)

if __name__ == "__main__":
  main()

Measured memory_bytes: 14184
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <numeric>
using namespace std;
#define MAX_N 400
#define MAX_S 100010

// input
int r;

int main() {
    cin >> r;

    int ans = 3 * r * r;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
const int MAX = 2e5 + 5;
const ll INF = (ll) 1e18;
ll arr[MAX], pref[MAX];int n;
inline ll range_sum(int left, int right) {return max(0LL, pref[right] - pref[left - 1]);}
int main() {
	scanf("%d", &n);fori(i, 1, n + 1) {scanf("%lld", arr + i);pref[i] = pref[i - 1] + arr[i];}
	ll ans = INF;
	int left = 1, middle = 2, right = 3;
	while(middle <= n - 2) {
		while(left+1<middle){ll a=range_sum(1,left),b=range_sum(left+1,middle);ll c=range_sum(1,left+1),d=range_sum(left+2,middle);if(abs(a-b)>abs(c-d))left++;else break;}
		while(right+1<n){ll a=range_sum(middle+1,right),b=range_sum(right+1,n),c=range_sum(middle+1,right+1),d=range_sum(right+2,n);if(abs(a-b)>abs(c-d))right++;else break;}
		ll minn=min({range_sum(1,left),range_sum(left+1,middle),range_sum(middle+1,right),range_sum(right+1,n)});
		ll maxx=max({range_sum(1,left),range_sum(left+1,middle),range_sum(middle+1,right),range_sum(right+1,n)});
		ans = min(ans, maxx - minn);middle++;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
using namespace std;

int N;
int K;
int Q;
int A[100001];
int ans[100001];

int main() {
  	cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K >> Q;
    for (int i = 0; i < Q; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) ans[i] = K - Q;
    
    for (int i = 0; i < Q; ++i) {
       ans[A[i] - 1] += 1;
    }
    for (int j = 0; j < N; ++j) {
          if (ans[j] > 0) {
             cout << "Yes" << endl;
          } else {
             cout << "No" << endl;
          }
    }
   
}

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

int main() {
    int N; string S; cin >> N >> S;
    vector<int> idx(10, -1);
    vector<vector<int>> sidx(10, vector<int>(10, -1));
    REP(i, 0, N) {
        int num = S[i] - '0';
        REP(j, 0, 10) {
            if (idx[j] == -1) continue;
            if (sidx[j][num] == -1) sidx[j][num] = i;
        }
        if (idx[num] == -1) {
            idx[num] = i;
        }
    }

    set<int> ans;
    REP(i, 0, 10) {
        if (idx[i] == -1) continue;
        REP(j, 0, 10) {
            if (sidx[i][j] == -1) continue;
            REP(k, sidx[i][j] + 1, N) {
                ans.insert(100 * i + 10 * j + (S[k] - '0'));
            }
        } 
    }

    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
    int count[4][3][10];
    int i, j, k;
    for(i = 0; i < 4; i++){
        for(j = 0; j < 3; j++){
            for(k = 0; k < 10; k++){
                count[i][j][k] = 0;
            }
        }
    }
    int n, b, f, r, v;
    scanf("%d", &n);
    for(int x = 0; x < n; x++){
        scanf("%d %d %d %d", &b, &f, &r, &v);
        count[b - 1][f - 1][r - 1] += v;
    }

    for(i = 0; i < 4; i++){
        for(j = 0; j < 3; j++){
            for(k = 0; k < 10; k++){
                printf(" %d", count[i][j][k]);
            }
            printf("\n");
        }
        if(i < 3){
            printf("####################\n");
        }
    }

    return 0;
}


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

int main(){
    int n;
    cin >> n;
    while(n-- > 0){
        int h, w;
        cin >> h >> w;
        int si[26], ei[26], sj[26], ej[26];
        for(int i = 0; i < 26; i++) si[i] = h, sj[i] = w, ei[i] = ej[i] = -1;
        char mat[h][w];
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> mat[i][j];
                if(mat[i][j] == '.')    continue;
                int ind = mat[i][j]-'A';
                si[ind] = min(si[ind], i);
                sj[ind] = min(sj[ind], j);
                ei[ind] = max(ei[ind], i);
                ej[ind] = max(ej[ind], j);
            }
        }
        bool safe = true;
        int dp[26][26] = {};
        for(int x = 0; x < 26; x++){
            if(ei[x] == -1) continue;
            for(int i = si[x]; i <= ei[x]; i++){
                for(int j = sj[x]; j <= ej[x]; j++){
                    if(mat[i][j] == '.'){
                        safe = false;
                        continue;
                    }
                    if(mat[i][j]-'A' == x)  continue;
                    dp[x][mat[i][j]-'A'] = -1;
                }
            }
        }
        for(int k = 0; k < 26; k++){
            for(int i = 0; i < 26; i++){
                for(int j = 0; j < 26; j++){
                    if(dp[i][k] == 0 || dp[k][j] == 0)  continue;
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
                }
            }
        }
        for(int i = 0; i < 26; i++) safe &= (dp[i][i] == 0);
        cout << (safe ? "SAFE" : "SUSPICIOUS") << endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<double> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double ans = 0;
    for(int i=0; i<n-1; i++){
        v[i+1] = (v[i+1]+v[i])/2.0;
    }
    cout << v[n-1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(long long X, long long A){
	if (X<A) cout << "0" << endl; else cout << "10" << endl;
}

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



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

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define mxn 200005
#define f first
#define s second
using namespace std;

int main()
{
    FLASH
    ll a,b;
    cin >> a >> b;
    cout << a * b;
    return 0;
}

Measured memory_bytes: 3620
n = gets.to_i
n.times do
s = gets
t = s.split
x1 = t[0].to_f 
y1 = t[1].to_f 
x2 = t[2].to_f 
y2 = t[3].to_f 
x3 = t[4].to_f 
y3 = t[5].to_f 
x4 = t[6].to_f 
y4 = t[7].to_f 

xx1 = x2 - x1
yy1 = y2 - y1
xx2 = x4 - x3
yy2 = y4 - y3

if xx1 == 0.0 || xx2 == 0.0
 if xx1 == 0.0 && xx2 == 0.0
  puts "YES"
 else
  puts "NO"
 end
 else
  a = yy1 / xx1
  b = yy2 / xx2
  if (a - b).abs < 1e-10
    puts "YES"
  else
    puts "NO"
  end
end

end


Measured memory_bytes: 6852
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    string w;
    cin >>w;
    map<ll,ll>m;
    rep(i,w.size()){
        m[w[i]]++;
    }

    for (const auto& [key, value] : m){
       if(value%2==1){
           cout<<"No"<<endl;
           return 0;
       }
    }
    
    cout << "Yes" << endl;


    return 0;
    

}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
typedef long long ll;

ll solve(ll x){
    if(x %2 == 1){
       if(((x+1)/2)%2 == 0) return 0;
       else return 1;
    }
    else{
        if(((x+2)/2) %2 == 0) return (0^(x+1));
        else return (1^(x+1));
    }
}

int main(void){
    ll a,b;
    cin >> a >> b;
    cout << (solve(a-1)^solve(b)) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX=10000;
static const int INFTY=(1<<20);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n;
vector<pair<int,int> >adj[MAX];

void dijkstra(){
  priority_queue<pair<int,int> > PQ;
  int d[MAX],color[MAX];
  for(int i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }

  d[0]=0;
  PQ.push(make_pair(0,0));
  color[0]=GRAY;

  while(!PQ.empty()){
    pair<int,int>f=PQ.top();
    PQ.pop();
    int u=f.second;
    color[u]=BLACK;

    if(d[u]<f.first*(-1)) continue;

    for(int j=0;j<adj[u].size();j++){
      int v=adj[u][j].first;
      if(color[v]==BLACK) continue;
      if(d[v]>d[u]+adj[u][j].second){
	d[v]=d[u]+adj[u][j].second;
	PQ.push(make_pair(d[v]*(-1),v));
	color[v]=GRAY;
      }
    }
  }

  for(int i=0;i<n;i++){
    cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
  }
}

int main(){
  int k,c,u,v;
  cin>>n;

  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v>>c;
      adj[u].push_back(make_pair(v,c));
    }
  }
  
  dijkstra();

  return 0;
}



Measured memory_bytes: 8108
#include <stdio.h>
 
#define MAX_N 100
 
int main(){
  int N,u,k,v,i,j;
  int G[MAX_N][MAX_N];
  for (i = 0 ; i < MAX_N ; i++) {
    for (j = 0 ; j < MAX_N ; j++) {
      G[i][j] = 0;
    }
  }
  scanf("%d",&N);
  for(i = 0 ; i < N ; i++){
    scanf("%d%d",&u,&k); u--;
    for(j = 0 ; j < k ; j++){
      scanf("%d",&v); v--;
      G[u][v] = 1;
    }
  }
  for(i = 0 ; i < N ; i++){
    for(j = 0 ; j < N ; j++){
      printf("%d%c",G[i][j],(j < N-1 ? ' ' : '\n'));
    }
  }
  return 0;
}



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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 4e5 + 5;

string s;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  cin>>s;
  int n = s.length();
  const ll mod = 1e9+7;
  vector<vector<ll>> dp(n+1, vector<ll>(4, 0));
  dp[n][3]=1;
  
  for (int i=n-1; i>=0; i--) {
    for (int j=3; j>=0; j--) {
      dp[i][j] = dp[i+1][j] * (s[i]=='?' ? 3ll : 1ll);
      if (j<3) {
	if (s[i]=='?' || s[i]=="ABC"[j]) {
	  dp[i][j] += dp[i+1][j+1];
	}
      }
      dp[i][j] %= mod;
    }
  }

  cout<<dp[0][0]<<endl;

  return 0;
}


Measured memory_bytes: 7376
def calc(x1, y1, x2, y2):
    return S[y2-1][x2-1] - S[y1-1][x2-1] - S[y2-1][x1-1] + S[y1-1][x1-1]

INF = 10**18
def dfs(x1, y1, x2, y2):
    key = (x1, y1, x2, y2)
    if key in memo:
        return memo[key]
    val = calc(x1, y1, x2, y2)
    if val < rest:
        memo[key] = (0, -1)
        return (0, -1)
    res = (1, val)
    for i in xrange(x1+1, x2):
        k1, r1 = dfs(x1, y1, i, y2)
        k2, r2 = dfs(i, y1, x2, y2)
        if r1 >= 0 and r2 >= 0:
            res = max(res, (k1+k2, min(r1, r2)))
    for i in xrange(y1+1, y2):
        k1, r1 = dfs(x1, y1, x2, i)
        k2, r2 = dfs(x1, i, x2, y2)
        if r1 >= 0 and r2 >= 0:
            res = max(res, (k1+k2, min(r1, r2)))
    memo[key] = res
    return res

while 1:
    h, w, s = map(int, raw_input().split())
    if h == 0:
        break
    U = [map(int, raw_input().split()) for i in xrange(h)]
    S = [[0]*(w+1) for i in xrange(h+1)]
    su = sum(sum(e) for e in U)
    rest = su-s
    memo = {}
    for i in xrange(h):
        tmp = 0
        for j in xrange(w):
            tmp += U[i][j]
            S[i][j] = S[i-1][j] + tmp
    k, r = dfs(0, 0, w, h)
    print k, r - rest

Measured memory_bytes: 74080
#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 100005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
int ksm(int a, int b, int p){
	int s = 1;
	while(b){
		if(b & 1) s = z * s * a % p;
		a = z * a * a % p;
		b >>= 1;
	}
	return s;
}
LL ans = 1e18, x[N];
int main(){
	int i, j, n, m, k;
	LL v1, v2;
	n = read(); m = read();
	for(i = 1; i <= n; i++) x[i] = read();
	for(i = 1; i <= n - m + 1; i++){
		j = i + m - 1;
		if(x[j] <= 0){
			ans = min(ans, abs(x[i]));
		}
		else if(x[i] >= 0) ans = min(ans, x[j]);
		else{
			v1 = abs(x[i]), v2 = abs(x[j]);
			ans = min(ans, min(v1 * 2 + v2, v2 * 2 + v1));
		}
	}
	printf("%lld", ans);
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
using namespace std;
#define i64  long long
#define lint long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define MOD_Q 1e9 + 7;

void solve()
{
  int N,K;
  cin>>N >> K;
  vector<int> vec(N + 1,0);
  for (int i = 1; i <= N; i++)
  {
    cin>>vec[i];
  }
  
  vector<int> DP (N + 1,I32_MAX);

  DP[1] = 0;

  for (int i = 2 ; i <= N; i++)
  {
    for (int j = 1; j <= K; j++)
    {
      if(i -j <= 0) continue;
      DP[i] = min(abs(vec[i] - vec[i-j])+DP[i - j],DP[i]);
    }
    
  }
  
  // DP[2] = abs(vec[2]-vec[1]);

  // for (int i = 3; i <= N; i++)
  // {
  //   DP[i] = min(abs(vec[i] - vec[i-2]) + DP[i-2],abs(vec[i] - vec[i-1]) + DP[i-1]);
  // }

  // for (int i = 0; i < N+1; i++)
  // {
  //   cout<<DP[i]<<endl;
  // }
  
  
  cout<<DP[N]<<endl;

  return;
}

int main(int argc, const char *argv[])
{

  solve();

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(x) (((long long)x)%modulo)



int main(){
	
	int H,W;
	cin>>H>>W;
	
	int N;
	cin>>N;
	int sx,sy;
	cin>>sy>>sx;
	
	string S,T;
	cin>>S>>T;
	
	int x = sx;
	int y = sy;
	for(int i=0;i<N;i++){
		if(S[i]=='R'){
			x++;
			if(x>W){
				cout<<"NO"<<endl;
				return 0;
			}
		}
		if(T[i]=='L'){
			x=max(x-1,1);
		}
	}
	
	x = sx;
	y = sy;
	for(int i=0;i<N;i++){
		if(S[i]=='L'){
			x--;
			if(x<1){
				cout<<"NO"<<endl;
				return 0;
			}
		}
		if(T[i]=='R'){
			x=min(x+1,W);
		}
	}
	
	x = sx;
	y = sy;
	for(int i=0;i<N;i++){
		if(S[i]=='U'){
			y--;
			if(y<1){
				cout<<"NO"<<endl;
				return 0;
			}
		}
		if(T[i]=='D'){
			y=min(y+1,H);
		}
	}
	
	x = sx;
	y = sy;
	for(int i=0;i<N;i++){
		if(S[i]=='D'){
			y++;
			if(y>H){
				cout<<"NO"<<endl;
				return 0;
			}
		}
		if(T[i]=='U'){
			y=max(y-1,1);
		}
	}
	
	cout<<"YES"<<endl;
	
	
	
	return 0;
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

class UnionFind {
  std::vector<int> p;

public:
  UnionFind(int n) : p(n, -1) {}

  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }

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

  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (p[y] < p[x]) std::swap(x, y);
    if (p[x] == p[y]) --p[x];
    p[y] = x;
    return true;
  }
};

int main()
{
    ll n,m;
    cin>>n>>m;
    UnionFind uf = UnionFind(n);
    for (int i = 0; i < m; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        uf.unite(x,y);
    }
    unordered_set<ll> us;
    for (int i = 0; i < n; i++)
    {
        us.emplace(uf.root(i));
    }
    cout<<us.size()<<endl;    

    return 0;
}

Measured memory_bytes: 4772
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pb 	push_back
#define ll  long long
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define debug(x) cerr<<#x<<" =: "<<x<<endl;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Find find_by_order
#define Order order_of_key
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 mrand(random_device{}());
ll rnd(ll x) { return mrand() % x;}
ll ksm(ll a,ll b,ll mod){ll ans=1;a%=mod;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll phi(ll n){ll ans=n;for(ll i=2;i*i<=n;i++){if(n%i==0) {while(n%i==0) n/=i;ans=ans*(i-1)/i;}}if(n>1) ans=ans*(n-1)/n;return ans;}
//head

const int maxn = 1e6 + 7;
vector<int> vec[maxn];
int a[maxn], ans[maxn];
set<int> s;

int main (){
    int s, w;
    cin >> s >> w;
    if (s <= w) cout << "unsafe\n";
    else cout << "safe\n";
    return 0;
}


Measured memory_bytes: 27012
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    if(Math.abs(c - a) <= d){
      System.out.println("Yes");
    }else if(Math.abs(b - a) <= d && Math.abs(c - b) <= d){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 23892
n,m,k = map(int, input().split( ))
A = list(map(int, input().split( )))
B = list(map(int, input().split( )))
acc1 = [0]
for i in range(n):
  acc1.append(acc1[-1] + A[i])
acc2 = [0]
for i in range(m):
  acc2.append(acc2[-1] + B[i])

ans = 0
j = m
for i in range(n+1):
  if acc1[i] > k:
    break
  while acc2[j] > k - acc1[i] and j > 0:
    j -= 1
  ans = max(ans,i+j)
print(ans)
  

Measured memory_bytes: 47520
/*	
*  Sachin Mittal
*/
#include<bits/stdc++.h>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,j,n) for(int i=j;i<n;i++)
#define F first
#define S second
#define lb lower_bound
#define mem0(dp) memset(dp,0,sizeof(dp))
#define mem1(dp) memset(dp,-1,sizeof(dp))
#define pb push_back
#define sz(s) (int)(s.size())
#define debug(x) cout << #x << " = " << x << '\n';
using namespace std;

void solve()
{
    double r;cin>>r;
    double pi=3.141592;
    double ans=(2*pi*r);
    cout<<fixed<<setprecision(10)<<ans;
}

int32_t main(){

ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
 //again
while(t--)
{
	solve();
}
}


Measured memory_bytes: 3828
<?php
$S=trim(fgets(STDIN));
$Q=trim(fgets(STDIN));
for($I=0;$I<$Q;$I++){
  $C=explode(' ',trim(fgets(STDIN)));

  if($C[0][2]=='i'){
    $p='';
    for($i=$C[1];$i<=$C[2];$i++) $p.=$S[$i];
    echo $p,PHP_EOL;
    continue;
  }
  if($C[0][2]=='v'){
    $l=$C[1]+(($C[2]-$C[1]+1)>>1);
    for($i=$C[1];$i<$l;$i++){
      $j=$C[2]-$i+$C[1];
      $s=$S[$j];
      $S[$j]=$S[$i];
      $S[$i]=$s;
    }
    continue;
  }
  for($i=$C[1];$i<=$C[2];$i++) $S[$i]=$C[3][$i-$C[1]];
}

Measured memory_bytes: 15468
#include <iostream>
#include <string>
#include <cstdlib>

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

	long long n;
	std::cin >> n;

	long long t[2] = {0,0} , x[2] = {0,0} , y[2] = {0,0} ;
	std::cin >> t[0] >> x[0] >> y[0];
  
	for (int i = 1; i <= n; ++i) {
		std::cin >> t[1] >> x[1] >> y[1];

		long long ss = abs(t[1] - t[0]) - abs(y[1] - y[0]) -  abs(x[1] - x[0]);
		if (ss < 0 || ss & 1) {
			std::cout << "No";
			return 0;
		}
		t[0] = t[1];
		x[0] = x[1];
		y[0] = y[1];
	}
	std::cout << "Yes";

	return 0;
}

Measured memory_bytes: 256