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

template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}
struct maxhist{
  vector<int> hist;
  struct rect{int height,idx;};

  void add_hist(int a){
    hist.push_back(a);
  }

  int get_max(){
    int res=0;
    stack<rect> s;
    for(int j=0;j<hist.size();j++){
      if((!s.size())||s.top().height<hist[j])s.push({hist[j],j});
      else if(s.top().height>hist[j]){
        int left;
        while(s.top().height>hist[j]){
          rect tmp=s.top();s.pop();
          left=tmp.idx;
          //chmax(res,tmp.height*(j-left));
          chmax(res,(tmp.height+1)*(j-left+1));
          if(!s.size())break;
        }
        s.push({hist[j],left});
      }
    }
    while(s.size()){
      rect tmp=s.top();s.pop();
      //chmax(res,tmp.height*(hist.size()-tmp.idx));
      chmax(res,(tmp.height+1)*((int)hist.size()-tmp.idx+1));
    }
    return res;
  }
};
struct maxrect{
  vector<vector<bool>> rect;

  void add_line(vector<bool> &v){
    rect.push_back(v);
  }
  void add_dot(int h,bool f){
    if(rect.size()<=h)rect.resize(h+1);
    rect[h].push_back(f);
  }

  int get_max(){
    int res=0;
    int h=rect.size();
    vector<vector<int>> hist(h);
    for(int i=0;i<h;i++)hist[i].resize(rect[i].size());
    for(int i=0;i<h;i++){
      maxhist mh;
      for(int j=0;j<hist[i].size();j++){
        if(i){
          if(hist[i-1].size()<=j)hist[i][j]=rect[i][j];
          else hist[i][j]=(hist[i-1][j]+rect[i][j])*rect[i][j];
        }
        else hist[i][j]=rect[i][j];
        mh.add_hist(hist[i][j]);
      }
      chmax(res,mh.get_max());
    }
    return res;
  }
};

signed main(){
  int h,w;cin>>h>>w;
  vector<string> s(h);
  for(int i=0;i<h;i++)cin>>s[i];
  maxrect m;
  vector<bool> f(w-1);
  for(int i=1;i<h;i++){
    for(int j=0;j<w-1;j++){
      int a=(s[i-1][j]=='#')+(s[i-1][j+1]=='#')+(s[i][j]=='#')+(s[i][j+1]=='#');
      f[j]=(a&1)^1;
    }
    m.add_line(f);
  }
  cout<<max({h,w,m.get_max()})<<endl;
}


Measured memory_bytes: 20736
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	
	static boolean[] isPrime;
	static int[][] data;
	static int size = 1000 + 2;
	static int set = size / 2 - 1;
	
	static void prime() {
		isPrime = new boolean[1000001];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
		for(int i=2; i*i<=1000000; i++) {
			if(isPrime[i]) {
				for(int j=i+i; j<=1000000; j+=i) {
					isPrime[j] = false;
				}
			}
		}
	}
	
	static void numArray() {
		data = new int[size][size];
		for(int i = 0; i < size; i++){
			Arrays.fill(data[i], 1<<24);
		}
		int now = 1, posx = set, posy = set;
		for(int i=1; now<=1000000; i++){
			System.out.print("");
			if(i % 2 == 1){
				for(int j=0; j<i && now<=1000000; j++){
					data[posy][posx] = now;
					posx++;
					now++;
				}
				for(int j=0; j<i && now<=1000000; j++){
					data[posy][posx] = now;
					posy--;
					now++;
				}
			}
			else {
				for(int j=0; j<i && now<=1000000; j++){
					data[posy][posx] = now;
					posx--;
					now++;
				}
				for(int j=0; j<i && now<=1000000; j++){
					data[posy][posx] = now;
					posy++;
					now++;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			prime();
			numArray();
			while(sc.hasNext()) {
				int m = sc.nextInt();
				int n = sc.nextInt();
				if(m + n == 0) break;
				
				int x = -1;
				int y = -1;
				for(int i= 0; i<size; i++) {
					for(int j=0; j<size; j++) {
						if(data[i][j] == n) {
							y = i;
							x = j;
						}
					}
				}
				
				int[][] dp = new int[size][size];
				dp[y][x] = 1;
				int max = 1;
				int num = 0;
				for(int i=y; i<size; i++) {
					for(int j=0; j<size; j++) {
						if(i == y && data[i][j] != n) continue;
						if(data[i][j] > m) continue;
						if(dp[i][j] == 0) continue;
						
						if(isPrime[data[i][j]]) {
							dp[i][j]++;
							if(max < dp[i][j]) {
								max = dp[i][j];
								num = data[i][j];
							}
							else if(max == dp[i][j]) {
								if(num < data[i][j]) {
									num = data[i][j];
								}
							}
						}
						
						dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j]);
						if(j >= 1) {
							dp[i+1][j-1] = Math.max(dp[i+1][j-1], dp[i][j]);
						}
						if(j + 1 < 1002) {
							dp[i+1][j+1] = Math.max(dp[i+1][j+1], dp[i][j]);
						}
					}
				}
				System.out.println(max-1 + " " + num);
			}
		}
	}
}



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

