akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  string N;
  cin >> N;
  bool seven = false;
  for (int i=0; i<3; i++) {
    if (N[i]=='7') {
      seven = true;
      break;
    }
  }
  if (seven) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 1000000000 + 7;

int main(){
  cout << setprecision(10);
  string s,t;
  cin >> s >> t;
  int ret = 0;
  for(int i = 0; i < s.size(); i++){
    if(s[i] != t[i]){
      ret++;
    }

  }
  cout << ret << endl;
}


Measured memory_bytes: 3912
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

int main() {
	int n, max, min;
	long long sum;
	(void)scanf("%d", &n);
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		(void)scanf("%d", &v[i]);
	}
	max = *max_element(v.begin(), v.end());
	min = *min_element(v.begin(), v.end());
	sum = accumulate(v.begin(), v.end(), 0ll);
	printf("%d %d %lld\n", min, max, sum);
	return 0;
}


Measured memory_bytes: 2760
N=input()
n=len(N)
x=0
flag=0
#print(N)
M=[0]*(n+1)
for i in range(n):
  M[i]=int(N[n-1-i])
#print(M)
for i in range(n+1):
  
  m=M[i]
  if m==5:
    x+=5
    flag=1
  elif m<5:
    x+=m
    flag=0
  else:
    x+=(10-m)
    flag=2
  if flag==2:
    M[i+1]+=1
  elif flag==1:
    if M[i+1]>=5:
      M[i+1]+=1
print(x)

Measured memory_bytes: 11972
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();

    let x: u64 = buf.trim().parse().unwrap();
    let mut n: u64 = 100;
    let mut ans: u64 = 0;

    while n < x {
        n = ((n as f64) * 1.01f64) as u64;
        ans += 1;
    }

    println!("{}", ans)
}


Measured memory_bytes: 2128
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = in.nextIntArray(n);
            int[] b = a.clone();
            Arrays.sort(b);
            int pos = n / 2 - 1;
            for (int i = 0; i < n; i++) {
                if (a[i] > b[pos]) {
                    out.println(b[(n - 1) / 2]);
                } else if (a[i] <= b[pos]) {
                    out.println(b[(n - 1) / 2 + 1]);
                }
            }
        }

    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

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

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

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

    }
}



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

int main(){
  int s1,s2;
  while(cin >> s1 >> s2,s1||s2){
    int ans = 0, val = s1+s2;

    for(int i=1;i<5;i++){
      cin >> s1 >> s2;
      if(val < s1 + s2){
	ans = i;
	val = s1 + s2;
      }
    }
    cout << (char)('A'+ans) << " " << val << endl;
  }
}

Measured memory_bytes: 1160
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// x ** n % mods を求める
pub fn mod_pow(x: i64, n: i64, mods: i64) -> i64 {
    if n == 0 {
        return 1;
    }
    let mut res = mod_pow(x * x % mods, n / 2, mods);
    if n % 2 == 1 {
        res = res * x % mods;
    }
    return res;
}

// (1/n) % mods を求める
pub fn mod_inv(n: i64, mods: i64) -> i64 {
    return mod_pow(n, mods-2, mods);
}

// nCk % mods を求める
pub fn mod_comb(n: i64, k: i64, mods: i64) -> i64 {
    let sum1 = (n-k+1..n+1).fold(1, |ac, x| ac * x % mods);
    let sum2 = (1..k+1).fold(1, |ac, x| ac * x % mods);
    return sum1 * mod_inv(sum2, mods) % mods;
}


fn main() {
    input!{
        n: usize,
    }
    if n % 2 == 0 {
        println!("{}", n / 2);
    }
    else {
        println!("{}", n / 2 + 1);
    }
}


Measured memory_bytes: 4352
n = gets.to_i
array = gets.split.map(&:to_i)
total = 0

num = 0
while num < n do
    for n in 1..n
    bimi = array[num].to_i * array[num + n].to_i 
    total = total + bimi
    end
    num = num + 1
end

puts total

Measured memory_bytes: 1788
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N = int(readline())
    A, B = map(int, readline().split())
    P = list(map(int, readline().split()))

    cnt = [0] * 3

    for x in P:
        if x <= A:
            cnt[0] += 1
        elif x <= B:
            cnt[1] += 1
        else:
            cnt[2] += 1

    print(min(cnt))


