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

int n;
int h[N], a[N];

long long t[N * 4];
void ubd(int tl, int tr, int x, long long y, int pos)
{
    if (tl == tr)
    {
        t[pos] = y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
long long qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), pos * 2),
     qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

long long dp[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &h[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = qry(1, n, 1, h[i], 1) + a[i];
        ubd(1, n, h[i], dp[i], 1);
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9600
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	sc.Buffer(make([]byte, 0), 1e6) // maxTokenSize
	sc.Split(bufio.ScanWords)
	defer out.Flush()
	/* --- code --- */
	n, x, t := nextInt(), nextInt(), nextInt()

	var ans int
	if n%x == 0 {
		ans = (n / x) * t
	} else {
		ans = ((n / x) + 1) * t
	}
	fmt.Println(ans)

}

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func split(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}

// -*-*-*-*-*-*-*-*-
// * tool snippets *
// -*-*-*-*-*-*-*-*-
func duplicate2Int(base [][]int) (ret [][]int) {
	ret = make([][]int, len(base))
	for i, v := range base {
		ret[i] = append([]int{}, v...)
	}
	return
}

func max(a, b int) int {
	return int(max64(int64(a), int64(b)))
}

func max64(a int64, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func min(a, b int) int {
	return int(min64(int64(a), int64(b)))
}

func min64(a int64, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
// * math flavor typical theories *
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
func gcd(a, b int) int {
	if a > b {
		return gcd(b, a)
	}
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func pow(a, b int) (ret int) {
	ret = a
	for i := 0; i < b-1; i++ {
		ret *= a
	}
	return
}

func powMod(n, m, mod int) (ret int) {
	ret = 1
	for m > 0 {
		if m&1 == 1 {
			ret *= n
			ret %= mod
		}
		n *= n
		n %= mod
		m >>= 1
	}
	return ret
}


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

int main() {
  int N, K, Q, A;
  cin >> N >> K >> Q;
  vector<int> V(N, K - Q);
  while (cin >> A) V.at(A - 1)++;
  for (auto v : V) cout << ((v > 0) ? "Yes" : "No") << "\n";  
}

Measured memory_bytes: 1024
fun main(Args: Array<String>) {
    val s = readLine() ?: return

    val year = s.substring(0..3).toInt()
    if (year > 2019) {
        println("TBD")
        return
    }
    if (year < 2019) {
        println("Heisei")
        return
    }

    val month = s.substring(5..6).toInt()
    if (month > 4) {
        println("TBD")
        return
    }
    println("Heisei")
}

Measured memory_bytes: 33684
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;

int main(){
    FIO;
    ll n, q;
    cin >> n >> q;
    vector<ll> adj[n+1];
    ll power[n+1];
    bool visited[n+1];
    for(ll i = 1 ; i < n ; i++){
        ll x, y;
        power[i] = 0;   visited[i] = false;
        cin >> x >> y;
        adj[x].push_back(y);    adj[y].push_back(x);
    }
    power[n] = 0;
    visited[n] = false;
    while(q--){
        ll v, x;
        cin >> v >> x;
        power[v] += x;
    }
    queue<pair<ll, ll> > qu;
    qu.push({1, 0});
    ll ans[n+1];
    while(qu.size()){
        pair<ll, ll> cur = qu.front();
        qu.pop();
        visited[cur.first] = true;
        cur.second += power[cur.first];
        for(ll i = 0 ; i < adj[cur.first].size() ; i++){
            if(!visited[adj[cur.first][i]]){
                qu.push({adj[cur.first][i], cur.second});
            }
        }

        ans[cur.first] = cur.second;
    }
    for(ll i = 1 ; i <= n ; i++){
        cout << ans[i] << " ";
    }
    return 0;
}


Measured memory_bytes: 21360
import math

a, b, x = map(int, input().split())
if x / a >= a * b / 2:
    h = 2 * (b - x / a ** 2)
    r = math.atan2(h, a)
else:
    w = 2 * (x / (a * b))
    r = math.atan2(b, w)

print(180 * r / math.pi)



Measured memory_bytes: 3188
// 2020-06-26 20:34:13
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = int_fast64_t;
using ull = unsigned long long;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

const int MAX_N = 500;
int n;
vector<int> s[2], w[2];
vector<ull> u[2];
vector<vector<int>> g;

void flip() {
  rep(i, n) rep(j, i) swap(g[i][j], g[j][i]);
}
bool solve() {
  g.assign(n, vector<int>(n, -1));
  rep(k, 2) {
    rep(i, n) {
      int x = w[k][i];
      if(s[k][i] != x) {
        rep(j, n) {
          if(g[i][j] == -1) g[i][j] = x;
          else if(g[i][j] != x) return false;
        }
      }
    }
    flip();
  }
  rep(_, 2) {
    rep(k, 2) {
      rep(i, n) {
        int x = w[k][i];
        if(s[k][i] == x) {
          bool ok = false;
          vector<int> idx;
          rep(j, n) {
            if(g[i][j] == x) ok = true;
            else if(g[i][j] == -1) idx.emplace_back(j);
          }
          if(!ok) {
            if(idx.size() == 0) return false;
            else if(idx.size() == 1) g[i][idx[0]] = x;
          }
        }
      }
      flip();
    }
  }
  vector<int> is, js;
  rep(k, 2) {
    rep(i, n) {
      rep(j, n) {
        if(g[i][j] == -1) {
          if(k == 0) is.push_back(i);
          else js.push_back(i);
          break;
        }
      }
    }
    flip();
  }
  rep(i, is.size()) rep(j, js.size()) {
    g[is[i]][js[j]] = (i+j) % 2;
  }
  return true;
}
void answer() {
  cin >> n;
  rep(i, 2) {
    s[i].resize(n);
    rep(j, n) cin >> s[i][j];
  }
  rep(i, 2) {
    u[i].resize(n);
    w[i].resize(n);
    rep(j, n) cin >> u[i][j];
  }
  vector<vector<ull> > ans(n, vector<ull>(n, 0));
  rep(d, 64) {
    rep(i, 2) {
      rep(j, n) w[i][j] = (u[i][j] >> d) & 1;
    }
    if(solve()) {
      rep(i, n) rep(j, n) ans[i][j] |= (ull(g[i][j]) << d);
    } else {
      cout << -1 << "\n";
      return;
    }
  }
  rep(i, n) {
    rep(j, n) {
      if(j) cout << " ";
      cout << ans[i][j];
    }
    cout << "\n";
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 8600
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main(){
    int l;
    cin >> l;
    stack<int> st;
    vector<bool> used(101,false);
    for(int i=0;i<l;i++){
        int c;
        cin >> c;
        if(c > 0){
            if(used[c] == true){
                cout << i+1 << endl;
                return 0;
            }
            used[c] = true;
            st.push(c);
        }
        else{
            if(st.empty() || st.top() != abs(c)){
                cout << i+1 << endl;
                return 0;
            }
            st.pop();
            used[abs(c)] = false;
        }
    }
    cout << "OK" << endl;
    return 0;
}




Measured memory_bytes: 3092
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];

	for (int i = 0; i < N; i++) {
		A[i] = i - A[i];
	}
	A.emplace_back(INF); //番兵
	DMP(A);

	lint ans = 0;
	for (int i = 0; i < N; i++) {

		if (A[i] > A[i + 1] || A[i] < 0) {
			cout << -1 << "\n";
			return 0;
		}
		
		if (A[i] != A[i + 1]) ans += i - A[i];

	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 1920
N,K=map(int,input().split())
h=[int(input()) for _ in range(N)]
h.sort(reverse=True)
min=float("inf")
#print(h)
for i in range(N-(K-1)):
    #print(h[i],h[i+K-1])
    if min>(h[i]-h[i+K-1]):
        min=h[i]-h[i+K-1]
print(min)

Measured memory_bytes: 50264
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int num = 30;
  
  // ここにプログラムを追記
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    
    int a = A;
    int j = 0;
    
    while (a % 2 == 0) {
       j ++;
       a /= 2;
    }
    if (j < num) {
      num = j; 
    }
  }
  
  cout << num << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()

{
    int n;

    scanf("%d", &n);

    if(n%10==7){

        printf("Yes\n");
    }

    else if((n/10)%10==7){
        printf("Yes\n");
    }

    else if(n/100 == 7){
        printf("Yes\n");
    }

    else
        printf("No\n");
    return 0;
}

Measured memory_bytes: 1644
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int INF = int(1E9);
int arr[MAXN + 5], sum[MAXN + 5], temp[MAXN + 5];
long long tot1 = 0, tot2 = 0;
int N;
void MergeSort(int le, int ri) {//归并排序求 区间内多少序列和为正数 即s[r] >s[l]且r>l  
    if( le == ri ) return ;
    int mid = (le + ri) >> 1;
    MergeSort(le, mid);
    MergeSort(mid+1, ri);
    int p = le, q = mid+1, r = le;
    while( p <= mid && q <= ri ) {
        if( sum[p] < sum[q] ) {  
            temp[r++] = sum[p++];
        }
        else {    //当s[p]>=s[q]时 说明P前面的数是小于S[Q]的 
            tot1 += (p-le);
            temp[r++] = sum[q++];
        }
    }
    while( p <= mid ) {
        temp[r++] = sum[p++];
    }
    while( q <= ri ) {   //P已经排结束 说明  剩下的Q 都比P前面的数大
        tot1 += (p-le);
        temp[r++] = sum[q++];
    }
    for(int i=le;i<=ri;i++)
        sum[i] = temp[i];
}
bool Check(int x) {
    tot1 = 0;
    for(int i=1;i<=N;i++)
        sum[i] = (arr[i] <= x ? 1 : -1);
    for(int i=1;i<=N;i++)
        sum[i] += sum[i-1];
    MergeSort(0, N);
    return tot1 >= (tot2/2 + 1); 
}
int main() {
    int le = INF, ri = -INF;
    scanf("%d", &N);
    for(int i=1;i<=N;i++) { 
        scanf("%d", &arr[i]);
        le = min(le, arr[i]);
        ri = max(ri, arr[i]);
        tot2 += i; //总序列数 (n+1)*n/2
    }
    while( le < ri ) {
        int mid = (le + ri) >> 1;
        if( Check(mid) ) ri = mid;
        else le = mid + 1;
    }
    printf("%d\n", ri);
}
/*  举例 10 20 20 30 30 30  中位数为30 说明<=中位数的数至少有L/2+1  
 二分枚举中位数x 本题每个数都是一个区间的中位数 ，实质就是求有多少个区间中位数小于等于x
 继续转化原序列中大于x的为1 反之-1 则求有多少个序列的和是正数  预处理前缀和 归并排序 求出 序列和为正数的个数*/ 

Measured memory_bytes: 1408
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		String[] s = new String[n];
		for(i=0;i<n;i++) {
			s[i] = sc.next();
		}
		sc.close();
		String[] s2;
		for(i=0;i<n;i++) {
			s2 = s[i].split("");
			Arrays.sort(s2);
			s[i] = String.join("", s2);
		}
		HashMap<String, Integer> c = new  HashMap<>();
		for(i=0;i<n;i++) {
			if(c.containsKey(s[i])) {
				c.put(s[i], c.get(s[i])+1);
			} else {
				c.put(s[i], 1);
			}
		}
		long ans=0;
		for (Integer ii : c.values()) {
			ans += (long)ii*(ii-1)/2;
		}
		out.println(ans);
	}
}


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

int main()
{
	string S;

	cin >> S;

	map<int, int> m;
	for( int i = 0; i < S.size(); i++ ) {
		m[S[i]]++;
	}
	string ans = "Yes";
	for( auto it = m.begin(); it != m.end(); it++ ) {
		if( (*it).second != 2 ) {
			ans = "No";
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    double xa, ya, ra, xb, yb, rb;
    cin >> xa >> ya >> ra >> xb >> yb >> rb;
    double d = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
    if (d+ra < rb) cout << -2 << endl;
    else if (d+rb < ra) cout << 2 << endl;
    else if (d <= ra+rb) cout << 1 << endl;
    else cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 0
// Problem : C - Tsundoku
// Contest : AtCoder - AtCoder Beginner Contest 172
// URL : https://atcoder.jp/contests/abc172/tasks/abc172_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)


#include <bits/stdc++.h> 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define l00p(i, a, b) for (int i=a; i<(b); i++)
#define loop(i, a) for (int i=0; i<(a); i++)
#define rep1(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define imax INT_MAX
#define imin INT_MIN
//#define MOD 998244353
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
const int MOD = 1000000007;
const char nl = '\n';
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}

int main() {
	 
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int t=1;
	while(t--)
	{
		ll n,m,k;
		int ans=0;
		cin>>n>>m>>k;
		vl a(n+1),b(m+1);
		a[0]=0;
		b[0]=0;
		l00p(i,1,n+1)
			cin>>a[i];
		l00p(i,1,m+1)
			cin>>b[i];
		//int ma=0,mb=0,mc=0;
		for(int i=1;i<=n;i++)
			a[i]+=a[i-1];
		for(int i=1;i<=m;i++)
			b[i]+=b[i-1];
		
		for(int i=0;i<=n;i++)
		{
			if(a[i]<=k)
			{
				int l=0,r=m+1;
				while(l+1<r)
				{
					int x=(l+r)/2;
					if(a[i]+b[x]<=k)
						l=x;
					else
						r=x;
				}
				ans=max(ans,i+l);
			}
			
		}
    cout<<ans;
    }
    
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,K;cin>>A>>B>>K;
  if(A+K-1>=B-K+1)
    for(int i=A;i<=B;i++)
      cout<<i<<endl;
  else{
    for(int i=A;i<A+K;i++)cout<<i<<endl;
    for(int i=B-K+1;i<=B;i++)cout<<i<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,a=0;cin>>N;
  vector<string>s(N);
  vector<int>t(N);
  for(int i=0;i<N;i++)cin>>s.at(i)>>t.at(i);
  string X;cin>>X;
  int i=0;while(s.at(i)!=X)i++;
  for(i++;i<N;i++)a+=t.at(i);
  cout<<a<<endl;
}

Measured memory_bytes: 256
func readInts(separator: String.Element = " ") -> [Int] {
    return readLine()!.split(separator: separator).map { Int($0)! }
}

func readThreeInts(separator: String.Element = " ") -> (a: Int, b: Int, c: Int) {
    let ints = readLine()!.split(separator: separator).map { Int($0)! }
    return (a: ints[0], b: ints[1], c: ints[2])
}

struct Book {
    let price: Int
    let points: [Int]

    static func decode() -> Book {
        var array = readInts()
        return Book(price: array.removeFirst(), points: array)
    }
}

func mainC() {
    let (N, M, X) = readThreeInts()
    let books = (0..<N).map { _ in Book.decode() }

    var results: [Int] = []
    // 1 ~ 2^Nまで
    // YES/NO問題, 二進数に変換して調べる
    for i in 0...(1<<N - 1) {
        var takahasi: [Int] = .init(repeating: 0, count: M)
        var price = 0

        for j in 0..<N {
            if ((i >> j) & 1) == 0 {
                takahasi = takahasi.enumerated().map { (index, element) in
                    return element + books[j].points[index]
                }
                price += books[j].price
            }
        }

        if takahasi.allSatisfy({ $0 >= X }) {
            results.append(price)
        }
    }

    if results.isEmpty {
        print(-1)
    } else {
        print(results.min()!)
    }
}
mainC()

Measured memory_bytes: 8328
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int ans = 0, big = 0, mid = 0, sma = 0;
		
		if (a >= b && a >= c) {
			// big = a;
			if (b >= c) {
				mid = a - b;
				sma = a - c;
			} else {
				mid = a - c;
				sma = a - b;
			}
		} else if (b >= a && b >= c) {
			// big = b;
			if (a >= c) {
				mid = b - a;
				sma = b - c;
			} else {
				mid = b - c;
				sma = b - a;
			}
		} else {
			// big = c;
			if (b >= a) {
				mid = c - b;
				sma = c - a;
			} else {
				mid = c - a;
				sma = c - b;
			}
		}
		
		while (sma > 0) {
			if (mid > 0 && sma > 0) {
				mid--;
				sma--;
				ans++;
			} else {
				sma -= 2;
				ans++;
			}
		}
		
		if (sma != 0) {
			ans++;
		}
		
		System.out.println(ans);

		sc.close();
	}
}


Measured memory_bytes: 23764
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
ll point[100005];
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	int n;
	ll x;
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> point[i];
		point[i] = abs(x - point[i]);
	}
	ll ans = point[0];
	for (int i = 1; i < n; i++) {
		ans = gcd(ans, point[i]);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1024
def examD():
    X, Y =LI()
    if abs(X-Y)<=1:
        ans = "Brown"
    else:
        ans = "Alice"
    print(ans)

import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


Measured memory_bytes: 3444
open Batteries
let h = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> a)

let rec ans n =
  match n with
   0 -> ""
  | _ -> let a = read_line() in a ^ "\n" ^ a ^ "\n" ^ ans (n-1)

let _ = print_endline (ans h)

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

int main()
{
    int n;
    cin>>n;
     string a,b;
     cin>>a>>b;
     string t;
     for(int i=0;i<n;i++)
      t+=a[i],t+=b[i];
      cout<<t;
         return 0;
}

Measured memory_bytes: 256
s = input()

def is_kaibun(kaibun):
    for i in range(len(kaibun)//2):
        if kaibun[i] != kaibun[-i-1]:
            return False
    return True

if not is_kaibun(s):
    print('No')
    exit()
# print(s[:(len(s)-1)//2])
if not is_kaibun(s[:(len(s)-1)//2]):
    print('No')
    exit()
# print(s[(len(s)+3)//2-1:])
if not is_kaibun(s[(len(s)+3)//2-1:]):
    print('No')
    exit()

print('Yes')


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


int main(void)
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    vector<int> cost(N+1);
    cost[0] = A[0] - 0;
    for(int i = 0; i < N-1; i++){
        cost[i+1] = A[i+1] - A[i];
    }
    cost[N] = 0 - A[N-1];


    int sum = 0;
    for(int i = 0; i < N+1; i++){
        sum += abs(cost[i]);
    }
    for(int i = 0; i < N; i++){
        int tot = sum;
        tot -= (abs(cost[i]) + abs(cost[i+1]));
        tot += abs(cost[i] + cost[i+1]);
        cout << tot << endl;
    }
    
    return 0;
}


Measured memory_bytes: 4052
p = [0 for x in range(999999)]
for x in xrange(1,999999,2):
        z = int(x**0.5)+1
        for y in xrange(3,z,2):
                if x % y == 0:
                        break
        else:
                p[x] = 1
p[1], p[2] = 0, 1

while 1:
        try:
                n = input()
                print sum(p[:n+1])
        except EOFError:
                break

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

const int MAX_STRING_SIZE = 2000000;

ll base = 1007;

vector<ll> MODS({2147483647, 6700417, 524287, 1000000007}

);

vector<vector<ll>> invs(MODS.size()), pows(MODS.size());

ll powm(ll e, ll x, ll m) {
  if (x == 0) return 1;
  if (x == 1) return e;
  if (x % 2 == 0) return powm((e * e) % m, x / 2, m);
  return (e * powm(e, x - 1, m)) % m;
}

void RHinit() {
  int i = 0;
  for (auto &p : MODS) {
    invs[i].resize(MAX_STRING_SIZE + 1);
    invs[i][0] = 1;
    ll inv = powm(base, p - 2, p);
    for (int j = 1; j <= MAX_STRING_SIZE; j++) {
      invs[i][j] = (invs[i][j - 1] * inv) % p;
    }
    pows[i].resize(MAX_STRING_SIZE + 1);
    pows[i][0] = 1;
    for (int j = 1; j <= MAX_STRING_SIZE; j++) {
      pows[i][j] = (pows[i][j - 1] * base) % p;
    }
    i++;
  }
}

struct RH {
  int n;
  string s;
  vector<vector<ll>> hs;

  RH(string &s) : s(s) {
    if (pows[0].empty()) {
      RHinit();
    }
    n = s.size();
    hs.resize(MODS.size());
    for (int i = 0; i < MODS.size(); i++) {
      hs[i].resize(n + 1);
      hs[i][0] = 0;
      for (int j = 0; j < n; j++) {
        hs[i][j + 1] = (hs[i][j] + pows[i][j] * s[j]) % MODS[i];
      }
    }
  }

  vector<ll> substr(int l, int r) {
    vector<ll> ret(MODS.size());
    for (int i = 0; i < MODS.size(); i++) {
      ret[i] = (hs[i][r] - hs[i][l] + MODS[i]) % MODS[i];
      ret[i] *= invs[i][l];
      ret[i] %= MODS[i];
    }
    return ret;
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s, t;
  cin >> s >> t;

  RHinit();
  int m = s.size();
  for (int l = s.size(), i = 0; i < l; i++) s.push_back(s[i]);
  string u = s;
  while (u.size() < t.size()) {
    for (int l = u.size(), i = 0; i < l; i++) u.push_back(u[i]);
  }
  for (int l = u.size(), i = 0; i < l; i++) u.push_back(u[i]);
  RH uh(u), th(t);
  vector<bool> ok(u.size());
  for (int i = 0; i < u.size() - t.size(); i++) {
    ok[i] = uh.substr(i, i + t.size()) == th.substr(0, t.size());
  }
  for (int i = u.size() - t.size(); i < u.size(); i++) {
    int r = u.size() - i;
    ok[i] = (uh.substr(i, u.size()) == th.substr(0, r)) &&
            (uh.substr(0, t.size() - r) == th.substr(r, t.size()));
  }
  int ans = 0;
  vector<bool> used(u.size());
  for (int i = 0; i < t.size(); i++) {
    if (used[i]) continue;
    int c = 0;
    bool all = true;
    for (int j = i; !used[j]; (j += t.size(), j %= u.size())) {
      used[j] = true;
      if (ok[j]) {
        c++;
        ans = max(ans, c);
      } else {
        all = false;
        c = 0;
      }
    }
    if (all) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 211656
import Text.Printf

ans :: (Double,Double) -> (Double,Double) -> (Double,Double) -> [Double]
ans (x1,y1) (x2,y2) (x3,y3) =
  -- (x1-xp)^2 + (y1-yp)^2 = a
  -- (x2-xp)^2 + (y2-yp)^2 = a
  -- (x3-xp)^2 + (y3-yp)^2 = a

  -- x1^2 - 2*x1*xp + xp^2 + y1^2 - 2*y1*yp + yp^2 = a
  -- x2^2 - 2*x2*xp + xp^2 + y2^2 - 2*y2*yp + yp^2 = a
  -- x3^2 - 2*x3*xp + xp^2 + y3^2 - 2*y3*yp + yp^2 = a

  -- x1^2-x2^2 - 2*(x1-x2)*xp + y1^2-y2^2 - 2*(y1-y2)*yp = 0
  -- x1^2-x3^2 - 2*(x1-x3)*xp + y1^2-y3^2 - 2*(y1-y3)*yp = 0

  -- A2 - B2 * xp + C2 - D2 * yp = 0
  -- A3 - B3 * xp + C3 - D3 * yp = 0

  -- A2*D3 - B2*D3*xp + C2*D3 - A3*D2 + B3*D2*xp - C3*D2 = 0
  -- xp = (A2*D3 + C2*D3 - A3*D2 - C3*D2) / (B2*D3-B3*D2)
  -- yp = (A2 + C2 - B2*xp) / D2

  let a2 = x1^2 - x2^2
      b2 = 2*(x1-x2)
      c2 = y1^2 - y2^2
      d2 = 2*(y1-y2)
      a3 = x1^2 - x3^2
      b3 = 2*(x1-x3)
      c3 = y1^2 - y3^2
      d3 = 2*(y1-y3)

      xp = (a2*d3 + c2*d3 - a3*d2 - c3*d2) / (b2*d3-b3*d2)
      yp = if d2 /= 0
           then (a2+c2-b2*xp) / d2
           else (a3+c3-b3*xp) / d3
      r  = sqrt ( (x1-xp)^2 + (y1-yp)^2 )
  in
    [xp,yp,r]

main = do
  c <- getContents
  let i = map (map read) $ map words $ drop 1 $ lines c :: [[Double]]
      o = map (\(x1:y1:x2:y2:x3:y3:_) -> ans (x1,y1) (x2,y2) (x3,y3)) i
  mapM_ (\x -> printf "%.3f %.3f %.3f\n" (x!!0) (x!!1) (x!!2) ) o

Measured memory_bytes: 4408
A,B,C=map(x->parse(Int,x),split(readline()," "))

d=gcd(A,B,C)

A=div(A,d)
B=div(B,d)
C=div(C,d)

a = sqrt(big(A))
if (Int(ceil(a))^2==A )
  (a = Int(ceil(a)))
elseif (Int(floor(a))^2==A )
  (a  =Int(floor(a)))
end
b = sqrt(big(B))
if (Int(ceil(b))^2==B )
  (b = Int(ceil(b)))
elseif (Int(floor(b))^2==B )
  (b  =Int(floor(b)))
end
c = sqrt(big(C))
if (Int(ceil(c))^2==C )
  (c = Int(ceil(c)))
elseif (Int(floor(c))^2==C )
  (c  =Int(floor(c)))
end

an = (a+b < c ) ? "Yes" : "No"
print(an)

Measured memory_bytes: 169640
// https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c

#include "algorithm"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll X;
  cin >> X;

  ll t = X / 100;
  ll r = X % 100;

  if (r <= 5 * t) drop(1);
  drop(0);
}

void solve2() {
  ll X;
  cin >> X;

  rep(c, X) {
    if (100 * c <= X && X <= 105 * c) drop(1);
  }

  drop(0);
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve2();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 256
i=59,c=100,f[],m,x,s;main(y){for(;s?++f[y*12+x+";<=0H/1GI:>T$"[--s]]:~scanf("%d,%d,%d",&x,&y,&s)?s=s*4+1:++i<178?i%12<10?m=fmax(m,f[i]),f[i]?c--:1:1:!printf("%d\n%d\n",c,m););}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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; }
const ll MOD = 1e9+7;

int main(){
    ll N;
    cin >> N;
    ll sum = 0;
    vector<ll> A(N);
    vector<ll> B(N);
    bool same = true;
    REP(i,N){
        ll a, b;
        cin >> a >> b;
        A[i] = a;
        B[i] = b;
        if(a != b) same = false;
        sum += a;
    }

    if(same){
        cout << 0 << endl;
        return 0;
    }

    ll ans = LLONG_MAX;
    REP(i,N){
        ll a, b;
        a = A[i];
        b = B[i];
        if(a > b){
            chmin(ans, b);
        }
    }

    ans = sum - ans;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    
    
	 long long n,i,j,k,sum=0,count=0,ans=0,x,y,l,r,m;
     cin>>x>>y>>n;
     if(y==1)
     {
         cout<<0; return 0;
     }
     if(n>(y-1))
     {
         n=y-1;
     }
     cout<<(x*n)/y-x*(n/y);
}

Measured memory_bytes: 3636
#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 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


int main() {
  vll v(6);
  FOR(i,0,6){
    cin>>v[i];
  }
//  bool a=false,b=false,c=false,d=false;
  vll count(4);
  FOR(i,0,6){
    if(v[i]==1) count[0]++;
    if(v[i]==2) count[1]++;
    if(v[i]==3) count[2]++;
    if(v[i]==4) count[3]++;
  }
  ll bns=1;
  FOR(i,0,4){
    bns*=count[i];
  }
  if(bns==4){
    co("YES");
  }
  else{
    co("NO");
  }
}


Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end
require 'bigdecimal'

N = get_int
V = get_ints

vx = V.sort
ans = vx[0]

1.step(N-1) do |i|
  ans = (ans + BigDecimal(vx[i])) / 2
end

puts ans.to_f


Measured memory_bytes: 14520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
//next_permutation(ALL(p));
//typedef priority_que<int> pque;//これは大きい順
//typedef priority_que<int, vector<int>, greater<int>> pque;//これは小さい順

bool isPrime(int x){
	if(x == 1){
		return false;
	}else{
		for(int i=2; i*i<=x; i++){
			if(x%i == 0) return false;
		}
	}
	return true;
}

int main(){
	int x;
	cin >> x;
	int p=x;
	while(!isPrime(p)) p++;
	cout << p << endl;


  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(input())
    hs = list(map(int, input().split()))

    dp = []
    for i, h in enumerate(hs):
        if i == 0:
            dp.append(0)
        elif i == 1:
            dp.append(dp[i-1] + abs(hs[i-1] - hs[i]))
        else:
            cost = min([
                dp[i-1] + abs(hs[i-1] - hs[i]),
                dp[i-2] + abs(hs[i-2] - hs[i]),
            ])
            dp.append(cost)

    print(dp[-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 21524
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

P, Q, R = MAP()

print(min(P+Q, P+R, Q+R))

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


typedef pair<int, int> pi;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define sq(i) (a)*(a)



int main()
{

	ios_base::sync_with_stdio(0);	
	cin.tie(0);			
	cout.tie(0);	
	
	ll n; cin >> n;
	ll sum = 0;
	for(int i = 0; i <= n; i++){
		
		if((i%3 !=0)and( i%5 != 0 ))
		{
			sum += i;
			
			
			}

		}
		cout << sum;
	
}


Measured memory_bytes: 3600
#include <stdio.h>

#define MAX 100


typedef struct {
	char sign;
	int value;
}Card;

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

void change_char(char *a, char *b) {
	char temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
int selectionSort(Card a[], int n)
{
	int i,j;
	int cnt = 0;
	for (i = 0; i < n; i++) {
		int minj = i;
		for (j = i; j < n; j++) {
			if (a[j].value < a[minj].value)
				minj = j;
		}
		if (minj != i) {
			change_int(&a[i].value, &a[minj].value);
			change_char(&a[i].sign, &a[minj].sign);
			cnt++;
		}
	}
	return cnt;
}

int bubbledSort(Card a[], int n)
{
	int flag = 1;
	int j;
	int cnt = 0;
	while (flag) {
		flag = 0;
		for (j = n - 1; j > 0; j--) {
			if (a[j].value < a[j - 1].value) {
				change_int(&a[j].value, &a[j - 1].value);
				change_char(&a[j].sign, &a[j - 1].sign);
				cnt++;
				flag = 1;
			}
		}
	}
	return cnt;
}


void print_a(Card a[], int n) {
	int i;
	for (i = 0; i < n - 1; i++) {
		printf("%c", a[i].sign);
		printf("%d ", a[i].value);
		
	}
	printf("%c%d\n",a[n-1].sign, a[n - 1].value);
}

void conversion(char s[][3],Card card[],int n) {
	int i;
	for (i = 0; i < n; i++) {
		card[i].sign = s[i][0];
		card[i].value = (int)s[i][1] - '0';
	}
}

int isStable(Card a[], Card b[],int n) {
	int i,flag;
	flag = 1;
	for (i = 0; i < n; i++) {
		if (a[i].sign != b[i].sign || a[i].value != b[i].value)
			flag = 0;
	}
	return flag;
}
int main()
{
	int n,i,cnt;

	char s[MAX][3];


	Card card1[MAX];

	Card card2[MAX];

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	
	conversion(s, card1, n);
	bubbledSort(card1, n);
	print_a(card1, n);
	printf("Stable\n");
	conversion(s, card2, n);
	selectionSort(card2, n);
	print_a(card2, n);
	if (isStable(card1,card2,n))
		printf("Stable\n");
	else
		printf("Not stable\n");
	return 0;

}


Measured memory_bytes: 2124
#include <bits/stdc++.h>
#define N 407
#define INF (1ll<<50)
using namespace std;
typedef long long ll;

ll n, pa[N], dp[N][N];

ll f(int i, int j) {
	if (i==j) return 0;
	if (dp[i][j]!=0) return dp[i][j];
	dp[i][j]=INF;
	for (int k=i; k<j; k++) {
		dp[i][j]=min(dp[i][j],f(i,k)+f(k+1,j)+pa[j]-pa[i-1]);
	}
	//printf("%d %d => %lld\n",i,j,dp[i][j]);
	return dp[i][j];
}


int main() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>pa[i];
		pa[i]+=pa[i-1];
	}
	cout<<f(1,n)<<endl;
}

Measured memory_bytes: 1536
import math
n=int(input())
mi=1/100000000
x=1
y=0
pi=math.pi
cnt=1
while abs(x)>mi or abs(y)>mi:
  x+=math.cos(cnt*n*pi/180)
  y+=math.sin(cnt*n*pi/180)
  cnt+=1
print(cnt)


Measured memory_bytes: 9552
#include <iostream>
#include <vector>
#include <queue>
#define int long long
using namespace std;

signed main(){
	int n,m,s,t,ds[100000],dt[100000],ans = 0,scnt[100000] = {},tcnt[100000] = {};
	vector<int> G[100000];
	queue<int> que;
	cin >> n >> m >> s >> t; s--;t--;
	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);
	}
	for(int i = 0;i < n;i++){
		ds[i] = -1;
		dt[i] = -1;
	}
	ds[s] = 0;
	que.push(s);
	while(!que.empty()){
		int v = que.front();que.pop();
		for(int to : G[v]){
			if(ds[to] == -1){
				ds[to] = ds[v] + 1;
				que.push(to);
			}
		}
	}
	dt[t] = 0;
	que.push(t);
	while(!que.empty()){
		int v = que.front();que.pop();
		for(int to : G[v]){
			if(dt[to] == -1){
				dt[to] = dt[v] + 1;
				que.push(to);
			}
		}
	}
	for(int i = 0;i < n;i++){
		if(ds[i] >= 0) scnt[ds[i]]++;
		if(dt[i] >= 0) tcnt[dt[i]]++;
	}
	for(int i = 0;i < ds[t] - 1;i++){
		ans += scnt[i] * tcnt[ds[t] - i - 2];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 13596
def main():
    n = int(input())
    p = list(map(int,input().split()))
    neoP = sorted(p)
    cnt = 0
    for i in range(len(p)):
        if p[i] != neoP[i]:
            cnt += 1

    if cnt == 0:
        print("YES")
    elif cnt == 2:
        print("YES")
    else:
        print("NO")

main()


Measured memory_bytes: 3060
n = int(input())
s = [0] * 13
h = [0] * 13
c = [0] * 13
d = [0] * 13
deck = [s,h,c,d]
for _ in range(n):
    suit, num = input().split()
    num = int(num)
    if suit == "S":
        deck[0][num-1] = 1
    elif suit == "H":
        deck[1][num-1] = 1
    elif suit == "C":
        deck[2][num-1] = 1
    else:
        deck[3][num-1] = 1
for i in range(4):
    for num, x in enumerate(deck[i]):
        if x == 0:
            if i == 0:
                print(f"S {num+1}")
            if i == 1:
                print(f"H {num+1}")
            if i == 2:
                print(f"C {num+1}")
            if i == 3:
                print(f"D {num+1}")


Measured memory_bytes: 5620
N = int(input())
S = list(input())

left = [0] * N
right = [0] * N
temp_left = 0
temp_right = 0

for i in range(N):
    left[i] = temp_left
    if S[i] == "W":
        temp_left += 1

    right[-1-i] = temp_right
    if S[-1-i] == "E":
        temp_right += 1

ans = float("inf")
for l, r in zip(left, right):
    ans = min(ans, l + r)

print(ans)


Measured memory_bytes: 67824
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
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; }
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
const int T = 1000000001;
int main() {
	string s;
	cin >> s;
	int n = s.size();
	string t = s;
	reverse(t.begin(), t.end());
	int q;
	cin >> q;
	int i;
	bool rev = false;
	string s1 = "";
	string s2 = "";
	string sr1 = "";
	string sr2 = "";
	for (i = 0; i < q; i++) {
		int a;
		cin >> a;
		if (a == 1) {
			rev = !rev;
			string tmp = s1;
			s1 = sr2;
			sr2 = tmp;
			string tmp2 = s2;
			s2 = sr1;
			sr1 = tmp2;
		}
		else {
			int A;
			cin >> A;
			string b;
			cin >> b;
			if (A == 1) {
				s1.insert(0, b);
				sr1 += b;
			}
			else {
				s2 += b;
				sr2.insert(0, b);
			}
		}
	}
	if (rev) cout << s1 << t << s2;
	else cout << s1 << s << s2;
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
vector<int>v;
stack<int>st;
int main()
{
    ll x,y=0;
    string s;
    cin>>x>>s;
    for(int i=0;i<s.size();i++)
      if(s[i]!='.'){
         y=y*10+s[i]-'0';
      }
    ll ans=x*y;
    while(ans){
        st.push(ans%10);
        ans/=10;
    }
    while(!st.empty()){
        v.push_back(st.top());
        st.pop();
    }
    if(v.size()<=2){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<v.size()-2;i++) cout<<v[i];
    cout<<endl;
}


Measured memory_bytes: 3632
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

Measured memory_bytes: 50952
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def dfs(fr, now, num):
    global graph, addsum, ans
    tmp = num + addsum[now]
    for a in graph[now]:
        if a == fr:
            continue
        dfs(now, a, tmp)
    ans[now] = tmp


def main():
    global graph, addsum, ans
    N, Q = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    addsum = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        p -= 1
        addsum[p] += x
    
    ans = [0]*N
    dfs(-1, 0, 0)

    print(*ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 236900
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;

int main(){
    long long N, M;
    cin >> N >> M;
    vector<long long> H(N);
    vector<long long> T(N,0);

    for(int i = 0 ; i < N ; i++){
        cin >> H[i];
    }

    for(int i = 0; i < M; i++){
        long long A, B;
        cin >> A >> B;
        if( H[A-1] > H[B-1]){
            T[B-1] = 1;
        }
        else if(H[A-1] < H[B-1]) {
            T[A-1] = 1;
        }
        else{
            T[A-1] = 1;
            T[B-1] = 1;
        }
    }
    
    long long count = 0;
    for(int i = 0 ; i < N ; i++){
        // cout << T[i] << endl;
        if(T[i] == 0) count++;
    }

    cout << count << endl;
}

Measured memory_bytes: 4844
import java.util.*;

public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int l = sc.nextInt();
      ArrayList<String> list = new ArrayList<>();
      for(int i=0;i<n;i++){
        list.add(sc.next());
      }
      Collections.sort(list);
      String output = "";
      for(String s:list){
        output = output+s;
      }
      System.out.println(output);
    }
}

Measured memory_bytes: 40388
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node{
  int key;
  Node *right,*left,*parent;
};

Node *root, *NIL;

void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y==NIL){
    root = z;
  }else{
    if(z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}

void inorder(Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n,i,x;
  string com;

  scanf("%d",&n);

  for(i = 0;i < n; i++){
    cin >> com;
    if(com == "insert"){
      scanf("%d",&x);
      insert(x);
    }else if(com == "print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}


Measured memory_bytes: 26692
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 04/11/2018 13:06:56
	flamers will **** you
*/
//#include<flamers.h>

#include "bits/stdc++.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define PB push_back
#define POB pop_back

using namespace std;

int main(){
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	int n;
	cin>>n;
	double t, a;
	int index = 1;
	double mx = 1000000.0;
	cin>>t>>a;
	for(int i = 0; i < n; i++) {
		double h;
		cin>>h;
		if(abs(a - (t - h*0.006)) < mx) {
			mx = abs(a - (t - h*0.006));
			index = i+1;
		}
	}
	cout<<index<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long ll;
int main() {
  string s;
  cin >> s;
  int a = 0, b = 0;
  rep(i,s.size())
  {
    if (s[i] == 'A' || s[i] == 'G' || s[i] == 'C' || s[i] == 'T') {
      b++;
    } else {
      a = max(a, b);
      b = 0;
    }
  }
  cout << max(a, b);
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_20190707_1
{    class Program
    {
        static void Main(string[] args)
        {
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());

            for(int i = 1; i < 4; i++)
            {
                if(i != A && i != B)
                {
                    Console.WriteLine(i);
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 11092