int w,h;

int curling(int a[20][20],int sh,int sw,int d)
{
	int i,c=-1,tmp;
	if(d>10){return -1;}
	else{
		if(sw-1>=0 && a[sh][sw-1]!=1)
			{
				for(i=sw-1;i>=0;i--)
				{
					if(a[sh][i]==1)
						{
							a[sh][i]=0;
							tmp = curling(a,sh,i+1,d+1);
							if(c < 0 || (c > tmp && tmp > 0))
							{c = tmp;}
							a[sh][i]=1;
							break;
						}
					if(a[sh][i]==3)
						{
						  return d;
						}
				}
			}
	
		if(sw+1>=0 && a[sh][sw+1]!=1)
			{
				for(i=sw+1;i<w;i++)
				{
					if(a[sh][i]==1)
						{
							a[sh][i]=0;
							tmp = curling(a,sh,i-1,d+1);
							if(c < 0 || (c > tmp && tmp > 0))
							{c = tmp;}
							a[sh][i]=1;
							break;
						}
					if(a[sh][i]==3)
						{
						  return d;
						}
				}
			}

		if(sh-1>=0 && a[sh-1][sw]!=1)
		{
			for(i=sh-1;i>=0;i--)
			{
				if(a[i][sw]==1)
					{
						a[i][sw]=0;
						tmp = curling(a,i+1,sw,d+1);
						if(c < 0 || (c > tmp && tmp > 0))
						{c = tmp;}
						a[i][sw]=1;
						break;
					}
				if(a[i][sw]==3)
					{
						return d;
					}
			}
		}
		
		if(sh+1>=0 && a[sh+1][sw]!=1)
		{
			for(i=sh+1;i<h;i++)
			{
				if(a[i][sw]==1)
					{
						a[i][sw]=0;
						tmp =  curling(a,i-1,sw,d+1);
						if(c < 0 || (c > tmp && tmp > 0))
						{c = tmp;}
						a[i][sw]=1;
						break;
					}
				if(a[i][sw]==3)
					{
						return d;
					}
			}
		}
	}
	return c;
}


int main(void)
{
	int i,j;
	int a[20][20];
	int sw,sh,gw,gh;
	
	while(1)
	{
		scanf("%d %d ",&w,&h);
		if(w == 0 && h == 0)break;
		
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				scanf("%d ",&a[i][j]);
				if(a[i][j] == 2){sh=i;sw=j;}
			}
		}
		
		printf("%d\n",curling(a,sh,sw,1));
	}
	return 0;
}

Measured memory_bytes: 412
n, k=gets.split.map(&:to_i)

m=10**5+5
c=Array.new(m){0}
d=Array.new(m){0}
n.times do
  a, b=gets.split.map(&:to_i)
  c[a+1]+=b
  # c[m-1]-=b
  d[a]+=b
end
m.times do |i|
  if i>0
    c[i]+=c[i-1]
  end
end
m.times do |i|
  if i>0
    if c[i]<k and c[i]+d[i]>=k
      puts i
      exit(0)
    end
  end
end


Measured memory_bytes: 5372
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
# N, M = map(int, input().split(' '))
X = int(input())

gojou = []
i = 0
saidai = 10**12

while 1:
    temp = i**5
    if temp > saidai:
        break
    gojou.insert(0, [i, temp])
    gojou.insert(0, [-i, -temp])
    i += 1

ls = len(gojou)
for i in range(ls):
    for j in range(i, ls):
        if gojou[i][1]-gojou[j][1] == X:
            print(gojou[i][0], gojou[j][0])
            exit()


Measured memory_bytes: 67796
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> g[100001];
bool flag[100001];
int d[2][100001];

void dfs(int pos, int num, int start) {
    for (int i = 0; i < g[pos].size(); ++i) {
        d[start][pos] = num;
        if (!flag[g[pos][i]]) {
            flag[pos] = true;
            dfs(g[pos][i], num + 1, start);
            flag[pos] = false;
        }
    }
}

int main(void) {
    cin >> N;
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0, 1);
    dfs(N, 0, 0);

    int fe = 0, su = 0;
    for (int i = 1; i <= N; ++i) {
        if (d[1][i] <= d[0][i]) fe++;
        else su++;
    }

    cout << (fe > su ? "Fennec" : "Snuke") << endl;
    return 0;
}

Measured memory_bytes: 14464
<?php
// Here your code !
    for($i=1; $i<=9; $i++){
        for($j=1; $j<=9; $j++){
            $result = $i * $j;
            if($i*$j==81){
                echo "$i"."x"."$j"."="."$result";
            }else{
            echo "$i"."x"."$j"."="."$result\n";
        }
            
        }
    }
