akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};

    public  static void main(String[] args)   throws Exception, IOException{        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int n=sc.nextInt();
        int x=sc.nextInt();
        int s[]=sc.nextIntArray(n);
        sort(s);
        
        long dp[][]=new long[100001][n+1];
        for (int i = 1; i <=100000 ; i++) {
        	dp[i][1]=i%s[0];
        }

        for (int i = 2; i <= n ; i++) {
        	for (int t = 1; t <= 100000; t++) {
				dp[t][i]=dp[t][i-1]*(i-1)%mod;
			}
        	for (int t = 1; t <= 100000; t++) {
				dp[t][i]+=dp[t%s[i-1]][i-1];
				dp[t][i]%=mod;
			}        	
		}

        out.println(dp[x][n]);
        out.flush();
    }



    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

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

//class P {
//    int id, d;
//    P(int  id, int d) {
//        this.id=id;
//        this.d=d;
//    }
//}

class P implements Comparable<P>{
    int id,T;
    P(int id, int T) {
        this.id=id;
        this.T=T;
    }
    public int compareTo(P p){
        return id-p.id; //des
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) throws IOException{
    	int r[] = new int[size];
    	for (int i = 0; i < size; i++) {
			r[i] = this.nextInt(); 
		}
    	return r;
    }
    public long[] nextLongArray(int size) throws IOException{
    	long r[] = new long[size];
    	for (int i = 0; i < size; i++) {
			r[i] = this.nextLong(); 
		}
    	return r;
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 234432
let () = print_endline @@ Scanf.scanf "%d %d %d %d %d" (fun n a b c d ->
  Array.init n (fun i -> (i * c - (n - 1 - i) * d, i * d - (n - 1 - i) * c))
  |> Array.to_list
  |> List.exists (fun (min, max) -> min <= abs (a - b) && abs (a - b) <= max)
  |> function true -> "YES" | false -> "NO")

Measured memory_bytes: 32640
#include <iostream>
#include <string>

using namespace std;

int main() {
	string s;
	int n = 0;

	cin >> s;

	for (int i = 0; i < s.size();) {
		if (s.substr(i, 2) == "01" || s.substr(i, 2) == "10") {
			n += 2;
			s.erase(i, 2);
			if (i != 0) i--;
		}
		else {
			i++;
		}
	}
	cout << n << endl;

	return 0;
}

Measured memory_bytes: 512
/*
author: Apoorv Singh
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef vector <int> vi;
typedef pair <int, int> pii;
typedef vector <long long> vll;
typedef pair <long long, long long> pll;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define For(i, a, b) for (long long i = a; i < b; ++i)
#define Forr(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define ll long long 
#define endl "\n"
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;  
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

template <class X>
void printarr(X arr[], int n) 
{
	for (int i = 0; i < n; ++i)
		cout << arr[i] << ' ';
	cout << endl;
}
 
template <class T, class cmp = less<T>> using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
 
ll modulo = 1e9 + 7;

ll fpow(ll a, ll n) 
{
	ll ans = 1;
	while (n) 
	{
		if (n&1) ans = (ans*a)%modulo;
		a = (a*a)%modulo; n = n >> 1;
	}
	return ans;
}

const int M = 3001;
ll dp[M][M][4];
ll grid[M][M];

void solve() 
{
	int r,c,k; cin >> r >> c >> k;
	For(i,0,k)
	{
		int x,y; ll v;
		cin >> x >> y >> v;
		grid[x-1][y-1] = v;
	}	
	// For(i,0,r)
	// {
	// 	For(j,0,c) cout << grid[i][j] << ' ';
	// 	cout << endl;
	// }
	memset(dp,0,sizeof(dp));
	dp[0][0][0] = 0;
	dp[0][0][1] = grid[0][0];
	ll ans = 0;
	For(i,0,r)
	{
		For(j,0,c)
		{
			For(k,0,4)
			{
				if (j+1 < c) 
				{
					dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k]);
					if (k < 3) 
						dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k]+grid[i][j+1]);
				}
				if (i+1 < r)
				{
					dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k]);
					dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][k]+grid[i+1][j]);
				} 
			}
		}
	}
	For(k,0,4) ans = max(ans, dp[r-1][c-1][k]);
	cout << ans << endl;
}

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

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

int main(){
    int a,b;
    cin >> a >> b;
    cout << "a ";
    if(a<b) cout << "< ";
    if(a==b) cout <<"== ";
    if(a>b) cout << "> ";
    cout << "b" << endl;
    
    return 0;
    
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define RREP(i,a,n) for(int i=(a),i##_len=(n);i<i##_len;++i)

int N;
ll ball[50][2]={};
// ll diff[50][50][2]={};
map<pair<ll,ll>,int> diff;

int main() {
  cin >> N;
  ll a;
  REP(i,N) {
    cin >> ball[i][0] >> ball[i][1];
  }
  REP(i,N-1) {
    RREP(j,i+1,N) {
      int x1,x2,y1,y2;
      auto key1 = make_pair(ball[i][0]-ball[j][0], ball[i][1]-ball[j][1]);
      auto key2 = make_pair(ball[j][0]-ball[i][0], ball[j][1]-ball[i][1]);
      if (diff.find(key1) != diff.end()) {
        diff[key1] += 1;
      } else {
        diff[key1] = 1;
      }
      if (diff.find(key2) != diff.end()) {
        diff[key2] += 1;
      } else {
        diff[key2] = 1;
      }
    }
  }
  int maxv = 0;
  for (auto itr : diff) {
    ll v = itr.second;
    if (v > maxv) {
      maxv = v;
    }
  }
  printf("%d\n", N-maxv);
  return 0;
}

Measured memory_bytes: 384
H,W=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(10)]
A=[list(map(int,input().split())) for _ in range(H)]

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k]=min(c[j][k],c[j][i]+c[i][k])

ans=0
for h in range(H):
    for w in range(W):
        if A[h][w]!=-1 and A[h][w]!=1:
            ans+=c[A[h][w]][1]
print(ans)

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

def is_ok(mid):
    s = 0
    for j in range(N):
        if mid < A[j]:
            s += A[j] // mid
    return s <= K

max_A = 10**9 + 1
ng = 0
ok = max_A

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
        
print(ok)

Measured memory_bytes: 104392
use std::io::*;
use std::str::*;

// const MOD: i32 = 1000000007;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let a: usize = read().unwrap();
    let b: usize = read().unwrap();
    let c: usize = read().unwrap();
    let d: usize = read().unwrap();

    println!("{}",
             std::cmp::min(a, b) +
             std::cmp::min(c, d)
             );
}


Measured memory_bytes: 4352
S = input()
Q = int(input())
rev = False
ad = ''
for _ in range(Q):
    A = input().split()
    if len(A) == 1:
        rev ^= True
    else :
        if (A[1] == '1' and rev == False) or (A[1] == '2' and rev == True):
            ad += A[2]
        else :
            S += A[2]

ans = (ad[::-1] + S)[::1 - 2 * rev]
print(ans)


Measured memory_bytes: 4468
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int x = in.nextInt();
      	
      	int numberof500 = x/500;
        int remainder = x%500;
        int numberof5 = remainder/5;
      	long ans = 1000*numberof500+5*numberof5;
      
      System.out.println(ans);
	}
}


Measured memory_bytes: 21844
while True:
    n, x = [int(arg) for arg in input().split()]
    if n == 0 and x == 0:
        break
    if x < 6:
        print(0)
        continue

    count = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                continue
            elif i + j >= x:
                continue
            for k in range(1, n + 1):
                if i != j and j != k and i != k and i + j + k == x:
                    count += 1
    print(int(count / 6))



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repd(i,a,b) for (int i = (a); i < (b); i++)
#define INF LLONG_MAX
#define mod 1000000007
typedef long long ll;
ll gcd(ll a, ll b)//最大公約数
{
  return b != 0 ? gcd(b, a % b) : a;
}
int main(void)
{
	ll A, B, C;
	cin >> A >> B;
	C = (A*B)/gcd(A, B);
	cout << C << endl;
	return 0;
}


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

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

ll get_score(const ll& p, const std::vector<ll>& X) {
  ll sum {};
  for (const auto& e : X) {
    sum += (e - p)*(e - p);
  }
  return sum;
}

int main() {
  ll N;
  std::cin >> N;
  std::vector<ll> X(N);
  rep(i,N) std::cin >> X[i];
  std::sort(X.begin(), X.end());
  ll left = 1, right = 100;
  ll left_score = get_score(left, X);
  ll right_score = get_score(right, X);
  for (ll mid = (left+right)/2;left+1<right;mid = (left+right)/2) {
    ll mid_score = get_score(mid, X);
    if (left_score < right_score) {
      right = mid;
      right_score = mid_score;
    } else {
      left = mid;
      left_score = mid_score;
    }
  }
  if (left_score < right_score) std::cout << left_score << '\n';
  else std::cout << right_score << '\n';
}


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;
//const i64 inf = 1'000'000'000'000'000'000ll + 7;
//const i64 inf = 1'000'000'007;

const long double eps = 1e-8;

const i64 MAXN = 100'000 + 6;

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    i64 a, b, h, m;
    cin >> a >> b >> h >> m;

    auto pi = acos(-1.0);

    double ha = (2 * pi * (h * 60 + m) / (12 * 60));
    double hx = cos(ha) * a;
    double hy = sin(ha) * a;

    double ma = (2 * pi * m / 60);
    double mx = cos(ma) * b;
    double my = sin(ma) * b;

    double R = sqrt(sqr(hx - mx) + sqr(hy - my));
    cout << R << endl;

    
    return 0;
}

Measured memory_bytes: 4084
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

typedef long long int ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vivi vector<vi>
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
int arrayMax(int a[], const int N){
    int maxv = 0;
    rep(i, N)maxv = max(a[i], maxv);
    return maxv;
}
/* -- template -- */
double dp[3000][3000]; //dp[i][j] : i枚目までのコインを投げて，表がj枚出る確率
int main(){
    int N; cin >> N;
    double p[N]; rep(i, N)cin >> p[i];
    dp[0][0] = 1;
    for(int i = 0;i < N;++i){
        for(int j = 0;j <= i + 1;++j){
            dp[i + 1][j] = dp[i][j] * (1.0 - p[i]);
            if(j - 1 >= 0)dp[i + 1][j] += dp[i][j - 1] * p[i];
        }
    }
    double sum = 0.0;
    for(int i = 1 + N / 2; i <= N; ++i){
        sum += dp[N][i];
    }
    printf("%.12f\n", sum);
}


Measured memory_bytes: 68864
//-----------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
 
#define cinsc ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOR(i,k,n)  for(int64 i=k;i<(int)n;i++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define SQ(x) ((x)*(x))
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
 
//ONLINE_JUDGE   LOCAL
//-----------------------------------------------------------------------------

int64 powr(int64 x,int64 y,int64 p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0;
    while (y > 0){   
        if (y & 1)  
            res = (res*x) % p;   
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
} 
 
void  in_o(){
#ifndef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    cinsc;
}

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

int main(){
    //in_o();
    int k;
    cin >> k;
    int64 ans = 0;
    for(int i = 1; i <= k; ++i)
        for(int j = 1; j <= k; ++j)
            for(int x = 1; x <= k; ++x)
                ans += __gcd(__gcd(i, j), x);
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 3496
//-------------
//include
//-------------
#include <map>
#include <list>
#include <cmath>
#include <vector>
#include <string>
#include <cctype>
#include <random>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
//-------------
//typedef
//-------------
typedef long long LL;
typedef  vector<int> VI;
typedef  pair<int, int> PII;
typedef  vector<int, int> VII;
typedef  map<string, int> MSI;
//-------------
//utillty
//-------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MK make_pair
#define PB push_back
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(a) cout<<a<<endl
//-------------
//repetition
//-------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//-------------
//debug
//-------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumpl(c) REP(i,SZ(c))cerr<<#c<<i<<"="<<(c[i])<<endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const int MOD = 1000000007;
int main()
{
	int a;
	cin >> a;
	if (a/10==9||a%10==9)
	{
		COUT("Yes");
	}
	else
	{
		COUT("No");
	}
#ifdef _DEBUG
	while(1);
#endif // _DEBUG

	return 0;
}

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

int main() {
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < s.size()/2; i++) {
    if (s[i] != s[s.size() - 1 - i]) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int w,h,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
string a[51];
bool used[51][51];
int dfs(int y,int x){
  if(y==-1||y==h||x==-1||x==w||used[y][x])return 0;
  if(a[y][x]=='B')return 1;
  if(a[y][x]=='W')return 2;
  used[y][x]=1;
  int pr=0;
  for(int t,i=0;i<4;i++){
    t=dfs(y+dy[i],x+dx[i]);
    if(!pr)pr=t;
    else if(t&&pr!=t)pr=3;
  }
  return pr;
}

int main(){
  while(cin>>w>>h,w){
    for(int i=0;i<h;i++)cin>>a[i];
    int ans[5]={};
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){  
	memset(used,0,sizeof(used));
	if(a[i][j]=='.')ans[dfs(i,j)]++;
      }
    cout<<ans[1]<<" "<<ans[2]<<endl;
  }
  return 0;
}

Measured memory_bytes: 3124
import java.util.*;
class Main {
  static Scanner sc = new Scanner(System.in);
  public static void main(String[] args) {
    int A=sc.nextInt(),B=sc.nextInt();
    for(int i=1;i<=3;i++){
      if(i!=A&&i!=B){
        System.out.println(i);
        break;
      }
    }
  }
}

Measured memory_bytes: 35588
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define all(x) (x.begin(),x.end())
#define pii pair<int,int> 
#define vi vector<int> 
#define FOR(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define fi first
#define se second
using namespace std;
void solve()
{
	string s,t;
	cin>>s>>t;
	int ans=MOD;
	for(int i=0;i<=s.length()-t.length();i++)
	{
		int x=0;
		for(int j=0;j<t.length();j++)
		{
			if(s[i+j]!=t[j])
			x++;
		}
		ans=min(ans,x);
	}
	
	cout<<ans<<endl;
}
int32_t main()
{
	int t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}
// Problem : B - Substring
// Contest : AtCoder - AtCoder Beginner Contest 177
// URL : https://atcoder.jp/contests/abc177/tasks/abc177_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)



Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

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

	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		if (s[i] == 'R') {
			int r = i;
			while (r + 1 < (int)s.size() && s[r + 1] == 'R') {
				r++;
			}
			ans = max(ans, r - i + 1);
			i = r;
		}
	}
	cout << ans << '\n';
}

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

using namespace std;

#define ll long long
#define ld long double

#define P pair<ll, ll>
#define FOR(i, n, m) for (ll i = n; i < (ll)m; i++)
#define FORr(i, m, n) for (ll i = n; i >= (ll)m; i--)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define sortAl(v) sort(v.begin(), v.end())
#define sortAlr(v)                                                             \
  sort(v.begin(), v.end());                                                    \
  reverse(v.begin(), v.end())
#define cout(n) cout << fixed << setprecision(n)

#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define all(v) v.begin(), v.end()
template <class T> inline void chmax(T &a, T b) { a = std::max(a, b); }
template <class T> inline void chmin(T &a, T b) { a = std::min(a, b); }

#define mod (int)(1e9 + 7)
#define INF LLONG_MAX

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

  ll N, K;
  cin >> N >> K;

  if (N % K == 0) {
    cout << 0 << endl;
  } else {
    cout << 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, step = 1;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++) {
    cin >> d.at(i);
  }
  sort(d.begin(), d.end());
  for (int j = 1; j < N; j++) {
    if (d.at(j - 1) < d.at(j)) {
      step++;
    }
  }
  cout << step << endl;
}

Measured memory_bytes: 3616
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int main(){
  int N;
  cin >> N;

  map<ll,ll> mp;
  ll max_d = 0;
  for(int i = 0;i < N;i++){
    ll d;
    cin >> d;
    if(i == 0 && d != 0){
      cout << 0 << endl;
      return 0;
    }
    max_d = max(d,max_d);
    mp[d]++;
  }

  if(mp[0] != 1){
    cout << 0 << endl;
    return 0;
  }


  ll ans = 1;
  for(ll i = 1;i <= max_d;i++){//深さ
    ll now_ = 1;
    for(ll j = 1;j <= mp[i];j++){//葉の数
      now_ *= mp[i-1];
      now_ %= MOD;
    }
    ans *= now_;
    ans %= MOD;
  }

  cout << ans << endl;
}


Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;

int main(){
    int r;
    cin >> r;
    cout << r*r << endl;
    return 0;
}


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

typedef long long ll;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

struct SegmentTree {
private:
    int n;
    vector<ll> node;
public:
    SegmentTree(vector<ll> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2*n-1,0);
        for (int i = 0;i < sz;++i) node[i+n-1] = v[i];
        for (int i = n-2;i >= 0;--i) node[i] = max(node[2*i+1],node[2*i+2]);
    }
    void update(int x,ll val) {
        x += (n-1);
        node[x] = val;
        while (x > 0) {
            x = (x-1)/2;
            node[x] = max(node[2*x+1],node[2*x+2]);
        }
    }

