akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
const double EPS=1e-6;
typedef vector<double> vec;
typedef vector<vec> mat;

vec gauss_jordan(mat A,vec b){
	int n=A.size()-1;
	mat B(n,vec(n+1));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			B[i][j]=A[i][j];
		}
	}
	for(int i=0;i<n;i++){
		B[i][n]=b[i];
	}
	for(int i=0;i<n;i++){
		int pivot=i;
		for(int j=i;j<n;j++){
			if(abs(B[j][i])>abs(B[pivot][i]))pivot=j;
		}
		swap(B[i],B[pivot]);
		if(abs(B[i][i])<EPS)return vec();
		for(int j=i+1;j<=n;j++){
			B[i][j]/=B[i][i];
		}
		for(int j=0;j<n;j++){
			if(i!=j){
				for(int k=i+1;k<=n;k++){
					B[j][k]-=B[j][i]*B[i][k];
				}
			}
		}
	}
	double res=0;
	for(int j=0;j<n;j++){
		res+=A[n][j]*B[j][n];
	}
	if(abs(res-b[n])>0.1)return vec();
	vec x(n);
	for(int i=0;i<n;i++){
		x[i]=B[i][n];
	}
	return x;
}

int d;
double v[10];

int main(void){
	while(1){
		scanf("%d",&d);
		if(d==0)break;
		for(int i=0;i<d+3;i++){
			scanf("%lf",&v[i]);
		}
		for(int i=0;i<d+3;i++){
			mat A(d+2,vec(d+1));
			vec b(d+2);
			int cnt=0;
			for(int j=0;j<d+3;j++){
				if(i==j)continue;
				for(int k=0;k<=d;k++){
					A[cnt][k]=pow((double)j,k);
				}
				b[cnt]=v[j];
				cnt++;
			}
			if(gauss_jordan(A,b).size()>0){
				printf("%d\n",i);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1104
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
#define f(i,n) for(int i=0;i<n;i++) 
#define fr(i,a,b) for(int i=a;i<b;i++) 
#define mp make_pair 
#define pb push_back 
#define P(i,j) pair<i,j> 
#define M(i,j) map<i,j> 
#define V(i) vector<i> 
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;


bool compare(P(ll,ll) a,P(ll,ll) b){
	if(a.F==b.F)
		return a.S<b.S;
	else return a.F<b.F;
}

void test(){
	ll n;
	cin>>n;
	V(P(ll,ll)) v;
	f(i,n){
		ll a,b;
		cin>>a>>b;
		v.pb(mp(a+b,a-b));
	}
	sort(v.begin(),v.end(),compare);
	ll in=1;
	ll count=1;
	ll end=v[0].F;
	while(in<v.size()){
		if(v[in].S>=end){
			count++;
			end=v[in].F;
		}
		in++;
	}
	cout<<count<<"\n";
}

int main(){
	int t=1 ;
//	cin>>t;
	while(t-->0){
		test();
	}
}

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

int main(){
  int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
  int dy[8] = {1,1,1,0,0,-1,-1,-1};
  int h, w; cin >> h >> w;
  string s[h];
  for(int i = 0; i < h; ++i){
     cin >> s[i];
  }
  int ans[h][w] = {};
  for(int y = 0; y < h; ++y){
    for(int x = 0; x < w; ++x){
      int num = 0;
      for(int j = 0; j < 8; ++j){
        if(s[y][x] == '#') {
          num = -1;
          continue;
        }
        if(y + dy[j] < 0 || y + dy[j] >= h) continue;
        if(x + dx[j] < 0 || x + dx[j] >= w) continue;
        int xx = x + dx[j];
        int yy = y + dy[j];
        if(s[yy][xx] == '#') ++num;
      }
      ans[y][x] = num;
    }
  }
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if(ans[i][j] == -1) cout << '#';
      else cout << ans[i][j];
    }
    cout << '\n';
  }
  return 0; 
}


Measured memory_bytes: 3636
using System;
using System.Linq;
using System.Collections;

class Problem
{
    static void Main()
    {
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        ArrayList al = new ArrayList();
        for(int i=1; i<=Math.Min(a[0],a[1]); i++)
        {
            if(a[0]%i==0 && a[1] % i == 0)
            {
                al.Add(i);
            }
        }
        Console.WriteLine(al[al.Count-a[2]]);
    }
}

Measured memory_bytes: 13396
(println
 (loop [lines (rest (line-seq (clojure.java.io/reader *in*)))
        numbers #{}]
   (if (empty? lines)
     (count numbers)
     (let [n (first lines)]
       (recur (rest lines)
              (if (contains? numbers n)
                (disj numbers n)
                (conj numbers n)))))))


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

int main(){
    int H, N;
    cin >> H >> N;

    vector<int> A(N);
    for(int i = 0; i < N; ++i) cin >> A.at(i);

    bool flag = false;
    int cnt = 0;

    for(int i = 0; i < N; ++i) {
        cnt += A.at(i);
    }

    if(H <= cnt) {
        cout << "Yes" << endl;
        flag = true;
    }

    if(flag == false) {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(i=j;i<k;i++)
#define all(obj) obj.begin(), obj.end()

signed main(){
    long long money=100;
    int cnt=0;
    long long x;
    long long plus;
    cin>>x;
    while(money<x){
        plus=money*0.01;
        money+=plus;
        cnt+=1;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 3596
// Date: 2020-03-21

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define D(x) cout<<#x<<" = "<<x<<endl;
#define SZ(x) ((int)x.size())
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

LL ans;
int a[15], use[15], n;
void dfs(int u) {
    if(u == n) {
        LL tp = 0;
        VI vec;
        vec.pb(0);
        rep(i, 1, n-1) if(use[i]) vec.pb(i);
        vec.pb(n);
        for(int i = 1; i < SZ(vec); ++i) {
            LL val = 0;
            for(int j = vec[i-1] + 1; j <= vec[i]; ++j) {
                val = val * 10 + a[j];
            }
            tp += val;
        }
        ans += tp;
        return;
    }
    use[u] = 1, dfs(u+1);
    use[u] = 0, dfs(u+1);
}

int main() {
    FIO;
    string s;
    cin >> s;
    n = s.size();
    rep(i, 1, n) a[i] = s[i-1]-'0';
    dfs(1);
    cout << ans;

    return 0;
}

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

vector<pair<long long int,long long int> > w[100005];
bool vis[100005];
int color[100005];


void bfs(long long int s)
{
    vis[s]=true;
    queue<long long int>q;
    q.push(s);
    while(!q.empty())
    {
        long long int x=q.front();
        q.pop();
        for(int k=0;k<w[x].size();k++)
        {
            long long int j=w[x][k].first;
            if(vis[j]==false)
            {
                vis[j]=true;
                q.push(j);
               if(w[x][k].second%2==0)
               {
                   color[j]=color[x];
               }
               else{
                color[j]=color[x]^1;
               }
            }
        }

    }
}

main()
{
    long long int n,i,j;
    cin>>n;
    for(i=0;i<n-1;i++)
    {
        long long int x,y,d;
        cin>>x>>y>>d;
         w[x].push_back({y,d});
         w[y].push_back({x,d});
    }

    color[1]=1;
    bfs(1);
    for(i=1;i<=n;i++)
    {
        cout<<color[i]<<endl;
    }
}



Measured memory_bytes: 11508
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {

    int N, K;
    cin >> N >> K;
    int h;
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        cin >> h;
        if (h >= K) {
            cnt += 1;
        }
    }
    cout << cnt << endl;
    return 0;
}


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

int main() {
    int n, a, b; cin >> n >> a >> b;
    if(n == 1) {
        if(a == b)
            cout << "1\n";
        else
            cout << "0\n";
        return 0;
    }

    long long ans = 1LL * (n - 1) * b + a - (1LL * (n - 1) * a + b) + 1;
    cout << max(0LL, ans) << "\n";
}

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

int main() {
	int w,h,n;
	int xs,ys;
	int xg,yg;
	int c,d,x,y;
	int v[101][101];
	int u[101][101];
	int flag=0;
	int xx[4]={-1,0,1,0};
	int yy[4]={0,1,0,-1};
	int xxx,yyy;
while(cin>>w>>h,w||h){
	cin>>xs>>ys;
	cin>>xg>>yg;
	cin>>n;
	fill(v[0],v[101],0);
	fill(u[0],u[101],0);
	for (int i = 0; i < n; ++i) {
			cin>>c>>d>>x>>y;
			if(d==0){
				v[x][y]=c;	v[x+1][y]=c;	v[x+2][y]=c;	v[x+3][y]=c;
				v[x][y+1]=c;	v[x+1][y+1]=c;	v[x+2][y+1]=c;	v[x+3][y+1]=c;
			}
			if(d==1){
				v[x][y]=c;	v[x][y+1]=c;	v[x][y+2]=c;	v[x][y+3]=c;
				v[x+1][y]=c;	v[x+1][y+1]=c;	v[x+1][y+2]=c;	v[x+1][y+3]=c;
			}
	}
	queue<pair<int,int> > q;
	u[xs][ys]=1;
	int color=v[xs][ys];
	q.push(make_pair(xs,ys));
	while(!q.empty()){
		pii=q.front();q.pop();
		if(pii.first==xg&&pii.second==yg){flag=1;break;}
		for (int i = 0; i < 4; ++i) {
			xxx=xx[i]+pii.first;
			yyy=yy[i]+pii.second;
			if(xxx>=1&&xxx<=w&&yyy>=1&&yyy<=h&&u[xxx][yyy]!=1&&color==v[xxx][yyy]){
				u[xxx][yyy]=1;
				q.push(make_pair(xxx,yyy));
			}
		}
	}
	if(flag){cout<<"OK"<<endl;}
	else{cout<<"NG"<<endl;}
	flag=0;
}
	return 0;
}

Measured memory_bytes: 3192
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

struct P {
    bool operator<(const P &p) const {
        return x < p.x;
    }
    int x, x0, x1;
};

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

    int n, q;
    cin >> n >> q;

    vector<P> p(n);
    for (int i = 0; i < n; i++) {
        int s, t, x;
        cin >> s >> t >> x;

        p[i] = { x, x + 1 - t, x + 1 - s };
    }
    sort(p.begin(), p.end());

    vector<int> d(q);
    for (int j = 0; j < q; j++) {
        int e;
        cin >> e;
        d[q - 1 - j] = -e;
        //cout << d[q - 1 - j] << endl;
    }

    set<int> st;
    for (int j = 0; j < q; j++) {
        st.insert(j);
    }
    vector<int> r(q, -1);
    for (int i = 0; i < n; i++) {
        //cout << p[i].x0 << ' ' << p[i].x1 << endl;
        int j0 = (int)(lower_bound(d.begin(), d.end(), p[i].x0) - d.begin());
        int j1 = (int)(lower_bound(d.begin(), d.end(), p[i].x1) - d.begin());
        //cout << j0 << ' ' << j1 << endl;
        auto it = st.lower_bound(j0);
        //for (int j = j0; j < j1; j++) {
        for (; it != st.end();) {
            int j = *it;
            if (j >= j1) break;
            //if (r[j] < 0) {
                r[j] = p[i].x;
                it = st.erase(it);
            //}
        }
    }

    for (int j = 0; j < q; j++) {
        cout << r[q - 1 - j] << '\n';
    }
    cout << flush;

    return 0;
}

Measured memory_bytes: 15232
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] order = new int[N];
		for(int i = 0; i < N; i++){
			order[i] = i;
		}

		double[] X = new double[N];
		double[] Y = new double[N];

		for(int i = 0; i < N; i++){
			X[i] = sc.nextDouble();
			Y[i] = sc.nextDouble();
		}

		double sum = 0;
		int count = 0;
		do{
			
			for(int i = 0; i < N - 1; i++){
				double d = distance(X[order[i]], Y[order[i]], X[order[i + 1]], Y[order[i + 1]]);
				sum += d;
			}
			count++;
		}while(nextPermutation(order));
		System.out.println(sum / count);
	}

	private static boolean nextPermutation(int[] array) {
		for (int i = array.length - 1 ; i > 0 ; i --) {
			if (array[i - 1] < array[i]) {
				int j = find(array, array[i - 1], i, array.length - 1);
				int temp = array[j];
				array[j] = array[i - 1];
				array[i - 1] = temp;
				Arrays.sort(array, i, array.length);
				return true;
			}
		}
		return false;
	}

	private static int find(int[] array, int dest, int f, int l) {
		if (f == l) {
			return f;
		}
		int m = (f + l + 1) / 2;
		return (array[m] <= dest) ? find(array, dest, f, m - 1) : find(array, dest, m, l);
	}
	
	private static double distance(double x1, double y1, double x2, double y2) {
		return(Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
	}
}

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

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

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

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

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

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

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

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

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    String s = sc.next();
    String t = sc.next();
    System.out.println(t.startsWith(s) ? "Yes" : "No");
  }
}

Measured memory_bytes: 25364
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>

using namespace std;
typedef complex<int> P;


bool solve(){
	int n;
	cin>> n;
	if(!n) return false;
	vector<P> vc;
	vc.push_back((0,0));
	
	P dxdy[4]={P(-1,0),P(0,-1),P(1,0),P(0,1)};
	for(int i=1;i<n;i++){
		P in;
		int n, d;
		cin>> n>> d;
		in = vc[n] + dxdy[d];
		vc.push_back(in);
	}
	
	int wmax, wmin, hmax, hmin;
	for(int i=0;i<vc.size();i++){
		if(i==0){
			wmax = vc[i].real();
			wmin = vc[i].real();
			hmax = vc[i].imag();
			hmin = vc[i].imag();
		}else{
			wmax = max(wmax, vc[i].real());
			wmin = min(wmin, vc[i].real());
			hmax = max(hmax, vc[i].imag());
			hmin = min(hmin, vc[i].imag());
		}
	}
	cout<< wmax - wmin + 1 << " "<< hmax - hmin + 1 << endl;
	
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	while(solve());

	return 0;
}

 

Measured memory_bytes: 1204
import java.util.*;
 
public class Main{
      public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            int L = sc.nextInt();
            if((N == M || M == L || N == L) && !(N == M && N == L)){
              System.out.println("Yes");
            } else {
              System.out.println("No");
            }
          }
}

