akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
    int b = sc.nextInt();
    if ( b%a == 0 ) {
      System.out.println(a+b);
    } else {
      System.out.println(b-a);
    }
  }
}

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}


int main() {
  int N;
  cin >> N;
  vector< int > H(N);
  cin >> H;

  int ret = 0;
  for(int i = 0; i < N; i++) {
    bool f = true;
    for(int j = i - 1; j >= 0; j--) {
      if(H[i] < H[j]) f = false;
    }
    ret += f;
  }
  cout << ret << endl;
}





Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define endl '\n'
#define ll long long
using namespace std;

int quotient(int a, int b) {
	return (a / b) + ((a % b) != 0);
}

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

	int n, x, t;
	cin >> n >> x >> t;
	cout << quotient(n, x) * t;

	return 0;
}


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

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

    int n, p;
    cin >> n >> p;
    int A[n], ec = 0;   //even_counter
    for(int i = 0; i < n; i++){
        cin >> A[i];
        if(A[i] % 2);
        else ec++;
    }
    long long ans = 0; 
    if(ec == n){
        if(p);
        else ans = pow(2, n);
    }else{
        ans = pow(2, n - 1);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
class Node
  def initilize
    @act = false
  end

  def insert(val)
    if val.empty?
      @act=true
    else
      case val[0]
      when 'A'
        @a = Node.new if @a.nil?
        @a.insert(val[1..-1])
      when 'C'
        @c = Node.new if @c.nil?
        @c.insert(val[1..-1])
      when 'G'
        @g = Node.new if @g.nil?
        @g.insert(val[1..-1])
      when 'T'
        @t = Node.new if @t.nil?
        @t.insert(val[1..-1])
      end
    end
  end
  
  def find(val)
    if val.empty?
      return @act
    else
      case val[0]
      when 'A'
        @a and @a.find(val[1..-1])
      when 'C'
        @c and @c.find(val[1..-1])
      when 'G'
        @g and @g.find(val[1..-1])
      when 'T'
        @t and @t.find(val[1..-1])
      end
    end
  end
  
  def dump
    p "@act: #{@act}, a:#{@a}, c:#{@c}, g:#{@g}, t:#{@t}"
  end
end

num = STDIN.gets
commands = STDIN.read.split("\n")

root = Node.new
commands.each do |command|
  proc,arg = command.split(' ')
  # p "command: #{proc} #{arg}"
  case proc
  when 'insert'
    root.insert(arg)
  when 'find'
    if root.find(arg)
      print "yes\n"
    else
      print "no\n"
    end
  end
end

Measured memory_bytes: 165924
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
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; }

lli n, x;