if __name__ == '__main__':
    main()


Measured memory_bytes: 61720
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int H = sc.nextInt();
		int W = sc.nextInt();

		int[][] a = new int[H][W];

		for (int i = 0; i < H;) {
			String s = sc.next();
			for (int j = 0; j < W; j++) {
				a[i][j] = s.charAt(j) == '.' ? 0 : 1;
			}
			i++;
		}

		boolean[] outputRow = new boolean[H];
		boolean[] outputCol = new boolean[W];

		for (int i = 0; i < H; i++) {
			outputRow[i] = false;
			for (int j = 0; j < W; j++) {
				if (a[i][j] == 1) {
					outputRow[i] = true;
				}
			}
		}

		for (int j = 0; j < W; j++) {
			outputCol[j] = false;
			for (int i = 0; i < H; i++) {
				if (a[i][j] == 1) {
					outputCol[j] = true;
				}
			}
		}

		for (int i = 0; i < H; i++) {
			if (!outputRow[i]) {
				continue;
			}
			for (int j = 0; j < W; j++) {
				if (outputCol[j]) {
					out.print(a[i][j] == 0 ? "." : "#");
				}
			}
			out.println();
		}

		sc.close();

	}

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

}


Measured memory_bytes: 28408
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>

using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::make_pair;
using std::vector;
using std::queue;
using std::deque;
using std::priority_queue;
using std::next_permutation;
//using std::iota;
using std::sort;
using std::greater;
using std::max;
using std::min;

using lli = long long int;
using ulli = unsigned long long int;

#define INF 999999999;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

lli Lf, Ls, N, ans;

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

	cin >> N;
	Lf = 2; Ls = 1;
	if(N == 1) cout << 1;
	else{
		for(int i = 1; i < N; i++){
			ans = Lf+Ls;
			Lf = Ls;
			Ls = ans;
		}
		cout << ans;
	}

	return 0;
}


Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[i] != L[j] and L[j] != L[k] and L[i] != L[k] and L[i] + L[j] > L[k] and L[i] + L[k] > L[j] and L[j] + L[k] > L[i]:
                ans += 1
print(ans)


Measured memory_bytes: 73784
#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6;
vector <int> adj[mxn];
int visited[mxn];
long long dist[mxn];
queue <int> q;
void bfs(int start)
{
    q.push(start);
    visited[start]=1;
    dist[start]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
       // cout<<u<<' ';
        for(int i=0;i<adj[u].size();i++)
        {
           int v= adj[u][i];
           if(!visited[v])
           {
               visited[v]=1;
               q.push(v);
               dist[v]=1+dist[u];
           }
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
   /*for(auto i:visited)
   {
       cout<<i<<" ";
   }*/

    bfs(1);

        if (dist[n]==2) cout<<"POSSIBLE"<<endl;
        else cout<<"IMPOSSIBLE"<<endl;
}


Measured memory_bytes: 36468
using System;
using System.Collections.Generic;

using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string dat = Console.ReadLine();
            DateTime ds = DateTime.Parse(dat);

            DateTime d = DateTime.Parse("2019/04/30");


            if (d < ds)
            {
                Console.WriteLine("TBD");
            }
            else
            {
                Console.WriteLine("Heisei");
            }



        }
    }
}


Measured memory_bytes: 13792
while True:
    H,W=map(int,input().split())
    if H==0 and W==0:
        break
    else:
        for i in range(H):
            for j in range(W):
                if (i+j)%2==0:
                    print('#',end='')
                else:
                    print('.',end='')
            print()
        print()


Measured memory_bytes: 7008
use proconio::input;