Measured memory_bytes: 23124
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
r,g,b,n=IL()
ans=0
for i in range(0,n+1):
    for j in range(0,n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
            
print(ans)

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

namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = IOUtils.ReadInt();
            var res = r * 2 * Math.PI;
            Console.WriteLine(res);
        }
    }

    static class IOUtils
    {
        public static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }
        public static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }
        public static ulong ReadUlong()
        {
            return ulong.Parse(Console.ReadLine());
        }
        public static int[] ReadInts()
        {
            return Console.ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();
        }
        public static long[] ReadLongs()
        {
            return Console.ReadLine().Split(' ').Select(v => long.Parse(v)).ToArray();
        }

        public static void WriteNums(params int[] nums)
        {
            Console.WriteLine(string.Join(" ", nums));
        }
    }
}


Measured memory_bytes: 18352
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main(){
    int n; cin >> n;
    vector<int> as(n);
    for(int i=0; i<n; ++i){
        cin >> as[i];
    }
    int ans=INT_MAX;
    for(int i=-100; i<=100; ++i){
        int c=0;
        for(int j=0; j<n; ++j){
            c+=(as[j]-i)*(as[j]-i);
        }
        ans=min(ans, c);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
mod = 10**9 + 7


def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    ans = 0
    for k in range(60):
        a = 0
        for i in range(n):
            a += A[i] & 1
            A[i] >>= 1
        da = (1 << k) % mod
        da *= (n - a)*a
        da %= mod
        ans += da
        ans %= mod
    print(ans)


main()


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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<pii, int> para;
const int inf = 1e9 + 7;
const int maxN = 1e6 + 5;

ll a[5];

int main() {
	cin>>a[0]>>a[1]>>a[2];
	sort(a, a + 3);
	if (a[0] % 2 == 0 || a[1] % 2 == 0 || a[2] % 2 == 0)
		cout<<"0";
	else
		cout<<a[0] * a[1];
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

	string ans;
	if (s == "AAA" || s == "BBB") {
		ans = "No";
	} else {
		ans = "Yes";
	}
	cout << ans << endl;

	return 0;
}


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

long long a[10][14];
int k,s=0;

long long find(int k,int hd,int dgt){
//	cout << k << ' ' << hd << ' ' << dgt << ' ' << a[hd][dgt] << endl;
	if (k > a[hd][dgt]){
		int hdd = hd+1,dgtt = dgt;
		if (hdd > 9){
			hdd = 1;
			dgtt ++;		
		}
		return find(k-a[hd][dgt],hdd,dgtt);
	}
	if (dgt == 1) return hd;
	long long ans = hd;
	for (int i=1;i<dgt;i++) ans*=10;
	return (ans + find(k,max(hd-1,0),dgt-1));
}

int main(){
	for (int i=0;i<=9;i++) a[i][1]=1;	
	for (int i=2;i<=11;i++){
		a[0][i]=a[0][i-1]+a[1][i-1];
		a[9][i]=a[9][i-1]+a[8][i-1];
		for (int j=1;j<9;j++){
			a[j][i]=a[j-1][i-1]+a[j][i-1]+a[j+1][i-1];	
		}
	}
	cin >> k;
	cout << find(k,1,1);
	return 0;
}

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

typedef long long ll;

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

int main(){
  ll N, M;
  cin >> N >> M;
  
  cout << N * M / gcd(N, M) << endl;
}

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

prev = None
flag = True
words = []
for i in range(N):
    w = input()
    if i != 0:
        if prev[-1] != w[0] or w in words:
            flag = False

    prev = w
    words.append(w)

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
N = int(input())
for i in range(N):
    s, d = map(int, input().split())
    s += 2**30; d += 2**30
    ans = 0
    while s + (s & -s) <= d:
        s += (s & -s)
        ans += 1
    d -= s
    while d:
        d -= (d & -d)
        ans += 1
    print(ans)



Measured memory_bytes: 5600
a,b,c,x,y = input().split()
A = int(a)
B = int(b)
C = int(c)
X = int(x)
Y = int(y)

min_yen = 0

if(X<Y):
	if(C*2*X < (A*X+B*X)):
		min_yen += C*2*X
		Y -= X

		if(X!=0 and (C*2 < B)):
			min_yen += C*2*Y
		elif(X!=0 and(C*2 >= B)):
			min_yen += B*Y

	else:
		min_yen += A*X

		if(C*2 < B):
			min_yen += C*2*Y
		else:
			min_yen += B*Y


elif(X>=Y):
	if(C*2*Y < (A*Y+B*Y)):
		min_yen += C*2*Y
		X -= Y

		if(X!=0 and (C*2 < A)):
			min_yen += C*2*X
		elif(X!=0 and(C*2 >= A)):
			min_yen += A*X
	else:
		min_yen += B*Y

		if(C*2 < A):
			min_yen += C*2*X

		else:
			min_yen += A*X

print(min_yen)

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;


int main() {
    int n, m, k; cin >> n >> m >> k;

    for(int i = 0; i <= n; i++){
        int sum = i * m;
        for(int j = 0; j <= m; j++){
            int tmp = sum + j * n - 2 * j * i;
            if(tmp == k){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 3680
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

template <typename T>
void print(const vector<T> &v) {
    for (auto e : v) cout << e << ' ';
    cout << endl;
}

//------------------------- Libraries -------------------------//

//--------------------------- Solve ---------------------------//

void solve() {
    int c[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[i][j];
        }
    }

    bool ok = true;
    
    int a1 = c[0][1] - c[0][0], a2 = c[0][2] - c[0][0];
    for (int i = 1; i < 3; i++) {
        if (c[i][1] - c[i][0] != a1) ok = false;
        if (c[i][2] - c[i][0] != a2) ok = false;
    }

    int b1 = c[1][0] - c[0][0], b2 = c[2][0] - c[0][0];
    for (int j = 1; j < 3; j++) {
        if (c[1][j] - c[0][j] != b1) ok = false;
        if (c[2][j] - c[0][j] != b2) ok = false;
    }

    cout << (ok ? "Yes" : "No") << '\n';
}

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

    solve();

    return 0;
}

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

int main() {
  string s;
  cin >>s;
  if(s == "SUN")
    cout << 7 << endl;
  if(s == "MON")
    cout << 6 << endl;
  if(s == "TUE")
    cout << 5 << endl;
  if(s == "WED")
    cout << 4 << endl;
  if(s == "THU")
    cout << 3 << endl;
  if(s == "FRI")
    cout << 2 << endl;
  if(s == "SAT")
    cout << 1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

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

	long long cnt=0;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
		{
			auto low=upper_bound(l.begin(),l.end(),l[j]-l[i]);
			auto up=lower_bound(l.begin(),l.end(),l[j]+l[i])-1;

			int ll=(low-l.begin());
			int uu=(up-l.begin());
			//cerr << i+1 << " " << j+1 << " : " << (low-l.begin())+1 << " " << (up-l.begin())+1 << endl;
			//cerr << max(ll,j+1)+1 << " " << max(uu,j+1)+1 <<  endl;

			// cnt+=(max(uu,j+1)-max(ll,j+1));

			int tmp=((l.begin()+j+1)-low);
			//cerr << "tmp : " << tmp << " uu : " << uu << " " << ll <<  endl;
			cnt += (uu-ll+1)-max(0,tmp);
		}


	cout << cnt << endl;



}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n);i++)
#define rep1(i,n) for(int i=1; i<(n); i++)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> gl(n, 0), gr(n, 0);

    gl[0] = a[0];
    rep1(i, n) gl[i] = __gcd(gl[i-1], a[i]);
    gr[n-1] = a[n-1];
    for(int i=n-2; i>=0; i--) gr[i] = __gcd(gr[i+1], a[i]);
    int ans = gr[1];
    rep1(i, n-1) ans = max(ans, __gcd(gl[i-1], gr[i+1]));
    ans = max(ans, gl[n-2]);
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;

int main()
{
    int N, K;
    cin >> N >> K;
    if (K == 1)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << N - K << endl;
    }
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll   long long
#define ld long double
#define endl '\n'
#define INF 10000000000000000
#define pll pair<ll,ll>
#define ff first
#define ss second

using namespace std;
const ll N = 1115;
const ll MOD = 10e8+7;
    ll dp[N][N];
int main()
{
 //freopen("input.txt","r",stdin);
 //  freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,m;
    cin>>n>>m;

    bool grid[n+6][m+6]={0};
    for(ll i =1;i<=n;i++) {
        for(ll j =1;j<=m;j++) {
            char b;
            cin>>b;
            if(b=='.') grid[i][j]=1;
        }
    }
dp[1][1]=1;
    for(ll i =1;i<=n;i++) {
        for(ll j =1;j<=m;j++) {
       //     cout<<dp[i][j]<<" ";
            if(i==1 &&j==1) continue;
                if(grid[i][j]) dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
        }
     //   cout<<endl;
    }
    cout<<dp[n][m];

}


Measured memory_bytes: 9984
import java.util.*;


public class Main {
	public static void main(String args[])throws Exception{
		Scanner sc = new Scanner(System.in);
		Integer[] mount = new Integer[10];
		int i = 0;
		while(sc.hasNext()){
			mount[i] = sc.nextInt();
			i++;
		}
		sort(mount);
		sc.close();
	}
	public static void sort(Integer[] mlist){
		Arrays.sort(mlist);
		for(int i=9; i >= 7; i--){
			System.out.println(mlist[i]);
		}
	}
	
}

Measured memory_bytes: 25916
import java.util.*;

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

        int n = sc.nextInt();

        int[] l = new int[n];

        for(int i = 0; i < n; i++){
            l[i] = sc.nextInt();
        }

        Arrays.sort(l);
        int ans = 0;

        for(int i = 0; i < n - 2; i++){
            for(int j = i + 1; j < n - 1; j++){
                for(int k = j + 1; k < n; k++){
                    if(l[i] + l[j] > l[k] && l[i] != l[j] && l[j] != l[k] && l[k] != l[i]){
                        ans++;
                    }
                }
            }
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 36432
#include<stdio.h>

int chksame(char *S,char *T,int len){
    for(int i=0;i<len;i++){
        if(S[i]!=T[i]){

            return -1;
        }
    }
    return 1;
}


int main(void){
    char S[100]={};
    char T[100]={};
    scanf("%s",S);
    scanf("%s",T);
    int len=0;
    while(S[len]!='\0'){
        len++;
    }
    for(int i=0;i<len;i++){
        char temp = S[0];
        for(int j=0;j<len-1;j++){
            S[j]=S[j+1];
        }
        S[len-1]=temp;
        if(chksame(S,T,len)==1){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
class Node:
    def __init__(self,key,left,right,parent):
        self.key = key
        self.left = left
        self.right = right
        self.p = parent

    def __repr__(self):
        return str(self.key)

def insert(T, z):
    y = None
    x = T 
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    #print(x,y,z)
    if y == None:
        #print("Y==None")
        T = z
        print(T)
    elif z.key<y.key:
        #print("z.key<y.key")
        y.left = z
    else:
        #print("z.key<y.key")
        y.right = z

def printPreorder(x):
    if x == None:
        return
    printPreorder(x.left)
    print(end=' ')
    print(x,end='')
    printPreorder(x.right)

def printMidorder(x):
    if x == None:
        return
    print(end=' ')
    print(x,end='')
    printMidorder(x.left)
    printMidorder(x.right)

def printal(x):
    printPreorder(x)
    print()
    printMidorder(x)
    print()


N = int(input())
Q = input().split()
T = Node(int(Q[1]),None,None,None)
for i in range(N-1):
    Q = input().split()
    if Q[0] == "print":
        printal(T)
        continue
    insert(T,Node(int(Q[1]),None,None,None))



Measured memory_bytes: 105256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define INF 1000000007
using namespace std;
typedef long long ll ;

int a,b,c,d;


int main(){
    fastio;
    cin>>a>>b>>c>>d;

	cout<<(a-c) * (b-d)<<"\n";
		
    return 0;
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

// struct edge { int to, cost; };
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VECINT;
typedef vector<ll> VECLL;

struct UnionFind {
  int N;
  vector<int> par,ranc;

  UnionFind(int n) : N(n),par(n),ranc(n) { REP(i,n) par[i]=i,ranc[i]=0; }

  int root(int s) {
    if (par[s]==s) return s;
    else return root(par[s]);
  }

  void merge(int a,int b) {
    a = root(a);
    b = root(b);
    if (a==b) return;

    if (ranc[a]>ranc[b]) {
      par[b] = a;
    } else {
      par[a] = b;
      if (ranc[a]==ranc[b]) ranc[b]++;
    }
  }

  bool same(int a,int b) { return root(a)==root(b); }

  bool connected() {
    int base = root(0);
    REP(i,N) if (base != root(i)) return false;
    return true;
  }
};

int main() {
  int N;cin>>N;
  vector<tuple<int,int,int>> xtowns;
  vector<tuple<int,int,int>> ytowns;
  REP(i,N) {
    int x,y;cin>>x>>y;
    xtowns.push_back(make_tuple(x,y,i));
    ytowns.push_back(make_tuple(y,x,i));
  }

  sort(ALL(xtowns));
  sort(ALL(ytowns));
  struct edge { int cost,from,to; };
  auto compare = [](edge a,edge b) { return a.cost>b.cost; };
  priority_queue<edge,vector<edge>,decltype(compare)> es(compare);
  FOR(i,1,N) {
    int x1,y1,idx1;
    int x2,y2,idx2;
    tie(x1,y1,idx1) = xtowns[i-1];
    tie(x2,y2,idx2) = xtowns[i];
    es.push({abs(x2-x1),idx1,idx2});
  }
  FOR(i,1,N) {
    int x1,y1,idx1;
    int x2,y2,idx2;
    tie(y1,x1,idx1) = ytowns[i-1];
    tie(y2,x2,idx2) = ytowns[i];
    es.push({abs(y2-y1),idx1,idx2});
  }

  UnionFind uf(N);
  int ans = 0;
  while (!es.empty()) {
    edge e = es.top();es.pop();
    if (uf.root(e.from)==uf.root(e.to)) continue;
    uf.merge(e.from,e.to);
    ans += e.cost;
    if (uf.connected()) break;
  }
  OUT(ans);

  return 0;
}

Measured memory_bytes: 7340
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
LL N,A,B,C,D;
int main(){
	scanf("%lld %lld %lld %lld %lld",&N,&A,&B,&C,&D);
	N--;
	for (LL i=0;i<=N;i++){
		LL P=A+(i-(N-i))*C;
		if (B==P){
			cout<<"YES"<<endl; return 0;
		}
		if (B<P){
			P-=(N-i)*(D-C);
			if (P<=B){
				cout<<"YES"<<endl; return 0;
			}
		}
		else{
			P+=i*(D-C);
			if (P>=B){
				cout<<"YES"<<endl; return 0;
			}
		}
	}
	cout<<"NO";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(){
    while (1) {
        int n,m[2][3]={1,2,3},i,from,to,ans=1;
        scanf("%d",&n);
        if (n==0) {
            return 0;
        }
        for (i=0; i<n; i++) {
            char com[6];
            from=i%2;
            to=(i+1)%2;
            scanf("%s",com);
            if (!strcmp(com, "North")) {
                m[to][0]=m[from][1];
                m[to][1]=7-m[from][0];
                m[to][2]=m[from][2];
            }else if (!strcmp(com, "East")){
                m[to][0]=7-m[from][2];
                m[to][1]=m[from][1];
                m[to][2]=m[from][0];
            }else if (!strcmp(com, "South")){
                m[to][0]=7-m[from][1];
                m[to][1]=m[from][0];
                m[to][2]=m[from][2];
            }else if (!strcmp(com, "West")){
                m[to][0]=m[from][2];
                m[to][1]=m[from][1];
                m[to][2]=7-m[from][0];
            }else if (!strcmp(com, "Right")){
                m[to][0]=m[from][0];
                m[to][1]=m[from][2];
                m[to][2]=7-m[from][1];
            }else if (!strcmp(com, "Left")){
                m[to][0]=m[from][0];
                m[to][1]=7-m[from][2];
                m[to][2]=m[from][1];
            }
            ans+=m[to][0];
        }
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 604
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val nums = Seq.fill(n)(sc.nextInt())
  val xSqSum = nums.map(x => x * x).sum
  val xSum = nums.sum
  println {
    (for {
      i <- 1 to 100
    } yield {
      val `-2y` = -2 * i
      xSqSum + `-2y` * xSum + i * i * n
    }).min
  }
}

Measured memory_bytes: 25916
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define MP make_pair
#define all(s) (s).begin(), (s).end()
#define rev(s) (s).rbegin(), (s).rend()
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

struct edge{
	int to;
	int cost;
	edge(int t, int c){to=t; cost=c;}
	bool operator<(const edge &r)const{
		return cost>r.cost;
	}
};

int main(){
	int n, m;
	while(cin >> n, n){
		cin >> m;

		vector<vector<edge> > G(n);
		rep(i, m){
			int cost, from, to;
			char c;
			cin >> from >> c >> to >> c >> cost;
			G[from].push_back(edge(to, cost));
			G[to].push_back(edge(from, cost));
		}

		priority_queue<edge> q;
		rep(i, G[0].size()){
			q.push(G[0][i]);
		}
		vector<int> v;
		v.push_back(0);

		int sum = 0;
		while(v.size() < G.size()){
			edge e = q.top();
			q.pop();
			if( find(all(v), e.to) != v.end()) continue;
			v.push_back(e.to);
			sum += e.cost/100-1;

			rep(i, G[e.to].size()){
				q.push(G[e.to][i]);
			}
		}
		cout << sum << endl;

	}


	return 0;
}

Measured memory_bytes: 1516
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define LL long long
#define int long long
const LL inf=0x3f3f3f3f3f3f3f3fll;
int a[N],n,q,sa,sb;
inline LL read(){
	LL 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;
}
namespace segmentTree{
	LL minx[3][N<<2],tag[N<<2];
	int pushup(int x,LL val){
		minx[0][x]+=val;
		minx[1][x]+=val;
		minx[2][x]+=val;
		tag[x]+=val;
		return 0;
	}
	int pushdown(int x){
		pushup(x<<1,tag[x]);
		pushup(x<<1|1,tag[x]);
		tag[x]=0;
		return 0;
	}
	int update(int x){
		minx[0][x]=min(minx[0][x<<1],minx[0][x<<1|1]);
		minx[1][x]=min(minx[1][x<<1],minx[1][x<<1|1]);
		minx[2][x]=min(minx[2][x<<1],minx[2][x<<1|1]);
		return 0;
	}
	int build(int x,int l,int r){
		if (l==r){
			minx[0][x]=inf+l;
			minx[1][x]=inf+n-l+1;
			minx[2][x]=inf;
			return 0;
		}
		int mid=(l+r)>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		update(x);
		return 0;
	}
	int modify(int x,int l,int r,int L,int R,LL val){
		if (L<=l && r<=R){
			pushup(x,val);
			return 0;
		}
		int mid=(l+r)>>1;
		pushdown(x);
		if (L<=mid) modify(x<<1,l,mid,L,R,val);
		if (mid<R) modify(x<<1|1,mid+1,r,L,R,val);
		update(x);
		return 0;
	}
	LL query(int x,int l,int r,int L,int R,int id){
		if (L<=l && r<=R) return minx[id][x];
		int mid=(l+r)>>1;
		LL res=inf<<1;
		pushdown(x);
		if (L<=mid) res=min(res,query(x<<1,l,mid,L,R,id));
		if (mid<R) res=min(res,query(x<<1|1,mid+1,r,L,R,id));
		return res;
	}
} 
using namespace segmentTree;
signed main(){
	n=read(),q=read(),sa=read(),sb=read();
	for (int i=1;i<=q;++i) a[i]=read();
	a[0]=sa;
	build(1,1,n);
	modify(1,1,n,sb,sb,-inf);
	for (int i=1;i<=q;++i){
		LL tmp=min(query(1,1,n,1,a[i],1)-(n-a[i]+1),query(1,1,n,a[i],n,0)-a[i]);
		modify(1,1,n,1,n,abs(a[i]-a[i-1]));
		LL cnt=query(1,1,n,a[i-1],a[i-1],2);
		if (cnt>tmp) modify(1,1,n,a[i-1],a[i-1],tmp-cnt);
	}
	cout<<query(1,1,n,1,n,2)<<endl;
	return 0;
}

Measured memory_bytes: 26368
n = int(input())
xy = []
ans = 0
for _ in range(n):
    xy.append([int(i) for i in input().split()])
for i in range(n-1):
    for j in range(i+1, n):
        ans += ((xy[j][0] - xy[i][0])**2 + (xy[j][1] - xy[i][1])**2)**0.5
print(ans*2/n)

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

using namespace std;

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

    bool flg = false;
    for (int i = a; i <= b; i++) {
        if (i%k == 0) {
            flg = true;
            break;
        }
    }
    
    if (flg) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n)         for(int i=0; i<(n); i++)
#define P pair<int, int>
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"

//----------------------------------------------------

int main(){
    string s;
    cin >> s;
    string t = "2019/04/30";
    if(t >= s) cout << "Heisei" << endl;
    else cout << "TBD" << endl;

}

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

using namespace std;

long long int gcd(long long int a, long long int b){
	long long int r;
	if(a>b) swap(a, b);

	r=a%b;
	while(r!=0){
		a=b;
		b=r;
		r=a%b;
	}

	return b;
}

long long int lcm(long long int a, long long int b){
	long long int g;
	g=gcd(a, b);
	return a/g*b;

}

int main(){

	int n;
	long long int ans;
	vector<long long int> t;

	cin>> n;
	t.resize(n);

	for(int i=0;i<n;i++) cin>> t[i];

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

	ans=t[0];
	for(int i=1;i<n;i++){
		//cout<< ans << endl;
		ans=lcm(ans, t[i]);
	}

	cout<< ans << endl;


}

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

int main() {
  ll N; cin>>N;
  vector<ll> a(N);
  for(ll i=0; i<N; i++){
    cin>>a[i];
  }
  sort(begin(a),end(a),greater<ll>());
  using tup = tuple<ll,ll,ll>;
  queue<tup> q;
  ll sum = a.front();
  tup t=make_tuple(0,1,a[1]);
  q.push(t);
  t=make_tuple(0,1,a[1]);
  q.push(t);

  for(ll i=2; i<N; i++){
    tup tt = q.front();
    q.pop();
    sum += get<2>(tt);
    tup t0=make_tuple(get<0>(tt),i,a[i]);
    tup t1=make_tuple(get<1>(tt),i,a[i]);
    q.push(t0);
    q.push(t1);
  }
  cout<<sum<<endl;
  return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    multiset<ll> st;
    REP(i, N){
    	auto itr = st.upper_bound(-A[i]);
    	if(itr == st.end()){
    		st.insert(-A[i]);
    	}else{
    		st.erase(itr);
    		st.insert(-A[i]);
    	}
    	//for(auto x: st) cout << x <<endl;
    	//cout << endl;
    }
    cout << st.size() << endl;
    return 0;
}

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

const int N = 200005;

int n, k, a[N], b[N], sum;

void solve()
{
	memset(b, 0, sizeof(b));
	for (int i = 1; i <= n; i++) b[max(1, i - a[i])]++, b[min(n + 1, i + a[i] + 1)]--;
	sum = 0;
	for (int i = 1; i <= n; i++) b[i] += b[i - 1], a[i] = b[i], sum += a[i] == n;
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	while (k-- && sum < n) solve();
	for (int i = 1; i <= n; i++) printf("%d ", a[i]);
	return 0;
}

Measured memory_bytes: 5384
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    string a;
    cin >> a;
    if(a == "Cloudy"){
        cout << "Rainy";
    }
    if(a == "Rainy"){
        cout << "Sunny";
    }
    if(a == "Sunny"){
        cout << "Cloudy";
    }
    cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a,b=0,i,c,d;
for(i=0;i<4;i++){
scanf("%d\n",&a);
b=b+a;
}
c=b/60;
d=b%60;
printf("%d\n%d\n",c,d);
return 0;
}



Measured memory_bytes: 2148
def frog(H,N):
    #print(H)
    DP = [10**10]*N
    #DP = [0]*N
    DP[0] = 0
    DP[1] = abs(H[1]-H[0])
    

    for i in range(2,N):
        diff1 = abs(H[i]-H[i-1])
        diff2 = abs(H[i]-H[i-2])
        #DP[i] = min(abs(H[i]-H[i-2])+DP[i-2],abs(H[i]-H[i-1])+DP[i-1])
        #print(DP[i],DP)
        DP[i] = chmin(DP[i],DP[i-1]+diff1)
        #print(DP[i])
        DP[i] = chmin(DP[i],DP[i-2]+diff2)
        #print(DP[i])
        #print(DP)
    #print(DP)
    return DP[-1]

def chmin(a,b):
    if a < b:
        return a
    else:
        return b

if __name__ == '__main__':
    N = int(input())
    H = list(map(int,input().split()))
    ans = frog(H,N)
    print(ans)
    

Measured memory_bytes: 13924
# 上位ノードほど @rank が大きい数字となる
class Node
  attr_accessor :parent, :rank

  # 親は自分自身、ランクは 0 として初期化する
  def initialize(n)
    @parent = n
    @rank = 0
  end
end

class UnionFind
  # 0 から n - 1 までのノードを初期化する
  def initialize(n)
    @nodes = (0...n).map { |i| Node.new(i) }
  end

  # 再帰で最も上位の親を探し、その値を返す（更新しないため少し遅い）
  def root(x)
    return x if @nodes[x].parent == x
    root(@nodes[x].parent)
  end

  # a と b を仲間にする
  def unite(a, b)
    a_root = root(a)
    b_root = root(b)
    # a 及び b の親が同じ場合は何もしない
    return if a_root == b_root

    # a親ランク < b親ランク の場合は、b親をa親の親とする
    # なお、ランクをいじる必要はなし
    if @nodes[a_root].rank < @nodes[b_root].rank
      @nodes[a_root].parent = b_root
    # その他の場合は、a親をb親の親とする
    else
      @nodes[b_root].parent = a_root
    # a親、及びb親のランクが同じ場合は、a親のランクを +1 する
      @nodes[a_root].rank += 1 if @nodes[a_root].rank == @nodes[b_root].rank
    end
  end

  # a と b の最も上位の親が同じかどうかを返す
  def same?(a, b)
    root(a) == root(b)
  end

  # 各ノードの親を全て出力する確認用
  def parents
    @nodes.map(&:parent)
  end
  
  # 各ノードの最も上位の親を全て出力する確認用
  def roots
    @nodes.size.times.map { |i| root(i) }
  end
end

n, m = gets.split.map(&:to_i)
numbers = gets.split.map(&:to_i)
numbers_where = []
numbers.each_with_index do |num, index|
  numbers_where[num - 1] = index
end
edges = []
m.times { edges << gets.split.map(&:to_i).map(&:pred) }
tree = UnionFind.new(n)
edges.each { |x, y| tree.unite(x, y) }
count = 0
numbers.each_with_index do |num, index|
  count += 1 if tree.same?(index, numbers_where[index])
end
puts count


Measured memory_bytes: 17668
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(int)(a); i++)
typedef long long ll;
const ll mod = 1000000007;

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

int main()
{
  ll n, k; cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll g = a[0];
  rep(i, n) g = gcd(g, a[i]);
  rep(i, n) {
    if (a[i] < k) continue;
    ll t = a[i]%k;
    if (t%g == 0) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
    ll n;
    cin >> n;
    int a[n];
    for(int i = 0;i<n;i++) cin >> a[i];
    ll k = 0,t = 1;
    for(int i = 0;i<n;i++)
    {
        if(a[i] == t)
        {
            k++;
            t++;
        }
    }
    if(k>0)cout << n - k << endl;
    else cout << -1 << endl;
    return 0;
}



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

ll a[500][500];
ll s[510][510];

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

	int H, W, h, w;
	cin >> H >> W >> h >> w;

	ll sum = 0;
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			a[i][j] = 1 * 1000;
			sum += a[i][j];
		}
	}
	for(int i = h - 1; i < H; i += h) {
		for(int j = w - 1; j < W; j += w) {
			sum -= a[i][j];
			a[i][j] = -(h * w - 1) * 1000 - 1;
			assert(abs(a[i][j]) <= (int)1e9);
			sum += a[i][j];
		}
	}

	if(sum <= 0) {
		cout << "No" << endl;
	}
	else{
		cout << "Yes" << endl;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				cout << a[i][j] << " ";
			}
			cout << endl;
		}
	}
}


Measured memory_bytes: 3584
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, n) revi(i, 0, n)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define allr(n) (n.rbegin(), n.rend())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

int main() {
  char X, Y;
  ci(X, Y);
  if(X < Y){
    co('<');
  }
  else if(X == Y){
    co('=');
  }
  else{
    co('>');
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>

using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;

int main()
{
  ll n;
  cin >> n;
  cout << (n*(n-1))/2 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 100000000

int main() {
	int ans = 0;
	string s, t;
	cin >> s >> t;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] != t[i]) ans++;
	}

	cout << ans;
	return 0;
}

Measured memory_bytes: 3932