int main(void){
    cin >> n >> x;
    vector<lli> a(n);
    rep(i, n) cin >> a[i];
    vector<lli> b = a;
    if(b[0] > x) b[0] = x;
    rep(i, n){
        if(i+1<n && b[i]+b[i+1]>x){
            lli d = b[i]+b[i+1]-x;
            b[i+1]-=d;
        }
    }
    lli ans = 0;
    rep(i, n){
        ans+=a[i]-b[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  double W,H,X,Y;
  cin>>W>>H>>X>>Y;
  cout<<W*H/2<<" ";
  if(X==W-X&&Y==H-Y){
    cout<<1<<endl;
  }else cout<<0<<endl;
}

Measured memory_bytes: 256
using System;

class Mitsui_A{
  static void Main(){
    int[] Ar1 = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
    int[] Ar2 = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
    
    if (Ar1[0] == Ar2[0]) Console.WriteLine("0");
    else Console.WriteLine("1");
  }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,M,T;
  T=0;
  cin >> N >> M;
  vector<long long> A(N);
  for (int i=0;i<N;i++) {cin >> A[i];}
  sort(A.begin(),A.end());
  for (long long i=0;i<M;i++) {
    if (N>10) {
      if (A[N-2]*2<=A[N-1] && i<M && A[N-1]>0) {
        while (A[N-2]*2>A[N-1] && i<M && A[N-1]>0) {A[N-1]/=2;i++;}
        //cout << "a";
      }
      while (A[0]*2>=A[N-1] && i+N<M && A[N-1]>0) {
        for (int i2=N-1;i2>=0;i2--) {
          A[i2]/=2;
          i++;
          //cout << "b";
          //cout << i;
        }
      }
      if (A[0]*2>=A[N-1] && i+N>=M && A[N-1]>0) {
        long long i3=N-1-(M-i)+1;
        for (int i2=N-1;i2>=i3;i2--) {
          A[i2]/=2;
          i++;
          //cout << "c";
        }
      }
      else if (A[N-1]>0) {
        long long B=A[N-1]/2;
        int i3=N-1;
        while (A[i3]>=B && i<M && A[N-1]>0 && i3>=0) {
          A[i3]/=2;
          i3--;
          i++;
          //cout << "d";
        }
      }
      
    }
    else {A[N-1]/=2;i++;}
    sort(A.begin(),A.end());
    if (A[N-1]==0) {i=M;}
    //cout << "WWO";
    i--;
  }
  for (int i=0;i<N;i++) {T+=A[i];}
  cout << T << endl;
  
}


Measured memory_bytes: 1024
from collections import deque, defaultdict

H, W = map(int, input().split())
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if visited[i][j]:
            continue
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        n = defaultdict(int)
        while len(q) > 0:
            si, sj = q.popleft()
            n[S[si][sj]] += 1
            for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                if 0 <= si + di < H and 0 <= sj + dj < W and S[si][sj] != S[si + di][sj + dj] and not visited[si + di][sj + dj]:
                    q.append((si + di, sj + dj))
                    visited[si + di][sj + dj] = True
        ans += n['#'] * n['.']

print(ans)


Measured memory_bytes: 10824
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            ans += (s.charAt(i) == '1')? 1 : 0;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
island, ship = map(int, input().split())
startTo, fromGoal = [False] * island, [False] * island
for i in range(ship):
  a, b = map(int, input().split())
  if a == 1:
    startTo[b - 1] = True
  elif b == 1:
    startTo[a - 1] = True
  elif a == island:
    fromGoal[b - 1] = True
  elif b == island:
    fromGoal[a - 1] = True
check = False
for i in range(island):
  if startTo[i] and fromGoal[i]:
    check = True
    break
if check:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Measured memory_bytes: 6132
#include<iostream>
#include<utility>
#include<algorithm>
#include<iomanip>

using namespace std;

#define allof(x) (x).begin(), (x).end()

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

ll gcd(ll x, ll y) {
    while (x % y) {
        x %= y;
        swap(x, y);
    }
    return y;
}

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

    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    cout << fixed << setprecision(15) << (double)W * H / 2.0 << " ";
    cout << (W == 2 * x && H == 2 * y);
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"unicode"
)

//先頭文字A判定
func ini(s string)bool {
	if s[0] == 'A' {
		return true
	} else {
		return false
	}
}

//C判定
func upc(s string)int {
	for i := 2; i < len(s)-1; i++{
		if s[i] == 'C' {
			return i
		}
	}
	return -1
}

//小文字判定
func isupper(s string, num int) bool {
	for i := range s {
      if i == 0 || i == num {
      	continue
      }
		target := rune(s[i])
		if unicode.IsUpper(target) {
          //fmt.Println(string(s[i]))
			return false
		}
	}
	return true
}

func main() {
	var s string
	fmt.Scan(&s)
	
	//fmt.Println(ini(s))
	//fmt.Println(upc(s) != -1)
	//fmt.Println(isupper(s,upc(s)))
	//fmt.Println(upc(s))
	if ini(s) && upc(s) != -1 && isupper(s,upc(s)) {
		fmt.Println("AC")
	} else {
		fmt.Println("WA")
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  cin >> N >> K;
  set<int> s;
  for (int i=0;i<K;i++){
    int D;
    cin >> D;
    s.insert(D);
  }
  int ans;
  for (int i=N;i<100000;i++){
    int j=i,k=i;
    bool can=true;
    while (k>=1){
      if (s.count(k%10)){
        can=false;
        break;
      }
      else{
        k=k/10;
      }
    }
    if (can){
      ans=j;
      break;
    }
  }
  cout << ans<< endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
//#define int long long
template<typename T> inline bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }

int main() {
    string S;
    cin >> S;
    int N = S.length();
    
    if (N == 2) { 
        if (S[0] == S[1]) { cout << "1 2" << endl; }
        else { cout << "-1 -1" << endl; }
        return 0;
    }
    
    auto is_ok = [] (string S) {
        assert(S.length() == 3);
        sort(S.begin(), S.end());
        return (S[0] == S[1] || S[1] == S[2]);
    };
    
    for (int i = 0; i <= N-3; i++) {
        if (is_ok(S.substr(i, 3))) {
            cout << i+1 << " " << i+3 << endl;
            return 0;
        }
    }
    
    cout << "-1 -1" << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,k,A[200000],ans=2e9,a;
  cin>>n>>k;
  rep(i,n) cin>>A[i];
  rep(i,n-k+1){
    if(A[i]<0&&A[i+k-1]>0) a=min(2*A[i+k-1]-A[i],A[i+k-1]-2*A[i]);
    else if(A[i+k-1]<0) a=-A[i];
    else a=A[i+k-1];
    ans=min(ans,a);
  }
  cout<<ans;
}

Measured memory_bytes: 640
n,a,b = map(int,input().split())
l=[]
for i in range(1,n+1): #1からNまでの整数を全探索
    ic = list(str(int(i))) #整数を各桁リスト化
    s = list(map(int,ic))
    if sum(s) >= a and sum(s) <= b:
        l.append(i)
print(sum(l))

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

using namespace std;
int main()
{
    long long n,num,sum=0;
    cin>>n;
    vector<int>v;
    long long  c=0;
    for(long long  i=0;i<n;i++)
    {
        cin>>num;
        if(num<0)
        {
            c++;
        }
        v.push_back(abs(num));
        sum +=abs(num);
    }
    sort(v.begin(),v.end());
    if(c%2==0)
    {
        cout<<sum<<endl;
    }
    else
    {
        cout<<sum-2*v[0]<<endl;
    }
}


Measured memory_bytes: 3944
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            String s  = sc.next();
            list.add(s);
        }
        List<String> listb = new ArrayList<String>(new HashSet<>(list));
        sc.close();
        System.out.println(listb.size());
    
        
    }
}