    ll getmax(int a,int b,int k = 0,int l = 0,int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return node[k];
        ll vl = getmax(a,b,2*k+1,l,(l+r)/2);
        ll vr = getmax(a,b,2*k+2,(l+r)/2,r);
        return max(vl,vr);
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> h(n),a(n),b(n);
    vector<ll> dp(n,0);
    SegmentTree seg(vector<ll>(n,0));
    for (int i = 0;i < n;++i) cin >> h[i];
    for (int i = 0;i < n;++i) cin >> a[i];
    for (int i = 0;i < n;++i) b[h[i]-1] = i;

    for (int i = 0;i < n;++i) {
        dp[i] = seg.getmax(0,b[i])+a[b[i]];
        seg.update(b[i],dp[i]);
    }
    cout << *max_element(dp.begin(),dp.end()) << endl;
    return 0;
}

Measured memory_bytes: 9856
from collections import defaultdict as dd

d=dd(int)
n,m=map(int,input().split())
l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]

o=sorted(l,key=lambda x:x[2])
for i,j in enumerate(o):
  d[j[1]]+=1
  o[i][3]=d[j[1]]

for i in sorted(o):
  print('{0:06d}'.format(i[1])+'{0:06d}'.format(i[3]))

Measured memory_bytes: 82388
#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

    set<int> s;
    ll ans = 0;
    for (int x = n - 1; x >= 0; --x) {
        int i = idx[x];
        ll c = 0;

        { // calc c
            s.insert(i);
            vector<int> l(2, -1);
            vector<int> r(2, n);
            {// calc l
                auto it = s.find(i);
                for (int j = 0; j < 2; j++) {
                    if (it == s.begin()) break;
                    --it;
                    l[j] = *it;
                }
            }
            {// calc r
                auto it = s.find(i);
                for (int j = 0; j < 2; j++) {
                    ++it;
                    if (it == s.end()) break;
                    r[j] = *it;
                }
            }

            vector<int> ls(2);
            ls[0] = i - l[0];
            ls[1] = l[0] - l[1];
            vector<int> rs(2);
            rs[0] = r[0] - i;
            rs[1] = r[1] - r[0];
            c = (ll) ls[0] * rs[1] + (ll) ls[1] * rs[0];
        }

        ans += c * (x + 1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 5760
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M = lr()
    H = lr()
    road = [-1]*N
    for i in range(M):
        a, b = lr()
        mab = max(H[a-1], H[b-1])
        if H[a-1] == H[b-1]:
            road[a-1] = float('inf')
            road[b-1] = float('inf')
        else:
            road[a-1] = max(mab, road[a-1])
            road[b-1] = max(mab, road[b-1])
    ans = 0
    for i in range(N):
        if road[i] == H[i] or road[i] == -1:
            ans += 1
    print(ans)
resolve()

Measured memory_bytes: 84864
// tsukasa_diary's programing contest code template
#include <bits/stdc++.h>
using namespace std;
#define TSUKASA_DIARY_S_TEMPLATE
// define
#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) int((a).size())
#define cauto const auto
// typedef
typedef long long lint;
typedef double Double;
typedef pair< int, int > pii;
template< typename T > using Vec = vector< T >;
template< typename T > using Matrix = Vec< Vec< T > >;
template< typename T > using USet = unordered_set< T >;
template< typename T, class C > using MyUSet = unordered_set< T, C >;
template< typename T, typename F > using UMap = unordered_map< T, F >;
template< typename T, typename F, class C > using MyUMap = unordered_map< T, F, C >;
// hash
class PiiHash { public: size_t operator () (const pii& p) const { return (p.first << 16) | p.second; } };
// popcount
inline int POPCNT(int x) { return __builtin_popcount(x); }
inline int POPCNT(lint x) { return __builtin_popcount(x); }
// inf
const int iINF = 1L << 30;
const lint lINF = 1LL << 60;
// eps
const Double EPS = 1e-9;
const Double PI = acos(-1);
// inrange
template< typename T >
inline bool in_range(T v, T mi, T mx) { return mi <= v && v < mx; }
template< typename T >
inline bool in_range(T x, T y, T W, T H) { return in_range(x,0,W) && in_range(y,0,H); }
// neighbor clockwise
const int DX[4] = {0,1,0,-1}, DY[4] = {-1,0,1,0};
const int DX_[8] = {0,1,1,1,0,-1,-1,-1}, DY_[8] = {-1,-1,0,1,1,1,0,-1};
// variable update
template< typename T > inline void modAdd(T& a, T b, T mod) { a = (a + b) % mod; }
template< typename T > inline void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > inline void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > inline void maxUpdate(T& a, T b) { a = max(a, b); }
// converter
template< typename F, typename T >
inline void convert(F& from, T& to) {
	stringstream ss;
	ss << from; ss >> to;
}





int main() {
	int N;
	cin >> N;
	
	vector< lint > a(N);
	for_(i,0,N) cin >> a[i];
	
	lint sum = accumulate(a.begin(), a.end(), lint());
	
	lint ans = abs(a[0] - (sum - a[0])), x = a[0];
	for_(i,1,N-1) {
		x += a[i];
		ans = min(ans, abs(x - (sum - x)));
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<typename T>
T gcd(T x, T y) {
    if (y==0) return x;
    return gcd(y, x % y);
}

template<typename T>
T lcm(T x, T y) {
    T g = gcd(x, y);
    return x / g * y;
}

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

    sort(all(a));
    ll g = abs(x - a[0]);
    for (int i = 1; i < n; i++) {
        g = gcd(g, abs(x - a[i]));
    }
    cout << g << endl;
}


Measured memory_bytes: 1024
// inputに入力データ全体が入る
function Main(input) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.split("\n");
  tmp0 = input[0].split(" ");
  N = Number(tmp0[0]);
  K = Number(tmp0[1]);

  ans = 0;
  for (var i = 1; i <= N; i++) {
    if (i < K) {
      multiplier = Math.ceil(Math.log2(Number(K / i)));
      ans += (1 / N) * Math.pow(1 / 2, multiplier);
    } else {
      ans += 1 / N;
    }
  }
  console.log(ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
// Main("3 10\n");


Measured memory_bytes: 9236
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


from itertools import permutations
from math import sqrt
import heapq
while 1:
    N = int(input())
    if N==0:
        break
    uf = UnionFind(N)
    Vs = [list(map(float, input().split())) for _ in range(N)]
    lis = [i for i in range(N)]
    Edges = []
    for a, b in permutations(lis, 2):
        x1, y1, z1, r1 = Vs[a]
        x2, y2, z2, r2 = Vs[b]
        d = max(0, sqrt((x1-x2)**2+(y1-y2)**2+(z1-z2)**2)-r1-r2)
        Edges.append((d, a, b))
    heapq.heapify(Edges)
    ans = 0
    while Edges:
        d, a, b = heapq.heappop(Edges)
        if not uf.same(a, b):
            ans += d
            uf.union(a, b)
    print('{:.3f}'.format(ans))


Measured memory_bytes: 6880
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    s = input()
    k = int(input())

    ichi = 0
    for i in range(len(s)):
        if s[i] == '1':
            ichi += 1
        else:
            break
    if ichi >= k:
        print(1)
    else:
        print(s[ichi])



if __name__ == '__main__':
  main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

#define fr(i,b,e) for(int i=(b); i!=(e); ++i)
#define rep(i,e) for(int i=0; i!=(e); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long int li;
typedef long long ll;
using graph = vector<vector<int>>;
using edgedp = vector<vector<pair<int,ll>>>;
constexpr int INF=1000000;
//constexpr int MOD=998244353;
constexpr int MOD=1e9+7;



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

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

    double sum=accumulate(all(a),0);
    sum=sum/4.0;
    sum=sum/(double) m;

    sort(all(a));
    //cout << a[n-m] << "\n"  ;
    if(a[n-m] < sum){
        cout << "No" <<"\n";
    }else{
        cout << "Yes" << "\n";
    }
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
  int x, y;
  int a, b;
  cin >> x >> y;
  bool flag = true;
  if((y-2*x)%2!=0)flag = false;
  if((4*x-y)%2!=0)flag = false;
  a = (y-2*x)/2;
  b = (4*x-y)/2;
  if(a<0)flag = false;
  if(b<0)flag = false;

  if(flag)cout << "Yes";
  else cout << "No";

  return 0;
}


Measured memory_bytes: 3636
#ifdef LOCAL_BUILD
#include "pch.h"
#define DLOG(msg) cout << "#" << __LINE__ << ":" << msg << endl;
#define DLOG_V(var) \
  cout << "#" << __LINE__ << ":" << #var << " : " << var << endl;
#else
#include <bits/stdc++.h>
#define DLOG(msg)
#define DLOG_V(var)
#endif
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> edges(n, vector<pair<int, int>>());
  for (int i = 0; i < n; ++i) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      int v, c;
      cin >> v >> c;
      edges[i].push_back(make_pair(v, c));
    }
  }
  int count = 1;
  constexpr auto not_yet = numeric_limits<int>::max();
  vector<int> costs(n, not_yet);
  costs[0] = 0;
  auto cmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
    return lhs.second > rhs.second;
  };
  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
  for (auto&& edge : edges[0]) {
    q.push(edge);
  }
  while (true) {
    auto state = q.top();
    q.pop();
    if (costs[state.first] > state.second) {
      assert(costs[state.first] == not_yet);
      for (auto&& edge : edges[state.first]) {
        q.push(make_pair(edge.first, edge.second + state.second));
      }
      costs[state.first] = state.second;
      if (++count == n) {
        break;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << i << " " << costs[i] << endl;
  }
}

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

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

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const double pi=acos(-1);





int main() 
{
  int N; cin>>N;
  vector<int> A(N);
  rep(i,N)
  {
    cin>>A.at(i);
  }
  vector<bool> vec(0);
  rep(i,N)
  {
    if(i==0) {continue;}
    if(A.at(i)>A.at(i-1)) {vec.push_back(true);}
    if(A.at(i)<A.at(i-1)) {vec.push_back(false);}
  }
  int ans=0;
  rep(i,vec.size())
  {
    if(i==0) {continue;}
    if(vec.at(i)!=vec.at(i-1)) {ans++; i++;}
  }
  cout<<ans+1<<endl;
  return 0;
}


Measured memory_bytes: 768
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>


using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
int main() {
  int N;
  cin >> N;
  switch(N%10){
  case 3:
    cout << "bon" << endl;
    break;
  case 0:
  case 1:
  case 6:
  case 8:
      cout << "pon" << endl;;
      break;
  default :
    cout << "hon" << endl;
  }

}

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

const int N = 1e5 + 10;

vector<int> a[N];
long long dp[N][3];

void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = INT_MIN;
        }
    }
}