?>

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

int main()
{
    ll h, n;
    cin >> h >> n;
    ll sum = 0;
    while (n--) {
        ll a;
        cin >> a;
        sum += a;
    }
    if (sum >= h) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
    return 0;
}

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

/*==========type============*/
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
typedef std::pair<std::string,ll> psl;

/*==========constant============*/
#define INF INT_MAX
#define INF_L LONG_MAX
#define INF_LL LLONG_MAX
#define MOD 1000000007

/*==========function============*/
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

using namespace std;

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

    ll n;
    cin >> n;
    vector< vector<ll> > abc(n,vector<ll>(3));
    REP(i,0,n){
        REP(j,0,3){
            cin >> abc[i][j];
        }
    }

    vector<vector<ll>> dp(n,vector<ll>(3));
    dp[0][0] = abc[0][0];
    dp[0][1] = abc[0][1];
    dp[0][2] = abc[0][2];

    REP(i,1,n){
        REP(j,0,3){
            ll x = dp[i-1][(j+1)%3], y = dp[i-1][(j+2)%3];
            dp[i][j] = x > y ? x : y;
            dp[i][j] += abc[i][j]; 
        }
    }
    
    ll ans = 0;
    REP(i,0,3){
        ans = max(dp[n-1][i],ans);
    }

    cout << ans << endl;

    return 0;
}    

Measured memory_bytes: 14216
#include <iostream>
using namespace std;
int main(){
  int n,a,b,c,x,xn,y[100],i,endcnt,flag;
  while(1){
    flag=0;
    endcnt=0;
    cin >> n >> a >> b >> c >> x;
    if(n==0&&a==0&&b==0&&c==0&&x==0) break;
    for(i=0;i<n;i++){
      cin >> y[i];
    }
    i=0;
    xn=x;
    while(1){
      if(xn==y[i]){
        i++;
      }
      if(i==n){
	flag=1;
        break;
      }
      endcnt++;
      if(endcnt==10001){
	break;
      }
      xn=(a*x+b)%c;
      x=xn;
    }
    if(flag==0) cout << -1 << endl;
    else cout << endcnt << endl;
  }
  return 0;
}

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

int gcd2(int a){
    int count = 0;
    while(a%2 == 0){
        a = a/2;
        count ++;
    }

    return count;
}

int main(){
    int n;
    cin >> n;
    int mincount = 1000000000;

    for(int i=0; i<n; i++){
        int newnum;
        cin >> newnum;
        mincount = min(mincount, gcd2(newnum));
    }

    cout << mincount << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int r,d,s;
    cin>>r>>d>>s;
    int n[11];
    n[0]=s;
    for(int i=1;i<=10;i++){
        n[i]=r*n[i-1]-d;
        cout<<n[i]<<endl;
    }
}

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

int main() {
  int N;
  cin >> N;
  bool check = true;
  for(int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if(a % 2 == 0) {
      if (a % 3 != 0 && a % 5 != 0) {
        check = false;
      }
    }
  }
  if(check) {
    cout << "APPROVED" << endl;
  }
  else {
    cout << "DENIED" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int n;
	long long s = 1;
	cin >> n;
	while (n)s *= n--;
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int h1,h2,h3;
	h1=a+a-1;
	h2=b+b-1;
	h3=a+b;
	cout<<max(h1,max(h2,h3));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ull = long long unsigned;
using P = pair<int,int>;
const int INF=1001001;
const int NMAX=8;
const int mod = 1000000007;

int main()
{
  double l;
  cin>>l;
  double a=l/3;
  double ans=a*a*a;
  cout<<fixed << setprecision(8)<<ans;


}


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

using namespace std;
using ll =long long;
#define rep(i,n) ;for( int i =0; i < n ; i ++)
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}

int abs(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int fiv(int n){
  if(n==0){
    return 0;
  }
  else if(n==1){
    return 1;
  }
  return fiv(n-1)+fiv(n-2);
}
ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}
int main(){
  ll n;
  cin>>n;
  cout<< (n+1)/2<<endl;

  
}



Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main(){
    let n = read::<usize>();
    let mut v = vec![0;n];
    let mut ans = 0.0;

    for x in 0..n {
        v[x] = read::<usize>();
    }

    v.sort();

    ans += (v[0] as f64) / u64::pow(2u64, (n-1) as u32) as f64;
    for x in 1..n {
        ans += (v[x] as f64) / u64::pow(2u64, (n-x) as u32) as f64;
    }

    println!("{}",ans);

}


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

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define INF INT_MAX/3
#define ALL(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define ll long long
#define ull unsigned long long

#define PI (3.141592653589794)
#define eps 1e-8

int main() {
	int n;
	long long a[100000] = {};
	ll dp[100000] = {};
	ll ans;
	cin >> n;
	REP(i, n) {
		cin >> a[i];
		dp[i] = (i == 0 ? 0 : dp[i - 1]) + a[i];
	}
	ll pos_ans = 0, pos_diff = 0;
	ll neg_ans = 0, neg_diff = 0;
	// + - + - +
	REP(i, n) {
		if (i % 2 == 0) {
			if (dp[i] + pos_diff <= 0) {
				ll change = (1 - (dp[i] + pos_diff));
				pos_ans += change;
				pos_diff += change;
			}
		}
		else {
			if (dp[i] + pos_diff >= 0) {
				ll change = ((dp[i] + pos_diff) + 1);
				pos_ans += change;
				pos_diff -= change;
			}
		}
	}

	// - + - + -
	REP(i, n) {
		if (i % 2 == 1) {
			if (dp[i] + neg_diff <= 0) {
				ll change = (1 - (dp[i] + neg_diff));
				neg_ans += change;
				neg_diff += change;
			}
		}
		else {
			if (dp[i] + neg_diff >= 0) {
				ll change = ((dp[i] + neg_diff) + 1);
				neg_ans += change;
				neg_diff -= change;
			}
		}
	}

	cout <<  min(pos_ans, neg_ans) << endl;
}

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

int main(){
    long long X, start(100), cnt(0);
    scanf("%lld", &X);

    while (start < X){
        start *= 1.01;
        cnt++;
    }

    printf("%lld\n", cnt);
    return 0;
}


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

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < n; ++i) cout << s[i] << t[i];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)