Measured memory_bytes: 73072
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cstdio>

using namespace std;


int N;
int flag[200001] = {0};
int ans = 0;

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        a--;
        flag[a]++;
    }

    
    for(int i = 0; i <= 100001; i++){
        int tmp = 0;
        tmp += flag[i-1] + flag[i] + flag[i+1];
        ans = max(ans,tmp);
    }

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


Measured memory_bytes: 640
import itertools
n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
c = [i for i in range(1,n+1)]
v = list(itertools.permutations(c,n))
a = v.index(p)
b = v.index(q)
print(abs(a-b))

Measured memory_bytes: 70212
#include "bits/stdc++.h"
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define ll long long


signed main() {
	string S; cin >> S;
	ll N = S.size();
	ll ans = N * (N + 1) / 2;
	vector<int>sa = suffix_array(S);
	for (auto x : lcp_array(S, sa)) {
		ans -= x;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 15648
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;


int main() {
    
    int N = 0;
    int K = 0;
    cin >> N >> K;
    vector<int> p(N);
    long int total = 0;
    
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    
    sort(p.begin(), p.end());
    for (int i = 0; i < K; i++) {
        total += p[i];
    }

    cout << total << endl;

    return 0;
}


Measured memory_bytes: 3188
from sys import stdin
a = [True]*1000000
for i in range(2,1000000):
    if a[i]:
        for j in range(i+i, 1000000)[::i]:
            a[j] = False

b = [None]*1000000
b[0] = b[1] = 0
for i in range(2,1000000):
    if a[i]:
        b[i] = b[i-1] + 1
    else:
        b[i] = b[i-1]

while True:
    try:
        print(b[int(input())])
    except:
        break


Measured memory_bytes: 23444
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, p int
	var s string
	fmt.Scan(&n)
	keys := make([]string, n)
	rsts := make(map[string]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&s, &p)
		keys[i] = s + fmt.Sprintf("%03d", 100-p)
		rsts[keys[i]] = i + 1
	}
	sort.Strings(keys)

	for _, k := range keys {
		fmt.Println(rsts[k])
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
constexpr ll ten(int n){return (n==0) ? 1 : 10 * ten(n-1);}
#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,N) for(int i=0;i<(int)(N);i++)
#define rep1(i,N) for(int i=1;i<=(int)(N);i++)
#define a first
#define b second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
template<class T, class U> void chmin(T& t, const U& u){ if(t>u) t = u;}
template<class T, class U> void chmax(T& t, const U& u){ if(t<u) t = u;}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& p){
    return os << "P(" << p.fs << ", " << p.sc << ")";
}
template<class T> ostream& operator<<(ostream& os, const vc<T>& v){
    os << "[";
    for(auto d: v) os << d << ", ";
    return os << "]";
}

using vi=vector<int>;

const int nmax=100010;
vi g[nmax];

bool vis[nmax];
void dfs(int v){
	if(vis[v])return;
	vis[v]=true;
	for(auto to:g[v])dfs(to);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int n;cin>>n;
    vi r(n),c(n);
    rep(_,n){
		int i,j;cin>>i>>j;
		i--;j--;
		g[i].pb(j);
		g[j].pb(i);
		r[i]++;
		c[j]++;
	}
	
	if(r!=vi(n,1)||c!=vi(n,1)){
		cout<<-1<<endl;
		return 0;
	}
	
	int ans=n;
	rep(i,n)if(!vis[i]){
		ans--;
		dfs(i);
	}
	
	cout<<ans<<endl;
}



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

int main(){
  long long A, B, C;
  cin >> A >> B >> C;
  long long ans;
  if(A%2==0 || B%2==0 || C%2==0) ans=0;
  else ans = min({A*B, B*C, C*A});
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
struct edge {
    int id,to;
    edge(int id,int to):id(id),to(to) {}
};
vector<vector<edge>> tree;
vi ans;

void dfs(int now = 0,int p = -1,int c = -1) {
    int nc = 0;
    for(auto e : tree[now]) {
        if(e.to == p) continue;
        if(nc == c) nc++;
        ans[e.id] = nc;
        dfs(e.to,now,nc);
        nc++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    tree.resize(n);
    rep(i,n-1) {
        int a,b;
        cin >> a >> b;
        a--; b--;
        tree[a].eb(i,b);
        tree[b].eb(i,a);
    }
    int k = 0;
    rep(i,n) chmax(k,(int)tree[i].size());
    ans.resize(n-1);
    dfs();
    cout << k << endl;
    rep(i,n-1) cout << ans[i]+1 << endl;
}

Measured memory_bytes: 8320
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
string s;
int n;
int main(){
  cin >> n >> s;
  bool used[2][26];
  int ret = 0;
  for(int i=1; i<n; i++){
    int tmp = 0;
    memset(used, false, sizeof(used));
    for(int j=0; j<n; j++){
      if(i<j) used[0][s[j]-'a'] |= true;
      else used[1][s[j]-'a'] |= true;
      }
    for(int j=0; j<26; j++){
      tmp += (used[0][j] & used[1][j]);
        }
    ret = max(ret, tmp);
    }
  cout << ret << endl;
  return 0;
  }
  

Measured memory_bytes: 256
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <queue>
#define PII pair<int, int>
#define T3I tuple<int, int, int>
using namespace std;

typedef long long ll;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

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

    int K, N;
    cin >> K >> N;
    vector<int> A(N);
    for(int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    int ans = K-A[N-1]+A[0];
    for(int i = 1; i < N; ++i) {
        ans = max(ans, A[i]-A[i-1]);
    }
    cout << K-ans << endl;
}


Measured memory_bytes: 1024
#%%
s = input()
n = len(s)

s = list(s)
a, b, c = 0, 0, 0
for i in range(n):
    if s[i] == 'a':
        a += 1
    elif s[i] == 'b':
        b += 1
    else:
        c += 1

d = (n-1)/3 + 1

if a <= d and b <= d and c <= d:
    ans = 'YES'
else:
    ans = 'NO'

print(ans)

Measured memory_bytes: 3956
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[i][j] = 0
        que = deque([[i,j]])
        while que:
            h,w = que.pop()
            for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
                nh = h+dh
                nw = w+dw
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if maze[nh][nw] == '#':
                    continue
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w]+1
                    que.appendleft([nh,nw])
        ans = max(ans,max([max(d) for d in dist]))
print(ans)

Measured memory_bytes: 10056
package main

import "fmt"

func stringToRunes(s string) (runes []rune) {
	runes = make([]rune, len(s))
	for i, r := range s {
		runes[i] = r
	}
	return
}

func main() {
	var even, odd string
	fmt.Scan(&even, &odd)
	le := stringToRunes(even)
	lo := stringToRunes(odd)
	var password string
	for i := 0; i < len(le)-1; i++ {
		password += string(le[i]) + string(lo[i])
	}
	if len(le) == len(lo) {
		password += string(le[len(le)-1]) + string(lo[len(lo)-1])
	} else {
		password += string(le[len(le)-1])
	}
	fmt.Println(password)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
 
  long long a, b, r, x, tmp;
 
  // printf("2つの自然数を入力してください。\n");
  // printf("1つ目の自然数 = ");
  // scanf("%d", &a);
  // printf("2つ目の自然数 = ");
  // scanf("%d", &b);

  cin >> a;
  cin >> b;
 
  x = a * b;
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
  /* 最小公倍数を出力 */
  // printf("最小公倍数 = %d\n", x/b);
  cout << x/b << endl;
}


Measured memory_bytes: 256
s = input()
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    if s[i] == "?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[len(s)][5])


Measured memory_bytes: 66140
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

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

const int maxn = 2e5 + 5;
const lli inf = 1e15;

int n, Q;
int A, B;
int x[maxn];

struct segment_tree
{
    vector<lli> val, lz;

    void init(int n)
    {
        val.resize(n * 4, inf);
        lz.resize(n * 4, 0);
    }

    void push(int x)
    {
        if(lz[x] == 0) return;
        lli t = lz[x];

        lz[x * 2] += t; val[x * 2] += t;
        lz[x * 2 + 1] += t; val[x * 2 + 1] += t;

        lz[x] = 0;
    }

    void update(int x, int l, int r, int p, lli v)
    {
        if(p < l || p > r) return;
        if(l == r)
        {
            val[x] = v;
            return;
        }
        push(x);
        int mid = (l + r) / 2;
        update(x * 2, l, mid, p, v);
        update(x * 2 + 1, mid + 1, r, p, v);
        val[x] = min(val[x * 2], val[x * 2 + 1]);
    }

    void inc(int x, int l, int r, int L, int R, int v)
    {
        if(L > r || l > R) return;
        if(l >= L && r <= R)
        {
            val[x] += v;
            lz[x] += v;
            return;
        }
        push(x);
        int mid = (l + r) / 2;
        inc(x * 2, l, mid, L, R, v);
        inc(x * 2 + 1, mid + 1, r, L, R, v);
        val[x] = min(val[x * 2], val[x * 2 + 1]);
    }

    lli get(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R || L > R) return inf;
        if(l >= L && r <= R)
            return val[x];
        push(x);
        int mid = (l + r) / 2;
        return min(get(x * 2, l, mid, L, R),
                   get(x * 2 + 1, mid + 1, r, L, R));
    }
} tree_all, treel, treer;

void read_input()
{
    cin >> n >> Q >> A >> B;
    for(int i = 1; i <= Q; ++i)
        cin >> x[i];
}

void init()
{
    tree_all.init(maxn); treel.init(maxn); treer.init(maxn);
    x[0] = A;
    tree_all.update(1, 1, n, B, 0);
    treel.update(1, 1, n, B, -B);
    treer.update(1, 1, n, B, B);
}

void solve()
{
    for(int i = 1; i <= Q; ++i)
    {
        lli nval = min(treel.get(1, 1, n, 1, x[i]) + x[i],
                       treer.get(1, 1, n, x[i] + 1, n) - x[i]);
        tree_all.inc(1, 1, n, 1, n, abs(x[i] - x[i - 1]));
        treel.inc(1, 1, n, 1, n, abs(x[i] - x[i - 1]));
        treer.inc(1, 1, n, 1, n, abs(x[i] - x[i - 1]));
        lli curval = tree_all.get(1, 1, n, x[i - 1], x[i - 1]);
        if(nval < curval)
        {
            tree_all.update(1, 1, n, x[i - 1], nval);
            treel.update(1, 1, n, x[i - 1], nval - x[i - 1]);
            treer.update(1, 1, n, x[i - 1], nval + x[i - 1]);
        }
    }
    cout << tree_all.get(1, 1, n, 1, n) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}



Measured memory_bytes: 38528
n = int(input())
top = [int(i) for i in input().split()]
bottom = [int(i) for i in input().split()]

maxlist = [0]*n

topsum = 0

btmsum = 0
for btm in bottom:
  btmsum += btm

for i in range(n):
  topsum += top[i]
  maxlist[i] = topsum + btmsum
  btmsum -= bottom[i]
  
print(max(maxlist))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using P = pair<int, int>;
int main()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = a*c;
    ans = max(a*d,ans);
    ans = max(b*c,ans);
    ans = max(b*d,ans);
    cout << ans << endl;
    
return 0;
}