int main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        a[i].resize(3);
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    init();
    dp[1][0] = a[1][0];
    dp[1][1] = a[1][1];
    dp[1][2] = a[1][2];
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (j != k) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
                }
            }
        }
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << '\n';                    
}

Measured memory_bytes: 8064
#include <iostream>
#include <cstdint>
#include <string>

int main()
{
    int32_t n;
    int32_t m;
    int32_t a = 1;
    int32_t b = 1;
    std::string s;

    std::cin >> n;

    if (n == 0) {
        s.push_back('0');
    } else {
        m = 0;
        while (m != n) {
            if ((n & a) != (m & a)) {
                m += b;
                s.push_back('1');
            } else {
                s.push_back('0');
            }

            a *= 2;
            b *= -2;
        }
    }

    std::string o(s.rbegin(), s.rend());
    std::cout << o << std::endl;

    return 0;
}


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

input_1 = list(map(int,input().split()))

input_converted = []

try:
    for i in range(N // 2 + 1):
        input_converted.append(input_1[2*i])
except:
    pass

ans = 0

for i in input_converted:
    if i % 2 == 1:
        ans += 1
        
print(ans)

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

#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(long long i=0;i<(n);i++)
#define FOR(i,a,b) for(long long i=(a);i<=(b);i++)

int main() {
  int N, M;
  cin >> N >> M;
  int K, A;
  map<int, int> m;
  REP(i, N) {
    cin >> K;
    REP(j, K) {
      cin >> A;
      if(m.find(A) == m.end()) {
        m[A] = 1;
      } else {
        m[A] += 1;
      }
    }
  }
  int ans = 0;
  map<int, int>::const_iterator it;
  for(it = m.begin(); it != m.end(); it++) {
    if(it->second == N) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define PP pair<P,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF INT_MAX/3
#define eps LDBL_EPSILON
#define mod (int)(1000000007)
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
signed main(){
	string s;
	cin>>s;
	sort(s.begin(),s.end());
	if(s[0]==s[1]&&s[2]==s[3]&&s[1]!=s[2])puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e5+10;

const ll is_query = -(1LL<<62);
struct Line {
  ll m, b;
  mutable function<const Line*()> succ;
  bool operator<(const Line& rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const Line* s = succ();
    if (!s) return 0;
    ll x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
// will maintain upper hull for maximum
struct HullDynamic : public multiset<Line> {
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    // could overflow
    return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
  }
  void insert_line(ll m, ll b) { m = -m; b = -b; // for lower hull
    auto y = insert({ m, b });
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) { erase(y); return; }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  ll eval(ll x) {
    auto l = *lower_bound((Line) { x, is_query });
    return -(l.m * x + l.b); // for lower hull
  }
};

ll sq(ll x) { return x*x; }

int n;
ll c;
// dp[i] = min cost to reach stone i
HullDynamic dp;
int h[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> c;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  dp.insert_line(-2*h[0], sq(h[0]));
  ll cur;
  for (int i = 1; i < n; i++) {
    cur = dp.eval(h[i]) + sq(h[i]) + c;
    dp.insert_line(-2*h[i], cur + sq(h[i]));
  }
  cout << cur << nl;
  return 0;
}


Measured memory_bytes: 19840
def make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
                    
    return divisors
    
n = int(input())
# print(f"{n}")

ans = 0
for i in range(1, n + 1, 2):
    divisors = make_divisors(i)
    if len(divisors) == 8:
        # print(f"{i} : {divisors}")
        ans += 1
print(ans)

Measured memory_bytes: 9336
//Prashant Tyagi
using namespace std;
#include <bits/stdc++.h>
#define TRACE
#ifdef TRACE
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define TR(...)
#endif
typedef  long long                     LL;
typedef  vector < int >                VI;
typedef  pair< int, int >              II;
typedef  vector < II >                 VII;
#define SI(x)                          scanf ("%d", &x)
#define SLL(x)                         scanf ("%lld", &x)
#define PI(x)                          printf ("%d\n", x)
#define PLL(x)                         printf ("%lld\n", x)
#define MOD                            98765431
#define PB                             push_back
#define MP                             make_pair
#define ALL(v)                         v.begin(), v.end()
#define VIF(x,V)                       for(int x:V)
#define FILL(a,b)                      memset(a,b,sizeof(a))
#define REP(i,j,n)                     for(int i=j;i<n;i++)
#define FLD(i,j,n)                     for(int i=n-1;i>=j;i--)
#define F                              first  
#define S                              second
#define fast_io                        ios_base::sync_with_stdio(false);cin.tie(NULL)

int main ()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n;SI(n);
	int x,y,z;
	x=y=z=0;
	REP(i,0,n){
		int a;SI(a);
		if(a%4==0)y++;
		else if(a%2==1)x++;
		else z++;
	}
	if(y>=x){
		cout<<"Yes"<<endl;
	}else if(x-y==1&&z==0){
		cout<<"Yes"<<endl;
	}else {
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

h.sort()

mi = 10 ** 9
temp = 10 ** 9

for i in range(N - K + 1):
    temp = h[i + K - 1] - h[i]
    if temp < mi:
        mi = temp

print(mi)


Measured memory_bytes: 7384
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    String s = sc.next();
    int b = sc.nextInt();

    if(s.equals("+")){
      System.out.println(a+b);
    }else{
      System.out.println(a-b);
    }
  }
}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/


int main(void) {
  ll i, j, k;
  ll a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  ll K;
  cin >> K;
  pt(a[K-1]);
  
  
  
  
  
  
}



Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int m,f,r;
		
		while(true) {
			m = sc.nextInt();
			f = sc.nextInt();
			r = sc.nextInt();
			
			if (m==-1 && f==-1 && r==-1) {
				break;
			}
			if (m==-1 || f==-1) {
				System.out.println("F");
			}else if(m+f < 30) {
				System.out.println("F");
			}else if(m+f < 50 && r < 50) {
				System.out.println("D");
			}else if(m+f < 65) {
				System.out.println("C");
			}else if(m+f < 80) {
				System.out.println("B");
			}else {
				System.out.println("A");
			}
			
		}
		
		
	}

}


Measured memory_bytes: 26264
import sys
N = int(input())
Xl = list(map(int, input().split()))
Xl.sort()
minx = Xl[0]
maxx = Xl[-1]
minsum = sys.maxsize
for i in range(minx, maxx+1):
    sumd = 0
    for x in Xl:
        sumd += (x - i)**2
    if sumd < minsum:
        minsum = sumd
print(minsum)


Measured memory_bytes: 3060
/**
     **author : _KMS_
     **created : 08-12-2019
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =1e6+1,MOD=1e9+7;
typedef long long LL;
bool vis[M];
long long Arr[M];
long long bigmod ( long long a, long long p, long long m )
{
    long long res =1;
    long long x = a;

    while ( p )
    {
        if ( p & 1 ) //p is odd
        {
            res = ( res * x )%m;
        }
        x = ( x * x )%m;
        p = p >> 1;
    }

    return res%m;
}
int main()
{
    ios::sync_with_stdio(false);//ISHWAR
    cin.tie(0);//Tourist_Twin
    long long n,i,result=0;
    cin>>n;
    for(i=0; i<n; i++)
        cin>>Arr[i];
    for(i=0; i<=60; i++)
    {
        long long one=0,zero=0,j;
        for(j=0; j<n; j++)
        {
            (Arr[j]%2)?one++:zero++;
            Arr[j]/=2;
        }
        zero=zero%MOD;
        one=one%MOD;
        long long sum=(((zero*one)%MOD)*bigmod(2,i,MOD))%MOD;
        result=((result%MOD)+(sum%MOD))%MOD;
    }
    cout<<result%MOD<<endl;

    return 0;
}


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

int gcd(int X,int Y){
  while(X*Y!=0){
    if(X>Y){
      X=X%Y;
    }else{
      Y=Y%X;
    }
  }
  return X+Y;
}

int main(){
  int n,s,i,j,k;
  cin >> n;
  s=0;
  vector<vector<int>> g(n+1,vector<int>(n+1,0));
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      g.at(i).at(j)=gcd(i,j);
    }
  }
  
  for(k=1;k<=n;k++){
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
        s=s+gcd(g.at(i).at(j),k);
      }
    }
  }
  
  cout << s << endl;
}

Measured memory_bytes: 3800
#include <iostream>
#include <math.h>
using namespace std;

//t=1が単利２がふくり

double tanri(int r,int y)
{
	return 1.0+(double)y*(double)r/100.0;
}

double hukuri(int r,int y)
{
	return pow(1.0+(double)r/100.0,y);
}

int main(void)
{
	int n,y,b,r,t;
	double max;
	int maxnum;

	while(1)
	{
		cin >> n;
		if(n==0)
			return 0;
		cin >> y;

		max = -1;
		maxnum = -1;
		for(int i=0;i<n;++i)
		{
			cin >> b >> r >> t;
			if(t == 1)
			{
				double d = tanri(r,y);
				if(d > max)
				{
					max = d;
					maxnum = b;
				}
			}
			if(t==2)
			{
				double d = hukuri(r,y);
				if(d > max)
				{
					max = d;
					maxnum = b;
				}

			}
		}
		cout << maxnum << endl;
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
b = list(map(int,input().split()))
ans = []

for j in range(N):
  n = list(range(1,len(b)+1))
  n_tmp = [x - y for (x, y) in zip(n,b)]
  if min(n_tmp) >= 0:
    tmp = sorted(list(set(b)),reverse = True)
    for i in tmp:
      if i == b[i-1]:
        ans.insert(0,b[i-1])
        b.pop(i-1)
        break
  else:
    print('-1')
    break
else:
  for k in range(N):
    print(ans[k])

Measured memory_bytes: 3064