int main() {
    ll n;
    cin >> n;
    priority_queue<ll> que;
    REP(i, n){
        ll a;
        cin >> a;
        que.push(a);
    }
    
    ll ans = 0;
    for(;;){
        ll t1 = que.top(), t2 = t1 + ans; que.pop();
        if(n > t2) break;
        
        ans += t2 / n;
        t1 -= n * (t2 / n) + t2 / n;
        
        que.push(t1);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ff first
#define ss second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long 
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define print_time cerr << "Time elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define ull unsigned long long
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
int gcd(int x,int y)
{
   // cout<<x<<' '<<y<<endl;
    if(y==0)
    return x;
    else
    return gcd(y,x%y);
}
int expo(int n,int m,int p)   //modULAR EXPONENTIATION
{
    int r=1;
    n=n%p;
    while(m>0)
    {
    if(m%2)
	r=(r*n)%p;
    n=(n*n)%p;
    m=m/2;
    }
    return r%p;
}
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;
 
    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;
 
    for (int i=5; i*i<=n; i=i+6)
    if (n%i == 0 || n%(i+2) == 0)
       return false;
 
    return true;
}
vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r)
	z[i] = min (r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
	++z[i];
    if (i + z[i] - 1 > r)
	l = i, r = i + z[i] - 1;
    }
    return z;
}
int n,k;
int dp[100005],h[100005];
int solve(int i)
{
	if(i==n-1)
		return 0;
	if(dp[i]!=-1)
		return dp[i];
	int ans=inf;
	for(int j=1;j<=k;j++){
		if(i+j<n)
	ans=min(ans,abs(h[i]-h[i+j])+solve(i+j));
}
	
	dp[i]=ans;
	return ans;
}
int32_t main()
{
   IOS;
   /*#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin); 
   freopen("output.txt","w",stdout);
   #endif
   /********************* Code starts here ***********************/
   memset(dp,-1,sizeof(dp));
   cin>>n>>k;
   for(int i=0;i<n;i++)
   {
   	cin>>h[i];
   }
   cout<<solve(0)<<endl;
}                       

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

#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())

typedef complex<double> P;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}
bool deq(double a,double b) {return abs(a-b)<eps;}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// 真ん中の切れ目を決めた後左右の2個をなるべく均等に切るのが最善
int n, a[200200], b[200200], res = LONG_LONG_MAX;
int p, q, r, s;

void le(int m) {
	int sum = b[m];
	int t = lower_bound(b,b+n,sum/2) - b;
	p = b[t], q = b[m]-b[t];
	while (1) {
		t--;
		if (t<=0) break;
		int be = abs(p-q), nw = abs(b[t] - (b[m]-b[t]));
		if (nw<be) p = b[t], q = b[m]-b[t];
		else break;
	}
}

void ri(int m) {
	int sum = b[n] - b[m-1];
	int sea = b[m-1] + sum/2;
	int t = lower_bound(b,b+n,sea) - b;
	r = b[t] - b[m-1], s = b[n]-b[t];
	while (1) {
		t--;
		if (t<=0) break;
		int rr = b[t] - b[m-1], ss = b[n]-b[t];
		int be = abs(r-s), nw = abs(rr-ss);
		if (nw<be) r = rr, s = ss;
		else break;
	}
}