Measured memory_bytes: 3632
from collections import deque

S = input()
Q = int(input())

d = deque(S)
flg = 1 #Trueが前から,
for i in range(Q):
    t, *a = input().split()
    if t == "1":
        flg = 1 - flg
    else:
        if flg:
            if a[0] == "1":
                d.appendleft(a[1])
            else:
                d.append(a[1])
        else:
            if a[0] == "2":
                d.appendleft(a[1])
            else:
                d.append(a[1])
d = list(d)
if flg:
    print(''.join(d))
else:
    print(''.join(d[::-1]))


Measured memory_bytes: 13884
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n;
int a[maxn];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1, greater<int>());
	int x, y;
	for(x = 1; x <= a[x]; ++x);
	--x;
	int sg1 = (a[x] - x + 1) & 1;
	for(y = x; x <= a[y]; ++y);
	--y;
	int sg2 = (y - x + 1) & 1;
	if(sg1 && sg2)
		puts("Second");
	else
		puts("First");
	return 0;
}
	 

Measured memory_bytes: 640
#include <stdio.h>
int main(void){
 int a,b,c;
 scanf("%d%d%d",&a,&b,&c);
 int x=a,n=b+c;
 if(x<b){x=b; n=a+c;}
 printf("%d",x<c?a+b:n);
 return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
/*
struct Edge
{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
*/
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> S(3);
    for (auto &it : S)
        cin >> it;
    string ans = "A";
    ans += S[1][0];
    ans += "C";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
 
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define int long long int
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define pow10(n) stoll("1"+string(n,'0'))
//fill(all(arr),1)
//if(map.count(key)){}
//bitset<20>(n);
//int mini=min({a,b,c,d,e});
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int32_t main(){
  FIO
  int n,a,b;
  cin>>n>>a>>b;
  for(int i=a;i<=b;i++)
  {
    if(i%n==0){cout<<"OK";return 0;}
  }
  cout<<"NG";
  
  return 0;
}

Measured memory_bytes: 3656
#include<stdio.h>
#include<string.h>
struct{char s;int n;}C[40],T[40],P;
int N,i,j;

void B()
{
	int i,j;
	for(i=0;i<N;i++)
		for(j=N-1;j>=0;j--)
		{
			if(C[j].n<C[j-1].n)
			{
				P=C[j];
				C[j]=C[j-1];
				C[j-1]=P;
			}
		}
}

void S()
{
	int i,j,p;
	for(i=0;i<N;i++)
	{
		p=i;
		for(j=i;j<N;j++)
			if(T[j].n<T[p].n)
				p=j;
		P=T[p];
		T[p]=T[i];
		T[i]=P;
	}
}

int main()
{
	scanf("%d\n",&N);
	for(i=0;i<N;i++)
		scanf("%c%1d%*c",&C[i].s,&C[i].n);
	memcpy(T,C,sizeof(C));
	B();S();
	for(i=0;i<N;i++)
		printf("%c%d%s",C[i].s,C[i].n,i==N-1?"\n":" ");
	puts("Stable");
	for(i=0;i<N;i++)
		printf("%c%d%s",T[i].s,T[i].n,i==N-1?"\n":" ");
	puts(memcmp(C,T,sizeof(C))==0?"Stable":"Not stable");
	return 0;
}

Measured memory_bytes: 620
// Sakhiya07 - Yagnik Sakhiya

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

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>

#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 1030;

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    ll n,m;
    cin >> n >> m;
    vector<ll> v[n];
    vector<vector<pll>> v1;
    ll a[n];
    for(ll i=0;i<n;i++)    cin >> a[i];
    for(ll i=0,x,y;i<m;i++)
    {
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    bool vis[n];
    memset(vis,0,sizeof(vis));
    for(ll i=0;i<n;i++)
    {
        if(vis[i]==0)
        {
            queue<ll> q;
            vector<pll> v2;
            q.push(i);
            vis[i] = 1;
            while(!q.empty())
            {
                ll top = q.front();
                q.pop();
                v2.pb({a[top],top});
                for(auto X:v[top])
                {
                    if(vis[X]==0)
                    {
                        vis[X] = 1;
                        q.push(X);
                    }
                }
            }
            sort(all(v2));
            v1.pb(v2);
        }
    }
    ll ans = 0;
    ll so = v1.size();
    ll sz = (so-1)*2;
    if(sz>n)    
    {
        cout<<"Impossible";
        return;
    }
    memset(vis,0,sizeof(vis));
    vector<pll> v2;
    for(ll i=0;i<so;i++)
    {
        v2.pb(v1[i][0]);
    }
    sort(all(v2));
    for(auto X:v2)
    {
        if(sz==0)    break;
        sz--;
        ans += X.ff;
        vis[X.ss] = 1;
    }
    v2.clear();
    for(ll i=0;i<v1.size();i++)
    {
        for(auto X:v1[i])
        {
            if(vis[X.ss])   continue;
            v2.pb(X);
        }
    }
    sort(all(v2));
    for(auto X:v2)
    {
        if(sz==0)   break;
        sz--;
        ans += X.ff;
    }
    cout<<ans;
}

int main()
{
    FAST;
    ll t = 1;
  //  cin >> t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 12764
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
from itertools import accumulate
#10**9+7
mod=1000000007


k=input()
d=int(input())
dp=[0]*(d+10)
dp2=0

for c in k:
    c=int(c)
    for e in range(d-1,-1,-1):
        dp[e+10]-=dp[e]
    dp[dp2]+=1
    dp[dp2+c]-=1
    dp=list(accumulate(dp))
    for e in range(9,-1,-1):
        dp[e]+=dp[d+e]
        dp[d+e]=0
    for e in range(d):
        dp[e]%=mod
    dp2=(dp2+c)%d
ans=dp[0]-1
if dp2==0:
    ans+=1
print(ans%mod)

Measured memory_bytes: 42220
H, W = map(int,input().split())
S = [input() for _ in range(H)]

result = [[0 for _ in range(W+1)]for _ in range(H+1)]
for i in range(H):
  for j in range(W):
    if(S[i][j] == '#'):
      result[i][j] = '#'
      if(result[i-1][j-1] != '#'):
        result[i-1][j-1] += 1
      if(result[i-1][j] != '#'):
        result[i-1][j] += 1
      if(result[i-1][j+1] != '#'):
        result[i-1][j+1] += 1
      if(result[i][j-1] != '#'):
        result[i][j-1] += 1
      if(result[i][j+1] != '#'):
        result[i][j+1] += 1
      if(result[i+1][j-1] != '#'):
        result[i+1][j-1] += 1
      if(result[i+1][j] != '#'):
        result[i+1][j] += 1
      if(result[i+1][j+1] != '#'):
        result[i+1][j+1] += 1

for r in result[:-1]:
  print(''.join(list(map(str,r[:W]))))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
vector<int> dv[1145140];
int val[1145140],sum[1145140];
int modpow(int x,int k){
	// x ^ k mod inf
	int res = 1;
	while(k>0){
		if(k%2)res = (res*x)%inf;
		x = (x*x)%inf;
		k >>=1;
	}
	return res;
}
signed main(){
	int n;
	cin>>n;
	vector<int> a;
	for(int i=0;i<n;i++){
		int x; cin>> x;
		a.pb(x);
	}
	for(int i=1;i<=1000000;i++){
		for(int j=i;j<=1000000;j+=i){
			dv[j].pb(i);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<dv[a[i]].size();j++){
			val[dv[a[i]][j]] += sum[dv[a[i]][j]] * a[i] ;
			val[dv[a[i]][j]] %= inf;
			sum[dv[a[i]][j]] += a[i];
			sum[dv[a[i]][j]] %= inf;
		}
	}
	int ans = 0;
	for(int i=1000000;i>=1;i--){
		for(int j=2*i;j<=1000000;j+=i){
			val[i] -= val[j];
			val[i] += inf;
			val[i] %= inf;
		}
		ans += val[i] * modpow( i, (ll)inf-2 );
		ans %= inf;
	}
	cout<<ans<<endl;
	return 0;
}

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

#define dump(x) cout << (x) << endl
#define Int int64_t
#define fi first
#define se second

Int INF = 1e18;
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    vector<pair<Int, Int>> vp;
    vp.emplace_back((Int)1, n);
    for (Int i = 2; i * i <= n; i++) {
        if (n % i == (Int)0) {
            vp.emplace_back(i, n / i);
        }
    }
    Int res = INF;
    for (Int i = 0; i < (Int)vp.size(); i++) {
        res = min(res, vp[i].fi + vp[i].se);
    }
    dump(res - (Int)2);
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll mod = 1e9+7;
const ll MAXN = 1000001;

ll spf[MAXN];  
void sieve() 
{ 
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++) 
        spf[i] = i; 
	for (int i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
    for (int i=3; i*i<MAXN; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (int j=i*i; j<MAXN; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}
unordered_map<ll,ll> mp;
bool getFactorization(int x) 
{ 
    vector<int> ret;
    map<ll,bool> vis; 
    while (x != 1) 
    { 
    	if(!vis[spf[x]]) {
        	ret.push_back(spf[x]); 
        	vis[spf[x]]=true;
    	}
        x = x / spf[x]; 
    }
    for(ll i:ret) {
    	if(mp.find(spf[i]) != mp.end()) 
        	return false;
        mp[spf[i]]++;
    }
    return true; 
}

int main() {
  fast
	sieve();
	ll n;
	cin>> n;
	ll a[n],i ,gd;
	bool f=false;
	for(i=0;i<n;i++) {
		cin>>a[i];
		if(!getFactorization(a[i]))
			f=true;
		if(i==0)
			gd=a[i];
		else
			gd = __gcd(gd,a[i]);
	}
	if(!f)
		cout<<"pairwise coprime";
	else if(gd == 1)
		cout<<"setwise coprime";
	else
		cout<<"not coprime";
	return 0;
}

Measured memory_bytes: 22360
#include <bits/stdc++.h>
//#include <atcoder/all>
#define ll long long int
#define MOD 1000000007
#define P pair<ll,ll>
#define INF 1000000000000000000
#define N 100000

//using namespace atcoder;
using namespace std;

int main(void){
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  vector<ll> num(N+1, 0);
  ll sum = 0;
  for (int i = 0; i < n; i++){
    cin >> a[i];

    num[a[i]]++;
    sum += a[i];
  }
  ll q;
  cin >> q;
  
  for (ll i = 0; i < q; i++){
    ll b, c;
    cin >> b >> c;
    
    sum += (c - b)*num[b];
    num[c] += num[b];
    num[b] = 0;
    cout << sum << endl;
  }

  return 0;
}


Measured memory_bytes: 4768
package main

import "fmt"

func main() {
        var a, b, c, d int
        fmt.Scan(&a)
        fmt.Scan(&b)
        fmt.Scan(&c)
        fmt.Scan(&d)

        if c < a {
                a, c = c, a
                b, d = d, b
        }

        answer := 0
        if c < b {
                if d <= b {
                        answer = d - c
                } else if b < d {
                        answer = b - c
                }
        }

        fmt.Printf("%d\n", answer)
}


Measured memory_bytes: 512
import java.util.Scanner;
public class Main{
	int a,b;
	
	public void solve(){
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		
		if(a<b){
			System.out.println("a < b");
		}if(a>b){
			System.out.println("a > b");
		}if(a==b){
			System.out.println("a == b");
		}
	}
		
    public static void main(String args[]){
        Main obj = new Main();
        obj.solve();
    }
}

Measured memory_bytes: 17348
S = input()
words = ["dream", "dreamer", "erase", "eraser"]
while len(S) > 0:
    flag = True
    for word in words:
        if S.endswith(word):
            flag = False
            S = S[:-len(word)]
    if flag:
        print("NO")
        exit(0)
print("YES")

Measured memory_bytes: 9124
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

using ll = long long;
struct Line { ll a, b; ll get(ll x) { return a * x + b; } };

static const int MAX = 2e5 + 9;
const ll INFL = 1e17;

struct LiChaoTree
{
	int N;
    Line a[MAX << 2];
    ll h[MAX];

    void init (ll _h[MAX], int _N)
    {
    	N = _N;
    	copy (_h, _h + N, h);
    	for (int i = 0; i < N << 2; ++i) a[i] = {0, INFL};
    }

    void upd (Line ln)
    {
        int root = 1, lo = 0, hi = N;
        while (true) {
			int mid = lo + hi >> 1;
            if (ln.get(h[mid]) < a[root].get(h[mid])) swap (ln, a[root]);
//            cerr << '[' << h[lo] << ", " << h[hi-1] << "]: " << a[root].a << ' ' << a[root].b << endl;
            if (lo + 1 >= hi) return;
            if (ln.get(h[lo]) < a[root].get(h[lo])) root = root << 1, hi = mid;
            else root = root << 1 | 1, lo = mid;
        }
    }

    ll get (int x)
    {
        int root = 1, lo = 0, hi = N; ll ans = INFL;
        while (true) {
        	int mid = lo + hi >> 1;
            ans = min(ans, a[root].get(h[x]));
            if (lo + 1 >= hi) return ans;
            if (x < mid) root = root << 1, hi = mid;
            else root = root << 1 | 1, lo = mid;
        }
    }

} tree;

int N;
ll C, h[MAX], f;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> C;
    for (int i = 0; i < N; ++i) cin >> h[i];
    tree.init(h, N);

    for (int i = 0; i < N; ++i) {
        f = (i == 0) ? 0ll : (tree.get(i) + h[i] * h[i] + C);
        if (i == N-1) return cout << f << endl, 0;
//        cout << f << ' ';
        tree.upd({-2 * h[i], f + h[i] * h[i]});
    }
}


Measured memory_bytes: 15872
// TEST
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(v)";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
var mod = 1e9+7;
function abmod(){for(var a=arguments,r=a[0],i=1;i<a.length;)r=((r>>16)*a[i]%mod*65536+(r&65535)*a[i++])%mod;return r;}
 
console.log(main());
function main(){
  var n = o.a();
  var x = o.a();
  var s = o.l().sort((a,b)=>b-a);
  var dp = Array(x+1).fill(0);
  dp[x] = 1;
  for (var i = 0; i < n; i++){
    var dp2 = Array(x+1).fill(0);
    for(var j = 0; j <= x; j++){
      dp2[j] += dp[j] * (n-i-1);
      dp2[j] %= mod;
      var m = j % s[i];
      dp2[m] += dp[j];
      dp2[m] %= mod;
    }
    dp = dp2;
  }
  var ans = 0;
  for(i = 0; i < s[n-1]; i++){
    ans += abmod(i,dp[i]);
  }

  return ans % mod;
}

Measured memory_bytes: 42004
#include <iostream>
using namespace std;
int main() {
	long int a, b, c, ans;
	cin >> a >> b >> c;
	if (b > c) ans = 0;
	else if (a == 1 && b != c) ans = 0;
	else if (a == 1) ans = 1;
	else ans = (a - 2)*(c - b) + 1;

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int Gcd(int a, int b)
{
	int buf;
	
	if (a < b){
		buf = b;
		b = a;
		a = buf;
	}
	
	if (b == 0) return (a);
	return (Gcd(b, a % b));
}

int main(void)
{
	int a;
	int b;
	int lcm;
	int gcd;
	
	while (scanf("%d %d", &a, &b) != EOF){
		gcd = Gcd(a, b);
		
		lcm = (a / gcd) * b;
		
		printf("%d %d\n", gcd, lcm);
	}
	
	return (0);
}

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

int main() {
    int N;
    std::cin >> N;

    std::vector<int> T(N + 1, 0);
    std::vector<int> X(N + 1, 0);
    std::vector<int> Y(N + 1, 0);
    for (int i = 1; i <= N; i ++) {
        std::cin >> T[i] >> X[i] >> Y[i];
    }

    bool can_travel = true;
    for (int i = 1; i <= N; i ++) {
        int min_steps = X[i] - X[i - 1] + Y[i] - Y[i - 1];
        int time = T[i] - T[i - 1];
        if (min_steps > time || (min_steps - time) % 2 != 0) {
            can_travel = false;
            break;
        }
    }
    std::cout << (can_travel ? "Yes" : "No") << std::endl;
}


Measured memory_bytes: 1408
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>

#define fo(i,j,l) for(int i=j;i<=l;i++)
#define fd(i,j,l) for(int i=j;i>=l;i--)
#define rep(i,j) for(int i=la[j];i;i=ne[i])

using namespace std;
typedef long long ll;
const ll N=5e5+1e3,M=2*N;
int n,m,k,l,o,a,w1,w2,oo,kk;
int q[N],ne[M],lb[M],la[N],t[M*2],d[N],ans[N],p[N];
set<int> op;

void read(int &o)
{
	o=0; char ch=' ';
	for(;ch<'0'||ch>'9';)ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())o=o*10+ch-48;
}

void write(int o)
{
	int kt=0; char ch[20];
	for(;o;o/=10)ch[++kt]='0'+o%10;
	fd(i,kt,1)printf("%c",ch[i]);
	printf("\n");
}

int min(int a,int b)
{if(a<b)return a;else return b;}

int max(int a,int b)
{if(a>b)return a;else return b;}

void jl(int o,int l,int r)
{
    t[o]=n+1; if(l==r)return;
	int mid=(l+r)/2;
	jl(o*2,l,mid); jl(o*2+1,mid+1,r); 
}

void change(int o,int l,int r)
{
	if(l==r&&l==w1){t[o]=w2; return;}
	if(l>w1||r<w1)return;
	int mid=(l+r)/2;
	change(o*2,l,mid); change(o*2+1,mid+1,r);
	if(t[o*2]<t[o*2+1])t[o]=t[o*2];else t[o]=t[o*2+1];
}

void question(int o,int l,int r)
{
	if(l>=w1&&r<=w2){
		if(t[o]<kk)kk=t[o];
		return;
	}
	if(l>w2||r<w1)return;
	int mid=(l+r)/2;
	question(o*2,l,mid); question(o*2+1,mid+1,r);
}

void llb(int a,int b)
{ne[++oo]=la[a]; lb[oo]=b; la[a]=oo; d[b]++;}

void doing()
{
	jl(1,1,n);
	fd(i,n,1){
        kk=n+1; w1=p[i]; w2=min(p[i]+k-1,n);
		question(1,1,n);
		if(kk!=n+1)llb(p[i],p[kk]);
		kk=n+1; w1=max(1,p[i]-k+1); w2=p[i];
		question(1,1,n);
		if(kk!=n+1)llb(p[i],p[kk]);
		w1=p[i]; w2=i;
		change(1,1,n);
	}
	fo(i,1,n)if(!d[i])op.insert(i);
	fo(i,1,n){
		int y=ans[i]=*op.begin(); op.erase(y);
		rep(j,y)
		if(!(--d[lb[j]]))op.insert(lb[j]);
	}
	fo(i,1,n)p[ans[i]]=i;
	fo(i,1,n)write(p[i]);
}

void intt()
{
	cin>>n>>k;
	fo(i,1,n)
	read(a),p[a]=i;
}

int main()
{
	intt();
	doing();
}

Measured memory_bytes: 37248
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
  int64_t N;
  cin >> N;
  
  unordered_map<string, int64_t> rec;
  for (int n = 0; n < N; ++n) {
    string S;
    cin >> S;
    ++rec[S];
  }
  cout << "AC x " << rec["AC"] << endl;
  cout << "WA x " << rec["WA"] << endl;
  cout << "TLE x " << rec["TLE"] << endl;
  cout << "RE x " << rec["RE"] << endl;

  return 0;
}


Measured memory_bytes: 3632