fn main() {
    input! {
        n: i64,
        k: i64
    }
    let m = 1000000007;
    let mut ans:i64 = 0;
    for i in k..n+2 {
        let min = i*(i-1)/2%m;
        let max = n*(n+1)/2%m - (n+1-i)*(n-i)/2%m;
        ans += (max -min + 1)%m;
        //println!("i={},min={},max={},ans={}", i,min,max,ans);
    }
    ans = ans%m;
    if ans<0 {ans += m;}
    println!("{}",ans);

}



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

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> G(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int ans = 0, last = 0;
  for (int i = 1; i < N; i++) {
    bool f = true;
    for (int j = 0; j < G[i].size(); j++) {
      if (last <= G[i][j] && G[i][j] <= i) {
        f = false;
        break;
      }
    }
    if (!f) {
      last = i;
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 6016
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define pb push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>b;i--)
#define mkp(a,b) make_pair(a,b)
#define all(v) v.begin(),v.end()
using namespace std;
bool compare(pair<int,int>& p1,pair<int,int>& p2)
{
    return p1.second<p2.second;
}
int main()
{
    fastio
    string s,t;
    cin>>s>>t;
    int count=0;
    REP(i,0,s.size())
    {
        if(s[i]!=t[i])
            count++;
    }
    cout<<count<<"\n";
}

Measured memory_bytes: 3812
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//
#define int long long
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#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 UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((a) >> (b)) & 1
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

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

  int ans = INF;
  for (int i = 0; i + 2 < s.size(); i++) {
    string tmp = s.substr(i, 3);
    int a = toInt(tmp);
    int b = abs(753 - a);
    chmin(ans, b);
  }

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


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
 
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        int C = stdIn.nextInt();
         
        double Cc = C * Math.PI /180;
         
        double L = Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Cc));
        double h = b * Math.sin(Cc);
        double S = b * Math.sin(Cc) * a /2;
         
        System.out.println(S);
        System.out.println(L + a + b);
        System.out.println(h);
    }
}


Measured memory_bytes: 26280
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

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

using namespace std;

long long gcd(long long a, long long b) {
    if(a < b){
        swap(a,b);
    }
    long long c;
    while(a%b !=0) {
        c = a;
        a = b;
        b = c%b;
    }
    return b;
}

long long lcm(long long a, long long b) {
    long long tmp = gcd(a,b);
    return (a/tmp)*(b/tmp)*tmp;
}