signed main() {
	cin >> n;
	repst(i,1,n) {
		cin >> a[i];
		b[i] = a[i] + b[i-1];
	}
	// i:左半分の右端
	repst(i,2,n-2) {
		int sl = b[i], sr = b[n] - b[i];
		int gl = sl/2, gr = sl + sr/2;
		le(i), ri(i+1);
		int mn = tmin(p,q,min(r,s)), mx = tmax(p,q,max(r,s));
		chmin(res, mx-mn);
	}
	cout << res << ln;
}

Measured memory_bytes: 3456
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vi2;
typedef vector<vi2> vi3;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<vll> vll2;
typedef vector<vll2> vll3;
typedef vector<bool> vb;

#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define umap unordered_map
#define uset unordered_set
#define vec vector
#define loop(a) for (auto &x : a)
#define all(a) a.begin(), a.end()
#define mp make_pair

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

    int n, m;
    cin >> n >> m;
    vi2 adj(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vi dist(n, -1), from(n, -1);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    int cnt = 0;
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        cnt++;
        loop(adj[h]) {
            if (dist[x] == -1) {
                dist[x] = dist[h] + 1;
                from[x] = h;
                q.push(x);
            }
        }
    }
    if (cnt < n) {
        cout << "No" << el;
    } else {
        cout << "Yes" << el;
        rep(i, 1, n) {
            cout << from[i] + 1 << el;
        }
    }
}


Measured memory_bytes: 10204
N = int(input())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

ans = 0
for i in range(N-1,-1,-1):
    if (A[i] + ans) % B[i] != 0:
        ans += B[i]-((A[i] + ans) % B[i])

print(ans)

Measured memory_bytes: 56792
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    let n: f64 = get();
    let m: f64 = get();
    let d: f64 = get();
    let tmp;
    if d == 0.0 {
        tmp = n;
    } else {
        tmp = 2.0 * (n - d);
    }
    println!("{:.15}", tmp * (m - 1.0) / n / n);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

// Ax = v
// 疎な連立方程式を解く
// Eが辺
// xが最終的な辺の係数

struct edge{
  ll from, to, num;
  edge(ll a, ll b, ll c):from(a), to(b), num(c){}
};
struct graphMatSolver{
  vector<bool> used;
  vector<ll> x, v;
  vector<vector<edge>> G;
  vector<edge> E;
  ll cnt = 0;
  ll N, M;

  graphMatSolver(ll max_n, ll max_m, vll dat){
    N = max_n, M = max_m;
    used.resize(N, false);
    x.resize(M, 0);
    v.resize(N, 0);
    G.resize(N);
    for(int i=0;i<dat.size();i++) v[i] = dat[i];
  }

  void err(){
    std::cout << -1 << '\n';
    exit(0);
  }

  void add_edge(ll from, ll to){
    if(from==to) return;
    G[from].push_back(edge(from, to, cnt));
    G[to].push_back(edge(from, to, cnt));
    E.push_back(edge(from, to, cnt));
    cnt++;
  }

  ll dfs(ll now){
    ll ret = v[now];
    used[now] = true;
    for(auto e:G[now]){
      ll to = (e.to==now?e.from:e.to);
      if(used[to]) continue;
      ll tmp = dfs(to);
      if(now==e.from) x[e.num] = tmp;
      else x[e.num] = tmp;
      ret ^= tmp;
    }
    return ret;
  }

  void solve(){
    for(int i=0;i<N;i++){
      if(used[i]) continue;
      ll y = dfs(i);
      if(y!=0) err();
    }
  }

  edge & operator [](int k){
    return E[k];
  }
};

int main(int argc, char const *argv[]) {
  ll n, m;std::cin >> n >> m;
  vvl T;
  vll z(n+1, 0);
  for(int i=0;i<m;i++){
    ll a, b;scanf("%lld %lld", &a, &b);
    a--, b--;
    T.push_back(vll{a, b});
    // a -> b
    z[a]^=1;
  }

  graphMatSolver mg(n+1, m+1, z);
  for(auto e:T) mg.add_edge(e[0], e[1]);
  mg.solve();
  for(auto e:mg.E) {
    if(mg.x[e.num]){
      std::cout << e.to+1 << " " << e.from+1 << '\n';
    }else{
      std::cout << e.from+1 << " " << e.to+1 << '\n';
    }
  }

  return 0;
}


Measured memory_bytes: 27056
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;++i)cin>>a[i];
  for(int i=1;i<n;++i)a[i]+=a[i-1];
  a.push_back(0);
  sort(a.begin(),a.end());
  int res=0,cnt=1;
  for(int i=0;i<n;++i){
    if(a[i]!=a[i+1]){
      res+=(cnt*(cnt-1))/2;
      cnt=1;
    }
    else cnt++;
  }
  res+=(cnt*(cnt-1))/2;
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 4736
// 420 Digits K
// 2019.12.26 bal4u

#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

char A[200005];
typedef struct { char a; int i; } T;
T a[200005], b[200005];
int f[128];

void distsort(T *ain, T *aout, int sz) {
	int i, x;

	for (i = 0; i < sz; ++i) ++f[ain[i].a];
	for (i = '9'; i > '0'; i--) f[i-1] += f[i];
	for (i = sz-1; i >= 0; i--) {
		x = ain[i].a, aout[--f[x]].a = x, aout[f[x]].i = ain[i].i;
	}
}

int main()
{
	int i, k, K, N;
	
    N = in(), K = in();
    if (K == 0) {
        while (N--) pc(gc()), gc();
    } else {
        for (i = 0; i < N; ++i) {
			A[i] = gc(), gc();
			b[i].i = i, b[i].a = A[i];
		}
		distsort(b, a, N);
		
		k = -1;
		for (i = 0; K < N; ++i) {
			if (a[i].a < A[K]) break;
			if (k < a[i].i && a[i].i < K) {
				pc(a[i].a), k = a[i].i, ++K;
			}
		}
		while (K < N) pc(A[K++]);
	}
	pc('\n');
	return 0;
}


Measured memory_bytes: 4920
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int x[m];
  for(int i=0; i<m; i++){
    cin>>x[i];
  }
  sort(x,x+m);
  vector<int>v;
  for(int i=0; i<m-1; i++){
    v.push_back(x[i+1]-x[i]);
  }
  sort(v.rbegin(),v.rend());
  long long sum=0;
  for(int i=0; i<v.size(); i++){
    sum+=v[i];
  }

  for(int i=0; i<n-1&&i<v.size(); i++){
    sum-=v[i];
  }
  cout<<sum<<endl;

}

Measured memory_bytes: 1276
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}

	vector<vector<int>> dp(n + 1, vector<int>(3));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			switch (j) {
			case 0:
				dp[i + 1][j] = max(dp[i][1] + a[i], dp[i][2] + a[i]);
				break;
			case 1:
				dp[i + 1][j] = max(dp[i][2] + b[i], dp[i][0] + b[i]);
				break;
			case 2:
				dp[i + 1][j] = max(dp[i][0] + c[i], dp[i][1] + c[i]);
				break;
			}
		}
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;

	return 0;
}

Measured memory_bytes: 6912
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

int p[6][6] = {{-1, 3, 5, 2, 4, -1}, //
               {4, -1, 1, 6, -1, 3},
               {2, 6, -1, -1, 1, 5},
               {5, 1, -1, -1, 6, 2},
               {3, -1, 6, 1, -1, 4},
               {-1, 4, 2, 5, 3, -1}};

main {
  auto v = in(vector<int>(6));
  int q;
  cin >> q;
  while (q--) {
    int a, b, i, j;
    cin >> a >> b;
    rep(k, 6) {
      if (a == v[k]) i = k;
      if (b == v[k]) j = k;
    }
    cout << v[p[i][j] - 1] << endl;
  }
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x, y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb3(x, y, z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

template <typename T>void print(T v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<v.size(); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto i= v.begin(); i!=v.end(); i++)cout<<setw(w)<<*i<<" ";cout<<endl;}
template <typename T>void print_vv(T v){if(v.size()==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<v[0].size(); j++)cout<<setw(w)<<j<<" ";cout<<endl;for(auto i= 0; i<v.size(); i++){cout<<i<<" {";for(auto j = 0; j!=v[i].size(); j++){cout<<setw(w)<<v[i][j]<<",";}cout<<"},"<<endl;}cout<<endl;}
template <class T, class U> void print_m(map<T,U> m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}

int main(){
    string s; int q,t,f; char c;
    while(cin>>s>>q){
        string beg, ed;
        bool rev = false;
        forn(i,q){
            cin>>t;
            if(t==1){
                rev=!rev;
            }else{
                cin>>f>>c;
                if(f==1){
                    if(!rev){
                        beg.push_back(c);
                    }else{
                        ed.push_back(c);
                    }
                }else{
                    if(!rev){
                        ed.push_back(c);
                    }else 
                        beg.push_back(c);
                }
            }
        }

        if(!rev){
            reverse(all(beg));
            cout<<beg<<s<<ed<<endl;
        }else{
            reverse(all(ed));
            reverse(all(s));
            cout<<ed<<s<<beg<<endl;
        }
        
    }
    return 0;
}

Measured memory_bytes: 1088
import scala.io.StdIn._
object Main extends App {

  val n: Int = readInt()
  val pointSeq: Seq[(Int, Int)] = Seq.fill(n)(readLine().split(" ").map(_.toInt))
    .map(arr => (arr(0), arr(1)))


  val combinationOf2Points: Seq[(Int, Int)] = (0 until n).combinations(2)
    .map(points => (points(0), points(1))).toSeq

  val pointsAndDistanceMap: Map[(Int, Int), Double] = combinationOf2Points.map { case (p1, p2) =>
    val distance = calcDistance(pointSeq(p1), pointSeq(p2))
    ((p1, p2), distance)
  }.toMap

  def solve() = {
    val permutations: Seq[Seq[Int]] = (0 until n).permutations.toSeq
    val allRoutesDistance = permutations.foldLeft(0D) { case (acc, route) =>
      acc + calcDistanceOfRoute(route)
    }
    allRoutesDistance / permutations.length
  }

  def calcDistance(point1: (Int, Int), point2: (Int, Int)): Double = {
    val (x1, y1) = point1
    val (x2, y2) = point2
    val dx = x1 - x2
    val dy = y1 - y2
    Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2))
  }

  def calcDistanceOfRoute(route: Seq[Int]): Double = {
    val lastPoint = route.length - 1
    (0 until lastPoint).foldLeft(0D) { case (acc, point1Idx) =>
      val point2Idx = if(point1Idx == lastPoint) 0 else point1Idx + 1
      val p1 = route(point1Idx)
      val p2 = route(point2Idx)
      acc + pointsAndDistanceMap.getOrElse((p1, p2), pointsAndDistanceMap(p2, p1))
    }
  }


  println(solve())

}