int main(){
    int n; cin >> n;
    vector<int> v(n);
    long long ans = 0;
    rep(i, n) {
        cin >> v[i];
        ans += v[i] -1;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
//url:
//problem name:

#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long,long>;
using veci = vector<int>;
using vecl = vector<long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long,long>>;

string a,b;
string n;

int main() {
    cin >> a >> b;
    n = a + b;
    string ans = "No";
    for(int i = 1; i*i <= 100100; i++) {
        if(to_string(i*i) == n) ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
#include<stdio.h>

int main(){
  int num; //あたえられる整数
  int N; //N進数
  int K; //桁数
  
  scanf("%d %d",&num,&N);
  
  while(num>0){
    num /= N;
    K++;
  }
  
  printf("%d",K);
  
  return 0;
}

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

int main() {
  int N, a=1,sum;
  cin >> N;
  for(int i=0;i<8;i++){
    a*=10;
    sum+=N%a/(a/10);
  }
  if(N%sum==0)
    cout << "Yes"<< endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	input = input.split("\n");
  	var S = input[0];
       S = S.replace(/o/g,"");
        if(S.length >= 8){
       console.log("NO");
}else{
       console.log("YES");
}
 }
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];


int main(){
  ll n,ans=0;cin>>n;
  vll a(n);
  rep(i,0,n){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  ll x=(n-2)/2;
  ans+=a[0];
  ll tmp=0;
  rep(i,0,x){
    tmp++;
    ans+=a[tmp]*2;
  }
  if(n%2){ans+=a[tmp+1];}
  cout<<ans<<endl;
}







Measured memory_bytes: 4792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>
#include <iterator>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

const double PI = 3.1415926535897932384626433832795;

int main() {
  int n, m;
  cin >> n >> m;
  LL ans = 0;
  //ans += (n - m ) * 100;
  LL pownum = pow(2, m);
  eprintf("pownum:%lld\n", pownum);
  ans = (100 * (n-m) + 1900*m) * pownum; 
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long lli;

const int MAXN = 250;
const int MAXM = MAXN*(MAXN+1)/2;
int N, M;
lli B[MAXM];

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

int main() {
  while(cin >> N && N) {
    M = N*(N+1)/2;
    for(int i = 0; i < M; ++i) {
      cin >> B[i];
    }
    vector<lli> even, odd;
    for(int i = 0; i < M; ++i) {
      if(B[i] % 2 == 0) even.push_back(B[i]);
      else odd.push_back(B[i]);
    }
    sort(even.begin(), even.end());
    sort(odd.begin(), odd.end());
    lli c1 = odd[0];
    lli c2 = even[0];
    lli c3 = even[1];
    {
      lli tmp = gcd(c1, c2);
      c1 /= tmp;
      c2 /= tmp;
    }
    {
      lli tmp = gcd(c1, c3);
      c1 /= tmp;
      c3 /= tmp;
    }
    lli a0 = sqrt(c2*c3);
    cout << a0 << endl;
    for(int i = 0; i < even.size(); ++i) {
      if(i) cout << " ";
      cout << even[i]/a0;
    }
    cout << endl;
  }  
  return 0;
}

Measured memory_bytes: 1852
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
 
int main(){
	ll n, m, d;
	cin >> n >> m >> d;
	ll k=(d==0)? n : 2*(n-d);
	printf("%.9f\n", (double)(m-1)*k/(n*n));
	return 0;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

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

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

void compress(vector<int> &v){
    int N = v.size(), mn = 1000000000;
    vector<pair<int,int>> a(N);
    for(int i=0; i<N; ++i){
        a[i].first = v[i];
        a[i].second = i;
        mn = min(mn, v[i]);
    }
    sort(a.begin(), a.end());
    
    int prev = mn-1, n = -1;
    for(int i=0; i<N; ++i){
        if(a[i].first == prev) v[a[i].second] = n;
        else{
            n++;
            prev = a[i].first;
            v[a[i].second] = n;
        }
    }
}

void Main(){
    int N; cin >> N;
    VI S(1<<N); REP(i,1<<N) cin >> S[i]; SORT(S);

    VI c; c.push_back(S.back()); S.back() = -1;
    REP(i,N){
        VI p = c;
        SORT(p);
        int ai = (1<<N)-1;

        while(p.size() && ai>=0){
            if(S[ai] == -1){
                ai--;
                continue;
            }

            if(S[ai] < p.back()){
                c.push_back(S[ai]);
                p.pop_back();
                S[ai] = -1;
            }

            ai--;
        }

        if(p.size()){
            cout << "No" << en;
            return;
        }
    }

    cout << "Yes" << en;
    return;
}

int main(void){
    cin.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t){
        Main();
    }
    return 0;
}

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

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll =V<pll>;
using vtpll = V<tpll>;
using vst = V<str>;
using vch = V<char>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define ci(a) cin>>a
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define cfs(a) cout<<fixed<<setprecision(a)
#define INF 1e16
#define mod 1e9+7
//vvll v(n,vll(m)) n行m列
//A.erase(A.begin()+i) 配列Aのi番目を消せる
//std::binary_search(v.bgn,v.en,a);
//abs(a,b)   pow(a,n)  to_string  stoll
//auto Iter=lower_bound(v.bgn,v.en,a);
//lower//upper  co(*Iter)co(Iter-v.bgn);

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
#define comuse Comuse()
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  ll n;
  str s;
  cin>>n>>s;
  if(n>=3200){
    co(s);
  }
  else{
    co("red");
  }
}


Measured memory_bytes: 256
N=int(input())
mod=10**9+7
memo=[{}for _ in range(N+1)]
def ok(last4):
    for i in range(4):
        t=list(last4)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if ''.join(t).count('AGC')>=1:
            return False
    return True
def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==N:
        return 1
    ret=0
    for c in 'AGCT':
        if ok(last3+c):
            ret+=dfs(cur+1,last3[1:]+c)
            ret%=mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,'TTT'))

Measured memory_bytes: 3820
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// flagを用いたバブルソート
int bubbleSort(int A[],int N) {
    int i,j;
    int sw = 0;
    unsigned short flag = 1;
    for(i=0;flag;i++) {
        flag = 0;
        for(j=N-1;j>=i+1;j--) {
            if(A[j]<A[j-1]) {
                swap(&A[j],&A[j-1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main(void) {
    int i, A[100], N, sw;
    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);

    sw = bubbleSort(A,N);

    for(i=0;i<N;i++) {
        if (i) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n%d\n",sw);

    return 0;
}


Measured memory_bytes: 2096
import java.util.Scanner;
class Main {
	public void aa() {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		while(x != 0 || y != 0) {
			if(x < y) {
				System.out.println(x + " " + y);
			} else {
				System.out.println(y + " " + x);
			}
			x = sc.nextInt();
			y = sc.nextInt();
		}
	}
	public static void main(String[] args) {
		new Main().aa();
	}
}

Measured memory_bytes: 27152
#include<iostream>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
  stack<int> S1;
  stack<pair<int, int> > S2;
  char ch;
  int sum = 0;
  for(int i = 0; cin >> ch; i++) {
    if(ch == '\\') S1.push(i);
    else if(ch == '/' && S1.size() > 0) {
      int j = S1.top(); S1.pop();
      sum += i - j;

      int a = i - j;
      while(S2.size() > 0 && S2.top().first > j) {
        a += S2.top().second; S2.pop();
      }
      S2.push(make_pair(j, a));
    }
  }

  vector<int> ans;
  while(S2.size() > 0) {
    ans.push_back(S2.top().second);
    S2.pop();
  }
  reverse(ans.begin(), ans.end());
  cout<<sum<<endl;
  cout<<ans.size();
  for(int i = 0; i < ans.size(); i++) {
    cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;

  return 0;
}



Measured memory_bytes: 3236
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
 
using namespace std;
 
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define rep(i,n) REP(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;

const int INF = 1e9;
const double EPS = 1e-8;
const int mod = 1e9 + 7;
const ll LINF = 1e18;
const double PI = acos(-1);

struct Input
{
	int n;char c;char str[1024];string s;ll l;
	int nextInt(){scanf("%d", &n);return n;}
	ll nextLong(){scanf("%lld", &l);return l;}
	char nextChar(){scanf("%c", &c);return c;}
	string next(){scanf("%s", str);return string(str);}
	string nextLine(){getline(cin, s);return s;}
};
Input in;

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

string s[8];
int d[8][8][8];

int count(int y, int x, int dir, int turn){
	int ret = 0, nx = x, ny = y;
	if(s[y][x] != '.') return 0;
	char c = (turn % 2 == 0 ? 'o' : 'x');
	char e = (turn % 2 == 1 ? 'o' : 'x');
	for(int i = 0; i < 9; i++){
		nx += dx[dir];
		ny += dy[dir];
		if(nx < 0 || nx >= 8 || ny < 0 || ny >= 8) return 0;
		if(s[ny][nx] == c) return i;
		else if(s[ny][nx] == '.') return 0;
	}
	return 0;
}

void fill(int y, int x, int dir, int turn){
	int nx = x, ny = y;
	char c = (turn % 2 == 0 ? 'o' : 'x');
	char e = (turn % 2 == 1 ? 'o' : 'x');
	s[y][x] = c;
	for(int i = 0; i < 9; i++){
		ny += dy[dir];
		nx += dx[dir];
		if(s[ny][nx] == c) return;
		s[ny][nx] = c;
	}
}

int main(){
	rep(i, 8) s[i] = in.next();
	
	for(int i = 0; i < 1000; i++){
		int y, x, dir, c = 0;
		for(int ty = 0; ty < 8; ty++){
			for(int tx = 0; tx < 8; tx++){
				int tc = 0, ttd = 0;
				for(int td = 0; td < 8; td++){
					int ttc = count(ty, tx, td, i);
					tc += ttc;
					if(ttc != 0) ttd |= (1<<td);
				}
				if((tc > c) || (i % 2 == 1 && tc == c)){
					c = tc;
					x = tx;
					y = ty;
					dir = ttd;
				}
			}
		}
		if(c == 0) continue;
		for(int td = 0; td < 8; td++){
			if((dir & (1<<td)) != 0) fill(y, x, td, i);
		}
	}

	rep(i, 8) cout<<s[i]<<endl;
}

Measured memory_bytes: 3292
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

void solve(){
  int n, k; cin >> n >> k;
  int sum = 0;
  for(int i = 0; i < n; i++){
    int h; cin >> h;
    if(h >= k) sum++;
  }
  cout << sum << endl;
  return;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
typedef long long ll;

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

    int cnt = 1;

    for(int i = 0; i < n; ++i){
        if(a[i] == cnt) ++cnt;
    }

    if(cnt == 1){
        cout << -1 << endl;
        return 0;
    }

    cout << n-cnt+1 << endl;

    return 0;
}


Measured memory_bytes: 1024
import itertools
n,d=map(int,input().split())
ans=0
def dist(A,B):
  ret=0
  for i in range(d):
    ret+=(A[i]-B[i])**2
  return int(ret**0.5)**2==ret
XX=[]
for i in range(n):
  X=[int(i) for i in input().split()]
  XX.append(X)

for c1,c2 in itertools.combinations(range(n),2):
  A,B=XX[c1],XX[c2]
  if dist(A,B):
    ans+=1
print(ans)

Measured memory_bytes: 3188
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<iostream>
using namespace std;
int f[100005];
int main(){
	int n,s,ans=0;
	scanf("%d",&n);
	int a;
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		f[a]++;f[a-1]++;f[a+1]++;
	}
	for(int i=1;i<=100000;i++)
		if(f[i]>ans)ans=f[i];
	printf("%d\n",ans);	 
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int b, c;
int eval(int n){
    return min(n, b - n);
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    in_arr(int, a, n);
    sort(a.begin(), a.end());
    b = a[n - 1];
    c = 0;
    repi(i, a){
        //cout << eval(*i) << endl;
        if(eval(*i) > eval(c)){
            c = *i;
        }
    }
    cout << b << " " << c << endl;
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
const int mod = 1e+9 + 7;

// i文字目まで見たとき、状態がjである場合の数(%mod)
// j=0 : どこにも印をつけていない状態
// j=1 : A一つだけに印をつけている状態
// j=2 : AとB一つずつに印をつけている状態
// j=3 : A,B,Cに印をつけた状態
ll dp[100005][4];

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

    string s; 
    cin >> s;
    int n = (int)s.length();

    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        if(s[i] == '?'){    // i文字目が確定していない場合
            // 前の状態を遷移させておく(i文字目は無視する場合)
            dp[i+1][0] = 3 * dp[i][0];
            dp[i+1][1] = 3 * dp[i][1];
            dp[i+1][2] = 3 * dp[i][2];
            dp[i+1][3] = 3 * dp[i][3];

            // 各文字を入れたときの追加処理
            dp[i+1][1] += dp[i][0];     // i文字目のAに印をつける場合
            dp[i+1][2] += dp[i][1];     // i文字目のBに印をつける場合
            dp[i+1][3] += dp[i][2];     // i文字目のCに印をつける場合
        }
        else{   // i文字目が確定している場合
            // 前の状態を遷移させておく(i文字目を無視する場合)
            dp[i+1][0] = dp[i][0];
            dp[i+1][1] = dp[i][1];
            dp[i+1][2] = dp[i][2];
            dp[i+1][3] = dp[i][3];

            // 各文字に対する追加処理
            if(s[i] == 'A'){
                dp[i+1][1] += dp[i][0];     // i文字目のAに印をつける場合
            }
            else if(s[i] == 'B'){
                dp[i+1][2] += dp[i][1];     // i文字目のBに印をつける場合
            }
            else if(s[i] == 'C'){
                dp[i+1][3] += dp[i][2];     // i文字目のCに印をつける場合
            }
        }
        if(dp[i+1][0] >= mod)   dp[i+1][0] %= mod;
        if(dp[i+1][1] >= mod)   dp[i+1][1] %= mod;
        if(dp[i+1][2] >= mod)   dp[i+1][2] %= mod;
        if(dp[i+1][3] >= mod)   dp[i+1][3] %= mod;
    }

    cout << dp[n][3] << endl;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
main(){
  int n;
  cin>>n;
  if(n==1){cout<<1;return 0;}
  vector<int> a(n);
  for(auto& i:a)cin>>i;
  sort(a.begin(),a.end());
  int res=0;
  int b[3][2]={0};
  b[0][1]=b[1][1]=b[2][1]=-1;
  for(int i=0;i<n;++i){
    if(b[0][1]<0){
      b[0][0]++;
      b[0][1]=a[i];
      continue;
    }
    if(b[0][1]!=a[i]){
      b[2][0]=b[1][0]; b[2][1]=b[1][1];
      b[1][0]=b[0][0]; b[1][1]=b[0][1];
      b[0][0]=1; b[0][1]=a[i];
    }
    else b[0][0]++;
    if(b[0][1]-1==b[1][1]&&b[1][1]-1==b[2][1])res=max(res,b[0][0]+b[1][0]+b[2][0]);
    else if(b[0][1]-1==b[1][1])res=max({res,b[0][0]+b[1][0],b[2][0]});
    else if(b[1][1]-1==b[2][1])res=max({res,b[1][0]+b[2][0],b[0][0]});
    else res=max({res,b[0][0],b[1][0],b[2][0]});
    cerr<<"["<<b[0][1]<<"]"<<b[0][0]<<" ["<<b[1][1]<<"]"<<b[1][0]<<" ["<<b[2][1]<<"]"<<b[2][0]<<"  r:"<<res<<"\n";
  }
  cout<<res;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 10;
 
ll n;
int arr[maxn];
int tree[maxn * 2];
 
int get_idx(int x) {
    return x + maxn;
}
 
void update(int x) {
    while(x < maxn * 2) {
        ++tree[x];
        x += x & -x;
    }
}
 
int query(int x) {
    int ret = 0;
    while(x) {
        ret += tree[x];
        x -= x & -x;
    }
    return ret;
}
 
int main(void) {
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", arr + i);
    int st = 1, ed = 1e9;
    int ans = INT_MAX;
    while(st <= ed) {
        int mid = st + ed >> 1;
 
        ll cnt = 0;
        memset(tree, 0, sizeof(tree));
        int base = 0;
        for(int i = 1; i <= n; ++i) {
            int now = arr[i] < mid ? -1 : 1;
            base += now;
            update(get_idx(now - base));
            cnt += query(get_idx(-base - 1));
        }
 
        //printf("%d %lld\n", mid, cnt);
 
        if(cnt <= n * (n + 1) / 4) { 
            st = mid + 1;
            ans = mid;              
 
        }
        else {
            ed = mid - 1;
        }
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 13;
int n, arr[maxN], a[maxN];
bool can (int x) {
    for (int i = 0; i < 2 * n - 1; i++)
	arr[i] = (a[i] >= x);
    int lst = arr[n - 1];
    int l = n - 2;
    int r = n;
    while (l >= 0 && arr[l] == arr[r] && arr[l] != lst) {
	lst = arr[l];
	l--;
	r++;
    }
    /* cout << x << " " << lst << endl;
    for (int i = 0; i < 2 * n - 1; i++)
	cout << arr[i] << " ";
	cout << endl;
    */
    return !lst;
}
    
int main () {
    cin >> n;
    for (int i = 0; i < 2 * n - 1; i++)
	cin >> a[i];
    int l = 0, r = 2 * n;
    while (r - l > 1) {
	int mid = l + r >> 1;
	if (can(mid))
	    r = mid;
	else
	    l = mid;
    }
    cout << l << endl;
}


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


int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
  
// Function to find gcd of array of 
// numbers 
int findGCD(int arr[], int n) 
{ 
    int result = arr[0]; 
    for (int i = 1; i < n; i++) 
    { 
        result = gcd(arr[i], result); 
  
        if(result == 1) 
        { 
           return 1; 
        } 
    } 
    return result; 
} 

int main(){
    int k;
    cin>>k;
    int sum=0;
    for(int i=1;i<=k;i++){
    	for(int j=1;j<=k;j++){
    		for(int p=1;p<=k;p++){
    			int arr[] = {i,j,p};
    			int n=3;
    			sum = sum + findGCD(arr, n);
    			
    			
    			
    			
			}
		}
	}
    
    
    cout << sum;
	
	   return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
using Graph = vector<vector<int>>;

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

  ll n; cin >> n;
  Vl a(n);
  rep(i, 0, n) cin >> a[i];
  ll x = 0, y = 0;
  rep(i, 0, n) y += a[i];
  ll ans = INF;
  rep(i, 0, n-1){
    x += a[i]; y -= a[i];
    ans = min(ans, abs(x-y));
  }
  cout << ans << endl;

  return 0;
}


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


//System.out.println();
public class Main implements Runnable { //クラス名はMain

    public static void main(String[] args) {
    	Thread.setDefaultUncaughtExceptionHandler((t,e)->System.exit(1));
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); //16MBスタックを確保して実行
    }

    //2 ≤ N ≤10^5
    //1 ≤ hi ≤ 10^4
    public void run() {
    	FastScanner sc = new FastScanner(System.in);
        int N = sc.nextInt();
        int h[] = new int[N];
        int dp[] = new int[N];

        dp[0]=0;
        for(int i=0; i<N; i++) {
        	h[i] = sc.nextInt();
        }

        int left = -1_000_000;
        int right = 1_000_000;

        for(int i=1; i<N; i++) {
        	if(i == 1) {
        		dp[i] = Math.abs(h[i]-h[i-1]);
        	}else {
        		//h[i-1] - h[i]
        		right = Math.abs(h[i]-h[i-1]) + dp[i-1];
        		//h[i-2] - h[i]
        		left = Math.abs(h[i]-h[i-2]) + dp[i-2];
        		if (left > right) {
        			dp[i] = right;
        		}else {
        			dp[i] = left;
        		}
        	}
        }

        System.out.println(dp[N-1]);

    }
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

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

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

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

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

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

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

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

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


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

int main(){
  int A,B,C,X,Y,ans=0;
  cin >> A >> B >> C >> X >> Y;
  if(A+B<2*C){
    ans=X*A+Y*B;
  }else{
    ans=min(X,Y)*C*2+max(X-Y,0)*min(A,2*C)+max(Y-X,0)*min(B,2*C);
  }
  cout << ans << endl;
    
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
state = 0

f = []
for i in range(n):
    f.append(0)
f[0]=1

state = state ^ a[0]

left = 0
for j in range(1,n):
    s = f[j-1]
    while state + a[j] != state ^ a[j]:
        s = s - 1
        state = state - a[left]
        left = left + 1
    f[j] = s + 1
    state = state + a[j]

ans = sum(f)
print(ans)

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

public class Main {

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		String s = fr.nextLine();
		int n = s.length();
		for (int cur = 1; cur<n/2; cur++) {
			boolean found = true;
			for (int i=0; i<(n-2*cur)/2; i++) {
				if (s.charAt(i) != s.charAt((n-2*cur)/2 + i)) {
					found = false;
					break;
				}
			}
			if (found) {
				System.out.println(n - 2*cur);
				break;
			}
		}
		
	}
	
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

		public String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}


Measured memory_bytes: 25392
#include<iostream>
 #include<algorithm>
 #include<cmath>
 #include<iomanip>
 #include<string.h>
 #include<cmath>
 #include<map>
 #include<vector>
using namespace std;
typedef long long ll;
char s[4005];
int main()
{
    int k,a,b;
    cin>>k>>a>>b;
    int flag=0;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            flag=1;
            cout<<"OK";
            break;
        }
        
    }
    if(!flag) cout<<"NG";
    
}


Measured memory_bytes: 3640
// ARC091D.cpp
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1, x, k; i <= n; i++)
    {
        scanf("%d%d", &x, &k);
        while (x % k != 0)
            x -= ((x % k - 1) / (x / k + 1) + 1) * (x / k + 1);
        ans ^= x / k;
    }
    puts(!ans ? "Aoki" : "Takahashi");
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdbool.h>

int A[1000010], G[100], cnt = 0;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void reverse(int *A, int n) {
	for (int i = 0; i < n/2; ++i) swap(&A[i], &A[n - 1 - i]);
}

void insertionSort(int *A, int n, int g) {
	for (int i = g; i < n; ++i) {
		int v = A[i];
		int j = i - g;
		while (j >= 0 && A[j] > v) {
			A[j+g] = A[j];
			j -= g;
			cnt++;
		}
		A[j+g] = v;
	}
}

void shellSort(int *A, int n) {
	int m = 0;
	G[m] = 1;
	while (true) {
		m++;
		G[m] = 3*G[m - 1] + 1;
		if (G[m] > n) break;
	}
	reverse(G, m);
	printf("%d\n", m);
	for (int i = 0; i < m; ++i) {
		if (i != m-1) printf("%d ", G[i]);
		else printf("%d\n", G[i]);
	}
	for (int i = 0; i < m; ++i) {
		insertionSort(A, n, G[i]);
	}
}

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

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



Measured memory_bytes: 6500
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    cout << (1000000 - n) % 1000 << "\n";
    return 0;
}

Measured memory_bytes: 3648