Measured memory_bytes: 53856
from collections import deque
H, W = map(int, input().split())
s_list = []
for _ in range(H):
    s = input()
    s_list.append(s)
ans = 0
visited = set({})
for h in range(H):
    for w in range(W):
        if s_list[h][w] == '.':
            if str(h) + '_' + str(w) not in visited:
                d = deque()
                d.append([h, w])
                plus = 1
                minus = 0
                while d:
                    i, j = d.pop()
                    visited.add(str(i) + '_' + str(j))
                    for ii, jj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                        if (0 <= (i + ii) < H) & (0 <= (j + jj) < W):
                            if str(i + ii) + '_' + str(j + jj) not in visited:
                                if s_list[i][j] != s_list[i + ii][j + jj]:
                                    d.append([i + ii, j + jj])
                                    visited.add(str(i + ii) + '_' + str(j + jj))
                                    if s_list[i + ii][j + jj] == '.':
                                        plus += 1
                                    else:
                                        minus += 1                                
                ans += plus * minus
print(ans)

Measured memory_bytes: 26492
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main()
{
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    if(s[0]==s[1]&&s[2]==s[3]&&s[1]!=s[2]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii ;
const int mod = 1e9 + 7;

ll binPow(ll x, ll y, ll md = mod){
    ll res = 1;
    x %= mod;
    while(y){
        if(y & 1){
            res = (res * x) % mod;
        }
        y >>= 1;
        x = (x * x) % mod;
    }
    return res;
}

void solve(){
   ll n;
   cin >> n;
   vector<ll> t(n, 0);
   vector<ll> a(n, 0);
   for(ll i = 0; i < n; ++i){
       cin >> t[i] >> a[i];
   }
   for(ll i = 1; i < n; ++i){
       ll k = max((t[i - 1] + t[i] - 1) / t[i], (a[i - 1] + a[i] - 1) / a[i]);
       t[i] *= k;
       a[i] *= k;
   }
   cout << t[n - 1] + a[n - 1] << "\n";
}

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M,Q;
  cin>>N>>M>>Q;
  vector<int>L(M);
  vector<int>R(M);
  vector<int>p(Q);
  vector<int>q(Q);
  for(int i=0;i<M;i++){
    cin>>L.at(i)>>R.at(i);
  }
  for(int i=0;i<Q;i++){
    cin>>p.at(i)>>q.at(i);
  }
  vector<vector<int>>rec1(N,vector<int>(N));
  vector<vector<int>>rec2(N,vector<int>(N));
  for(int i=0;i<M;i++){
    rec1.at(L.at(i)-1).at(R.at(i)-1)=rec1.at(L.at(i)-1).at(R.at(i)-1)+1;
  }
  for(int i=0;i<N;i++){
    rec2.at(i).at(0)=rec1.at(i).at(0);
  }
  for(int i=0;i<N;i++){
    for(int j=1;j<N;j++){
      rec2.at(i).at(j)=rec2.at(i).at(j-1)+rec1.at(i).at(j);
    }
  }
  for(int i=0;i<Q;i++){
    int sum=0;
    for(int j=p.at(i)-1;j<q.at(i);j++){
      sum=sum+rec2.at(j).at(q.at(i)-1);
    }
    cout<<sum<<endl;
  }
}

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

constexpr int inf = 1e9;

int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> c(m), x(n);
        for(int i = 0; i < m; ++i) {
            cin >> c[i];
        }
        for(int i = 0; i < n; ++i) {
            cin >> x[i];
        }

        vector<int> dp(256, inf);
        dp[128] = 0;
        for(int i = 0; i < n; ++i) {
            vector<int> nxt(256, inf);
            for(int j = 0; j <= 255; ++j) {
                for(int k = 0; k < m; ++k) {
                    int nc = max(0, min(255, j + c[k]));
                    nxt[nc] = min(nxt[nc], dp[j] + (x[i] - nc) * (x[i] - nc));
                }
            }
            dp = move(nxt);
        }

        cout << *min_element(begin(dp), end(dp)) << endl;
    }
}



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

int main() {
  int k, a, b;
  scanf("%d", &k);
  scanf("%d %d", &a, &b);

  bool found = false;
  for (int i = a; i <= b; i++)
    if (i % k == 0)
      found = true;

  if (found)
    printf("OK\n");
  else
    printf("NG\n");
  
  return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N, X; cin >> N >> X;
    vec b(N), l(N), u(N);

    int dif = 0;
    pairs p(N);
    REP(i, N){
        cin >> b[i] >> l[i] >> u[i];
        dif += b[i] * l[i];
        p[i] = Pii(u[i] * X - (u[i] - l[i]) * b[i], i);
    }
    Sort(p); Reverse(p);

    vec S(N + 1);
    S[0] = 0;
    REP(i, N) S[i + 1] = S[i] + p[i].f;
    
    int a0 = -1, a1 = N * X;
    while(a1 - a0 > 1){
        int a = (a0 + a1) / 2;
        int n = a / X, k = a % X;
        int D = 0;
        if(k == 0){
            D = S[n];
        }else{
            REP(i, N){
                int tmp = 0;
                int i0 = p[i].s;
                if(k >= b[i0]) tmp = u[i0] * k - (u[i0] - l[i0]) * b[i0];
                else tmp = l[i0] * k;
                if(i < n) tmp += S[n + 1] - p[i].f;
                else tmp += S[n];
                Max(D, tmp);
            }
        }
        if(D >= dif) a1 = a;
        else a0 = a;
    }
    Out(a1);

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N), B(N), C(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) cin >> B[i];
  for (int i = 0; i < N-1; i++) cin >> C[i];

  int res = B[N-1];
  for (int i = 0; i < N-1; i++) {
    res += B[i];
    if (A[i]+1 == A[i+1]) {
      res += C[A[i]-1];
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
def solve(a, b, n):
    return a * min(b - 1, n) / b

assert solve(5, 7, 4) == 2
assert solve(1, 1, 1) == 0
assert solve(11, 10, 9) == 9

(a, b, n) = map(int, raw_input().split())

print solve(a, b, n)



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

int main(){
    int N;cin>>N;
    vector<int> score(N);
    for(int i=0;i<N;i++)cin>>score.at(i);
    sort(score.begin(),score.end(),greater<int>());
    int p=0,ans=0;
    for(int i=0;i<N;i++){
        if(score.at(i)%10!=0)p=score.at(i);
        ans+=score.at(i);
    }
    if(p==0 and ans%10==0)cout<<0<<endl;
    else if(ans%10==0)cout<<ans-p<<endl;
    else cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000002
#define MAX2 10000

int main(){
  unsigned short *A, *B;

  int arr[MAX2+1];
  int n, i, j;
  
  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  for ( i = 0; i <= MAX2; i++ ){
    arr[i] = 0;
  }
  
  for ( i = 0; i < n; i++ ){
    scanf("%hu", &A[i + 1]);
    arr[A[i + 1]]++;
  }

  for ( i = 1; i <= MAX2; i++ ){
    arr[i] = arr[i] + arr[i - 1];
  }
  
  for ( j = 1; j <= n; j++ ){
    B[arr[A[j]]] = A[j];
    arr[A[j]]--;
  }

  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", B[i]);
  }
  
  printf("\n");

  return 0;
}

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

using ll=long long; 

int digit(int n){
	int sum=0;
	while(n>0){
		sum+=n%10;
		n/=10;
	}
	return sum;
}

bool f(int n){
	return n%digit(n)==0;
}

void solve(){
	int n;
	cin>>n;
	if(f(n)){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

signed main(){
	//while(1)
	solve();
}

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

int main(void){
	int k, s, ans = 0;

	cin >> k >> s;

	for (int x = 0; x <= k; x++){
		for (int y = 0; y <= k; y++){
			int z = s - x - y;
			if (z >= 0 && z <= k) ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

	int h, w;
	int i, j;

	while(1){
		scanf("%d %d ", &h, &w);		/* H??¨W?????\??? */

	if(h==0&&w==0)break;				/* H??¨W????????????0??????????????¢?????????????????? */
		for(i=0;i<h;i++){				/* ???H????????? */
			for(j=0;j<w;j++){			/* ?¨?W????????? */
				if(i==0||i==h-1||j==0||j==w-1){		/* ????????¢?????????for????????°????????????if??§?????¨????????????????????????????????? */
					printf("#");		/* if?????¶??????????????????????????? */

				}else{
					printf(".");		/* if?????¶??????????????????????????? */
				}
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 576