akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	int N;
	cin >> N;

	bool flag = true;

	int pt = 0;
	int px = 0;
	int py = 0;
	rep(i, N) {
		int t, x, y;
		cin >> t >> x >> y;

		int dist = abs(x - px) + abs(y - py);
		int diffT = t - pt;

		if (dist > diffT) flag = false;
		if (dist % 2 != diffT % 2) flag = false;

		pt = t;
		px = x;
		py = y;
	}

	cout << (flag ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 256
from operator import itemgetter


def solve(n, ppp):
    qqq = sorted(enumerate(ppp), key=itemgetter(1))
    left_next_index = list(range(-1, n - 1)) + [-1, -1]
    right_next_index = list(range(1, n + 1)) + [n, n]
    ans = 0
    for i, p in qqq:
        l2 = left_next_index[i]
        l1 = left_next_index[l2]
        r1 = right_next_index[i]
        r2 = right_next_index[r1]
        ans += p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
        left_next_index[r1] = l2
        right_next_index[l2] = r1
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))


Measured memory_bytes: 26596
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 100000 + 233;
LL l[maxn],r[maxn],v[maxn],lsum[maxn],rsum[maxn],c,n,lmax1[maxn],lmax2[maxn],rmax1[maxn],rmax2[maxn];
int main(){
	scanf("%lld%lld",&n,&c);
	for(int i = 1;i <= n;++i){
		scanf("%lld%lld",&l[i],&v[i]);
		r[i] = c - l[i];
		lsum[i] = lsum[i - 1] + v[i];
	}
	for(int i = n;i >= 1;--i)rsum[i] = rsum[i + 1] + v[i];
	for(int i = 1;i <= n;++i){
		lmax1[i] = max(lmax1[i - 1],lsum[i] - l[i]);
		lmax2[i] = max(lmax2[i - 1],lsum[i] - 2*l[i]);
	}
	for(int i = n;i >= 1;--i){
		
		rmax1[i] = max(rmax1[i + 1],rsum[i] - r[i]);
		rmax2[i] = max(rmax2[i + 1],rsum[i] - 2*r[i]);
	}
	LL ans = 0;
	for(int i = 1;i <= n;++i){
		LL tmp = 0;
		tmp = max(lmax1[i],rmax1[i]);
		ans = max(ans,tmp);
		tmp = max(lmax1[i] + rmax2[i + 1],rmax1[i] + lmax2[i - 1]);
		ans = max(ans,tmp);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 7296
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let N = get!(usize);
    let p = get!(Vec<usize>);

    // (1, 2, ..., N) とpを比較し、異なる要素数が2以下ならばYes
    let x = p.iter()
        .enumerate()
        .filter(|&(i, &q)| q != i + 1)
        .count();
    let ans = if x <= 2 {
        "YES"
    } else {
        "NO"
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
import math
n, d = map(int, input().split())
p_list = []
ans = 0

for i in range(n):
    p_list.append(list(map(int, input().split())))

# 探索する
for i in range(len(p_list)):
    for j in range(i+1, len(p_list)):
        dis = 0
        for k in range(d):
            dis += (p_list[i][k] - p_list[j][k]) ** 2
        #print(math.sqrt(dis))
        t_dis = math.sqrt(dis)
        #print(round(t_dis), t_dis, round(t_dis) == t_dis)
        if round(t_dis) == t_dis:
            ans += 1

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include<vector>

using namespace std;
typedef long long ll;

bool check(ll n){ 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true;
    if (n % 2 == 0 || n % 3 == 0) 
        return false;  
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
} 

ll ans,mx,sum,mn=1e18,cnt;
ll flag;

int main(){
	ll n,m;
	cin>>n>>m;
	if(n==1 ){ 
		cout<<m;
		return 0;
	}
	for(ll i=1; i<=m/n; i++){
		ll flag=i*n;
		if(flag <=m){
			ll temp=m-flag;
			if(temp%i==0) {
				mx=max(mx,i);
			}
		}
	}
	// if(check(m)==1) cout<<1<<endl;
	 cout<<mx<<endl;
}



Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <climits>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;
const int MAX_N = 110;
const int MAX_V = 100100;
// dp[i][sum_v] : i - 1番目まででvの和がsum_vを超えるようなwの和の最小値
ll dp[MAX_N][MAX_V];

int main() {

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

  int N, W;
  cin >> N >> W;
  vector<ll> w(N), v(N);
  for (int i = 0; i < N; ++i) {
    cin >> w[i] >> v[i];
  }

  for (int i = 0; i < MAX_N; ++i) {
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
      dp[i][sum_v] = LLONG_MAX / 2;
    }
  }
  dp[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
      // iを選ぶ時
      if (sum_v - v[i] >= 0) dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - v[i]] + w[i]);
      // iを選ばない時
      dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v]);
    }
  }

  ll max_v = 0;
  for (ll sum_v = 0; sum_v < MAX_V; ++sum_v) {
    if (dp[N][sum_v] <= W) max_v = max(max_v, sum_v);
  }
  cout << max_v << endl;
  return 0;
}

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

X =list()

Y = 0

for i in range(0,N):
    X.append(list(map(int,input().strip().split(' '))))

if (X[0][1]+X[0][2]-X[0][0])%2 == 0 and X[0][1]+X[0][2] <= X[0][0]:
    for i in range(0,N-1):
        T = X[i+1][0]-X[i][0]
        A = X[i+1][1]-X[i][1]
        B = X[i+1][2]-X[i][2]
        if (A+B-T)%2 == 0 and A+B <= T:
            Y = Y
        else:
            Y += 1
    if Y == 0:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Measured memory_bytes: 27380
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long int lli;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define YES_RTN s_cout("Yes");return 0
#define NO_RTN  s_cout("No");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);


int main(void) {

	int    A[4],cost;

	i_cins(3,A);
	qsort(A, 3, sizeof(int), s_asort);
	cost = (A[2]-A[1])+(A[1]-A[0]);
	i_cout(cost);

	return 0;
	}
	
//降順
int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
//
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	rept(i, 0, n) {
		i_cin(*(a + i));
	}
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  Int h,w;
  cin>>h>>w;
  vector<vector<Int> > a(h,vector<Int>(w));
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++)
      cin>>a[i][j];

  Int ans=1e15;
  for(Int y=0;y<h;y++){
    for(Int x=0;x<w;x++){
      Int tmp=0;
      for(Int i=0;i<h;i++){
	for(Int j=0;j<w;j++){
	  tmp+=a[i][j]*min(abs(i-y),abs(j-x));
	}
      }
      ans=min(ans,tmp);
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3168
# D - Even Relation
from typing import List, Tuple


def main():
    N, *X = map(int, open(0).read().split())
    tree: List[List[Tuple[int, int]]] = [[] for _ in range(N + 1)]
    for u, v, w in zip(*[iter(X)] * 3):
        w %= 2
        tree[u].append((v, w)), tree[v].append((u, w))

    color = [-1] * (N + 1)
    color[1] = 1
    stack = [1]
    while stack:
        u = stack.pop()
        cur = color[u]
        for v, w in tree[u]:
            if color[v] != -1:
                continue
            color[v] = cur ^ w
            stack.append(v)

    print("\n".join(map(str, color[1:])))


if __name__ == "__main__":
    main()


Measured memory_bytes: 126100
//競技プログラミング用のテンプレート
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <math.h>

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

using namespace std;
using ll = long long int;
using p = pair<int, int>;
using pl = pair<ll, ll>;
using v = vector<int>;
using vd = vector<double>;
using vs = vector<string>;
using vl = vector<ll>;

int main()
{
    string s;
    cin >> s;
    int l = 0;
    int r = s.length() - 1;
    int count = 0;
    while(l < r){
        if(s[l] != s[r]){
            count++;
        }
        l++;
        r--;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
using Int = unsigned long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
int const mod = 1e9+7;
#define END {cout<<(ans)<<'\n'; return 0;}
#define ALL(vec) vec.begin(),vec.end()
#define Pr(type) priority_queue<type>
#define gPr(type) priority_queue<type,vector<type>,greater<type>>
#define V(type) vector<type>
#define rep(i,n) for(int i=0; i<n; i++)
#define rer(i,s,n) for(int i=s; i<n; i++)
#define gnr(i,l,r) for(int i=r; i>=l; i--)
#define eb emplace_back
#define pri1(a) cout<<a<<'\n'
#define pri2(a,n) rep(i,(n)-1)cout<<a[i]<<' '; cout<<a[(n)-1]<<'\n';
#define prip(p) cout<<(p).first<<' '<<(p).second<<'\n'
template<class T> inline bool cmin(T& a, T b) { if (a > b) { return a = b; } return false; }
template<class T> inline bool cmax(T& a, T b) { if (a < b) { return a = b; } return false; }

int n,m,q,_,x,y;
string s,sb;
bool ok;
char ch;



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

  cin>>n>>m; Int a[n],b[n]; V(Int)ta,use;
  Int ans=0;
  rep(i,n)cin>>a[i]>>b[i];
  rer(i,1,30)if((m>>i)&1)ta.eb(i);
  bitset<30>k(m);
  for(int i:ta){
    bitset<30>uke;
    rep(j,30){
      if(j<i)uke[j]=1;
      else if(j==i)uke[j]=0;
      else uke[j]=k[j];
    }
    use.eb(uke.to_ullong());
  }
  use.eb(m);
  for(Int i:use){
    Int up=0;
    rep(j,n){
      ok=true;
      rep(l,30)if(((i>>l)&1)<((a[j]>>l)&1)){ok=false; break;};
      if(ok)up+=b[j];
    }
    cmax(ans,up);
  }
  END
}

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

#define ll long long
#define mod 1000000007
#define pll pair<long long,long long>
#define pdd pair<long double,long double>
#define vll vector<ll>
#define rep(i,j,n) for(int i=j;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define inf 1e17
#define N 100010
// priority_queue<pll,vector<pll>,greater<pll> >pq;
// priority_queue<ll,vector<ll>,greater<ll> >pq1;

ll result(ll a, ll b, ll p){
    ll ans=1;
    if(b==(-1))
        b=p-2;
    while(b){
        if(b&1){
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

ll T,n,m;

int main(){
	if(fopen("input.txt", "r"))
	freopen("input.txt", "r", stdin),
    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    while(n){
    	if(n%10==7){
    		cout << "Yes";
    		return 0;
    	}
    	n/=10;
    }
    cout << "No";

    return 0;
}


Measured memory_bytes: 3636
N = int(input())
CSFlist = [tuple(map(int, input().split())) for _ in range(N - 1)]
for i in range(N):
    now = 0
    for c, s, f in CSFlist[i:]:
        now = max(now, s)
        now += (f - now % f) if now % f != 0 else 0
        now += c
    print(now)


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <sstream>
#include <iterator>
#include <sstream>
#include <iomanip>
#include <istream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

int main()
{
    
    int a, b, c;
    cin >> a >> b >> c;

    if(a <= c && c <= b) cout << "Yes" << endl;
    else cout << "No" << endl;

}


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

int main() {
  int N;
  cin >> N;
  
  for(int i = 0; i<N; i++){
    string C;
    cin >> C;
    if(C=="Y"){
      cout << "Four"<<endl;
      break;
    }
    
    else if(N==i+1){
      cout << "Three"<<endl;
    }
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
char a[51][51], b[51][51];
 
int main() {
	vector<pair<int,int>> v; 
	int n,m;
	cin>>n>>m;
	for(int i=0; i<n;i++)
			for(int j=0; j<n;j++) cin>>a[i][j];
 
 
	for(int i=0; i<m;i++)
			for(int j=0; j<m;j++) cin>>b[i][j];
	

	int t=m-1;
	bool l;
	for(int i=0; i<n;i++)
			for(int j=0; j<n;j++) {
				if(i+t<n && j+t<n && a[i][j]==b[0][0] && a[i+t][j]==b[t][0] 
					&& a[i+t][j+t]==b[t][t] && a[i][j+t]==b[0][t])
				v.emplace_back(i,j);
			}
	for(auto & u:v){
		int first=u.first;
		int second=u.second;
		l=0;
		//cout<<a<<" "<<b<<endl;
		for(int i=0; i<m;i++)
			for(int j=0; j<m;j++) 
			if(b[i][j]!=a[i+first][j+second]) l=1;
			
		if(l==0) {
			cout<<"Yes"<<endl;
			return 0;
		}		
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a[3]={1}; 
  char ch[3]={'A','B','C'};
  char d,e,f;
  while(cin>>d>>e>>f){
    for(int i=0;i<3;i++)
      if((d==ch[0]&&f==ch[1]) ||(d==ch[1]&&f==ch[0]))
	swap(a[0],a[1]);
      else if((d==ch[0]&&f==ch[2]) ||(d==ch[2]&&f==ch[0]))
	swap(a[0],a[2]);
      else if((d==ch[1]&&f==ch[2]) ||(d==ch[2]&&f==ch[1]))
	swap(a[1],a[2]);
  }
  for(int i=0;i<3;i++)
    if(a[i]==1)
	cout<<ch[i]<<endl;
  return 0;
}

Measured memory_bytes: 1132
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

ll N,L,K;
ll A[SIZE],D[SIZE];
ll SUM[SIZE];


ll calc(ll head_index,ll head_loc,ll tail_index){

	ll n_1 = (L-head_loc+1);
	ll first_1 = A[head_index]+(head_loc-1)*D[head_index];
	ll sum_head = (n_1*(2*first_1+(n_1-1)*D[head_index]))/2;

	ll n_2 = (K-(n_1))%L;
	if(n_2 == 0){
		n_2 = L;
	}
	ll first_2 = A[tail_index];
	ll sum_tail = (n_2*(2*first_2+(n_2-1)*D[tail_index]))/2;

	return sum_head+sum_tail;
}


int main(){

	scanf("%lld %lld %lld",&N,&L,&K);

	SUM[0] = 0;

	for(int i = 1; i <= N; i++){

		scanf("%lld %lld",&A[i],&D[i]);

		SUM[i] = (L*(2*A[i]+(L-1)*D[i]))/2;
		SUM[i] += SUM[i-1];
	}

	ll add_index;

	if(K <= L){

		add_index = 0;

	}else{ //K > L

		if((K-L)%L == 0){

			add_index = (K-L)/L;

		}else{

			add_index = (K-L)/L+1;
		}
	}

	//末尾の数列のindexが切り替わる位置を求める
	ll MID;
	ll left = 1,right = L,mid = (left+right)/2;
	ll tmp,tmp_add;

	while(left <= right){

		tmp = L-mid+1;

		if((K-tmp)%L == 0){

			tmp_add = (K-tmp)/L;

		}else{

			tmp_add = (K-tmp)/L+1;
		}

		if(tmp_add == add_index){

			MID = mid;
			left = mid+1;

		}else{

			right = mid-1;
		}
		mid = (left+right)/2;
	}

	ll ans = 0;
	ll tail_index,base_sum;
	ll calc_L,calc_R,mid1,mid2;

	for(ll i = 1; i <= N; i++){

		tail_index = min(i+add_index,N);
		if(tail_index >= i+2){

			base_sum = SUM[tail_index-1]-SUM[i];

		}else{

			base_sum = 0;
		}

		//1-MIDで検索
		if(tail_index == i){

			//最も右側の数列
			ll first = A[i];
			if(L >= K){

				first += (L-K)*D[i];
			}

			tmp = (min(L,K)*(2*(first)+(min(L,K)-1)*D[i]))/2;
			ans = max(ans,base_sum+tmp);

		}else{

			calc_L = 1, calc_R = MID;

			while(calc_L+2 < calc_R){

				mid1 = (2*calc_L+calc_R)/3;
				mid2 = (calc_L+2*calc_R)/3;

				if(calc(i,mid1,tail_index) > calc(i,mid2,tail_index)){

					calc_R = mid2;
				}else{

					calc_L = mid1;
				}
			}

			for(int k = calc_L; k <= calc_R; k++){

				ans = max(ans,base_sum+calc(i,k,tail_index));
			}
		}

		if(MID == L)continue;
		//MID+1-Lで検索

		calc_L = MID+1, calc_R = L;

		tail_index++;
		tail_index = min(tail_index,N);

		if(tail_index >= i+2){

			base_sum = SUM[tail_index-1]-SUM[i];

		}else{

			base_sum = 0;
		}

		while(calc_L+2 < calc_R){

			mid1 = (2*calc_L+calc_R)/3;
			mid2 = (calc_L+2*calc_R)/3;

			if(calc(i,mid1,tail_index) > calc(i,mid2,tail_index)){

				calc_R = mid2;
			}else{

				calc_L = mid1;
			}
		}

		for(int k = calc_L; k <= calc_R; k++){

			ans = max(ans,base_sum+calc(i,k,tail_index));
		}
	}

	printf("%lld\n",ans);

	return 0;
}



Measured memory_bytes: 5484
N, D = gets.split.map(&:to_i)
X = []
N.times do
  X << gets.split.map(&:to_i)
end

ans = 0
(0..N-1).each do |i|
  (i+1..N-1).each do |j|
    sum = 0
    D.times do |k|
      sum += (X[i][k]-X[j][k])*(X[i][k]-X[j][k])
    end

    t = Math.sqrt(sum).floor
    if (t * t == sum.to_i) == true
      ans += 1
    end
  end
end

p ans


Measured memory_bytes: 3836
import math
pi = math.pi

A,B,H,M = map(int,input().split())

nakami = (60*H - 11*M)*pi/360
cs = math.cos(nakami)

anssq = A**2 + B**2 - 2*A*B*cs
ans = math.sqrt(anssq)
print(ans)



Measured memory_bytes: 9488
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
//const int INF = 1<<29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    int64_t A, B, N;
    cin >> A >> B >> N;
    int64_t y = min(B - 1, N);
    cout << (A * y) / B << endl;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank;
	int size;
	public:
    int cnt;

    union_find()=default;
    union_find(int n){ init(n); }

    void init(int n){
		size=n;
		cnt=n;
		parent.resize(size);
		rank.resize(size);
		for(int i=0; i<size; ++i){
			parent[i]=i;
			rank[i]=0;
		}
	}

	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}

	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
		} else {
			parent[y]=x;
			if(rank[x]==rank[y]) ++rank[x];
		}
		--cnt;
	}

	bool is_same(int x,int y){
		return find(x)==find(y);
	}
};

struct edge{
    int s,t,c;
    edge(int s,int t,int c):s(s),t(t),c(c){}
    bool operator<(const edge& other)const{ return c<other.c; }
};

void solve(){
    while(true){
        int n,m;
        cin >> n >> m;
        if(n==0 and m==0) break;
        vector<edge> edges;
        rep(i,0,m){
            int s,t,c;
            cin >> s >> t >> c;
            --s;
            --t;
            edges.emplace_back(edge(s,t,c));
        }
        sort(edges.begin(),edges.end());
        union_find uf(n);
        vector<int> costs;
        for(const auto& e:edges) if(!uf.is_same(e.s,e.t)){
            uf.unite(e.s,e.t);
            costs.emplace_back(e.c);
        }
        cout << costs[max(0,(n-2)/2)] << endl;
    }
}


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(8);
    solve();
    return 0;
}

Measured memory_bytes: 3308
#include <iostream>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main(){
    LL n;
    LL a;
    LL num_max=1000000000000000000;
    LL ans=1;
    bool overflow=false;
    bool zero=false;
    cin >> n;
    for(LL i=0; i<n; i++){
        cin >> a;
        if(a==0){
            zero=true;
        }else if(num_max/a<ans){
            overflow=true;
        }
        ans*=a;
    }

    if(zero==true){
        cout << 0 << endl;
    }else if(overflow==true){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
    int n,m;
    cin>>n>>m;
    vector<tuple<int,int,int>>data(m);//0=pref,1=year,2=order
    rep(i,m){
        cin>>get<0>(data[i])>>get<1>(data[i]);
        get<2>(data[i])=i;
    }
    sort(data.begin(),data.end());
    int cnt=0;
    rep(i,m){//1 to order in pref
        if(i==0||get<0>(data[i])==get<0>(data[i-1])){
            cnt++;
            get<1>(data[i])=cnt;
        }
        else{
            cnt=1;
            get<1>(data[i])=cnt;
        }
    }
    char c1,c2;
    vector<tuple<int,string,string>>ans(m);//0=order,1=prefnum,2=inprefnum
    rep(i,m){
        get<0>(ans[i])=get<2>(data[i]);
        rep(j,6){
            c1='0'+get<0>(data[i])%10;
            c2='0'+get<1>(data[i])%10;
            get<1>(ans[i])=c1+get<1>(ans[i]);
            get<2>(ans[i])=c2+get<2>(ans[i]);
            get<0>(data[i])/=10;
            get<1>(data[i])/=10;
        }
    }
    sort(ans.begin(),ans.end());
    rep(i,m){
        cout<<get<1>(ans[i])<<get<2>(ans[i])<<endl;
    }
	return 0;
}


Measured memory_bytes: 14464
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define f first
#define s second
#define pb push_back

main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int l, r, d;
	cin>>l>>r>>d;
	cout<<(r/d)-((l-1)/d);
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> v(n);
  rep(i, n) cin >> v[i];

  vector<ll> sl(n + 1);
  rep(i, n) sl[i + 1] = sl[i] + v[i];

  vector<int> rv(n);
  rep(i, n) rv[i] = v[i];
  reverse(all(rv));

  vector<ll> sr(n + 1);
  rep(i, n) sr[i + 1] = sr[i] + rv[i];

  ll ans = 0;
  rep(l, k + 1) rep(r, k - l + 1) {
    if(l + r > n) continue;
    int ret = k - l - r;
    vector<int> hand;
    rep(i, l) hand.push_back(v[i]);
    rep(i, r) hand.push_back(rv[i]);
    sort(all(hand));
    ll now = sl[l] + sr[r];
    rep(i, ret) {
      if(i >= hand.size()) break;
      if(hand[i] > 0) break;
      now -= hand[i];
    }
    ans = max(ans, now);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <inttypes.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    intmax_t A[3][3], N, b[10];
    intmax_t ans = 0;

    for (size_t i = 0; i < 3; i++) {
        for (size_t j = 0; j < 3; j++) {
            scanf("%jd", &A[i][j]);
        }
    }
    scanf("%jd", &N);
    for (size_t i = 0; i < N; i++) {
        scanf("%jd", &b[i]);
    }

    for (size_t i = 0; i < 3; i++) {
        for (size_t j = 0; j < 3; j++) {
            for (size_t k = 0; k < N; k++) {
                if (A[i][j] == b[k]) {
                    A[i][j] = 0;
                }
            }
        }
    }

    for (size_t i = 0; i < 3; i++) {
        bool bingo = true;
        for (size_t j = 0; j < 3; j++) {
            if (A[i][j] != 0)
                bingo = false;
        }
        if (bingo) {
            puts("Yes");
            return 0;
        }
    }

    for (size_t j = 0; j < 3; j++) {
        bool bingo = true;
        for (size_t i = 0; i < 3; i++) {
            if (A[i][j] != 0)
                bingo = false;
        }
        if (bingo) {
            puts("Yes");
            return 0;
        }
    }

    if (A[0][0] == 0 && A[1][1] == 0 && A[2][2] == 0) {
        puts("Yes");
        return 0;
    }

    if (A[0][2] == 0 && A[1][1] == 0 && A[2][0] == 0) {
        puts("Yes");
        return 0;
    }

    puts("No");

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define LL long long
#define M 1000005
using namespace std;
const int P=1e9+7;
int gcd(int n,int m){
	return m?gcd(m,n%m):n;
}
int A[205][205];
int main(){
	int n;
	/*LL ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		if(i%3&&i%5)ans+=i;
	}
	cout<<ans<<endl;*/
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)A[i][j]=gcd(i,j);
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				ans+=A[A[i][j]][k];	
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3940
#include <cstdio>
#include <algorithm>
#ifdef WIN32
#define L_L "%I64d"
#else
#define L_L "%lld"
#endif
#define lt p<<1
#define rt p<<1|1
#define IL inline
#define N 200020
#define REP(a,b,c) for(a=b;a<=c;a++)
using namespace std;
typedef long long lol;
const lol inf=1e15;
int x[N],X,n,q;
lol tag,tmp,val,ml[N<<2],mr[N<<2];
IL int rd(){
	int res=0;char c;while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
IL void build(int p,int l,int r){
	if(l==r){ml[p]=((l==X)?0:inf)-l;mr[p]=((l==X)?0:inf)+l;return;}
	int mid=(l+r)>>1;build(lt,l,mid),build(rt,mid+1,r);
	ml[p]=min(ml[lt],ml[rt]),mr[p]=min(mr[lt],mr[rt]);
}
IL void LM(int p,int l,int r){
	if(r<=X){tmp=min(tmp,ml[p]);return;}
	int mid=(l+r)>>1;
	LM(lt,l,mid);if(X>mid)LM(rt,mid+1,r);
}
IL void RM(int p,int l,int r){
	if(l>=X){tmp=min(tmp,mr[p]);return;}
	int mid=(l+r)>>1;
	if(X<=mid)RM(lt,l,mid);RM(rt,mid+1,r);
}
IL void modify(int p,int l,int r){
	if(l==r){ml[p]=val-l,mr[p]=val+l;return;}
	int mid=(l+r)>>1;
	if(X<=mid)modify(lt,l,mid);else modify(rt,mid+1,r);
	ml[p]=min(ml[lt],ml[rt]),mr[p]=min(mr[lt],mr[rt]);
}
IL void travel(int p,int l,int r){
	if(l==r){tmp=min(tmp,ml[p]+l);return;}
	int mid=(l+r)>>1;
	travel(lt,l,mid),travel(rt,mid+1,r);
}
int main(){
	n=rd(),q=rd(),x[0]=rd(),X=rd();
	int i,t;build(1,1,n);
	REP(i,1,q)x[i]=rd();
	REP(i,1,q){
		tmp=inf,X=x[i],LM(1,1,n),val=tmp+X;
		tmp=inf,RM(1,1,n),val=min(val,tmp-X);
		t=abs(x[i]-x[i-1]),val-=t,tag+=t;
		X=x[i-1];modify(1,1,n);
	}
	tmp=inf;travel(1,1,n);tmp+=tag;
	printf(L_L,tmp);
  return 0;
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout << fixed
#define endl '\n'

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

void solve(istream& cin, ostream& cout) {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (abs(a - c) <= d || (abs(a - b) <= d && abs(c - b) <= d))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
  return 0;
}
#endif


Measured memory_bytes: 3620
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();
        int Ac = 0;
        int Bc = 0;
        int Cc = 0;
        char turns = 'a';
        while (true) {
            if (turns == 'a' && Ac >= A.length()) {
                System.out.println("A");
                return;
            } else if (turns == 'b' && Bc >= B.length()) {
                System.out.println("B");
                return;
            } else if (turns == 'c' && Cc >= C.length()) {
                System.out.println("C");
                return;
            }
            char turn = 0;
            if (turns == 'a') {
                turn = A.charAt(Ac);
                Ac++;
            } else if (turns == 'b') {
                turn = B.charAt(Bc);
                Bc++;
            } else {
                turn = C.charAt(Cc);
                Cc++;
            }
            switch(turn) {
            case 'a' :
                turns = 'a';
                break;
            case 'b' :
                turns = 'b';
                break;
            case 'c' :
                turns = 'c';
            }
        }
    }
    
}


Measured memory_bytes: 35736
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.IO.Compression;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{

    class Program
    {
        private const long COMDIV = 1000000007;

        static void Main(string[] args)
        {
            var r1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var r2 = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine(r1[0] == r2[0] ? 0 : 1);

        }
    }
}

Measured memory_bytes: 28268
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	while (1) {

		int N; cin >> N;
		if (!N)break;
		vector<int>nums(N);
		for (int i = 0; i < N; ++i) {
			cin >> nums[i];
		}
		sort(nums.begin(), nums.end());
		long long int ans = 0;
		for (int i = 0; i < N; ++i) {
			ans += (N - i - 1)*nums[i];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3156
H,W = map(int,input().split()) 
import math
if (H == 1) or (W == 1):
    print(1)
else:
    if H%2 ==0:
        print(H//2*W)
    else:
        if W%2 == 0:
            print(H*(W//2))
        else:
            print(H*((W-1)//2)+(H+1)//2)

Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
	int x,y,z;
	scanf("%d %d",&x,&y);
	if(x<=y){
		z=y-x;
		printf("%d\n",z);
	}
	else	if(x>=y){
		z=x-y;
		printf("%d\n",z);
	}
	return 0;
}


Measured memory_bytes: 2756
#include<stdio.h>
int main(){
  int n=0,i=0,j=0;
  int R[200000];
  int max=0,min=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&R[i]);
  }
  max=-1000000000;
  min=R[0];
  for(j=1;j<n;j++){
      if(max<R[j]-min)max=R[j]-min;
      if(min>R[j])min=R[j];
  }
  printf("%d\n",max);
  return 0;
}



Measured memory_bytes: 2520
#include <bits/stdc++.h>
using namespace std;
const int64_t INF=999999999;

int main() {
   int A,B,T;
   cin>>A>>B;
   int ans=0;
   ans+=max(A,B)+ max(max(A,B)-1,min(A,B));
   cout<<ans<<endl;
return 0;}

Measured memory_bytes: 256
N=gets.to_i
T,A=gets.strip.split(' ').map(&:to_i)
H=gets.strip.split(' ').map(&:to_i)
ans=0
(N-1).times{|i|
    if (A-(T-H[ans]*0.006)).abs>(A-(T-H[i+1]*0.006)).abs
        ans=i+1
        end
}
puts ans+1

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh

int main()
{
	dhoom;
	int a , b , c;
	cin >> a >> b >> c;
	if(c < a || c > a + b)
		cout << "NO" << endl;
	else 
		cout << "YES" << endl;
		
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int sum=0;
  string s;
  cin>>s;
  int L=s.size();
  bool OK = true;
  if(s[0]!='A') OK=false;
    for(int i=1;i<L;i++){
      if(isupper(s[i])){
        if(i==1||i==L-1||s[i]!='C'){
          OK=false;
        }
        sum++;
      }
         }
         if(sum!=1) OK=false;
         if(OK==true)cout<<"AC";
         else cout<<"WA";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Endl '\n'
typedef long long int lli;
void solve();
int main(int argc, char const *argv[]){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
    solve();
}
void solve(){
  int A, B, C, D;
  cin>>A>>B>>C>>D;
  int turn = 0;
  while(A>0 && C>0){
    if(turn == 0){
      C-=B;
    }else{
      A-=D;
    }
    turn = !turn;
  }
  if(A>0){
    cout<<"Yes"<<Endl;
  }else{
    cout<<"No"<<Endl;
  }
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

ll dp[500008];
string s;

ll f(ll m){
	ll &r=dp[m];
	if(r>=0)return r;
	if(m==0&&s[0]=='<'){
		r=0; return r;
	}
	if(m==SZ(s)&&s[m-1]=='>'){
		r=0; return r;
	}
	if(m>0&&m<SZ(s)&&s[m-1]=='>'&&s[m]=='<'){
		r=0; return r;
	}
	if(m==0){
		r=f(1)+1; return r;
	}
	if(m==SZ(s)){
		r=f(m-1)+1; return r;
	}
	if(s[m-1]=='<'&&s[m]=='<'){
		r=f(m-1)+1; return r;
	}
	if(s[m-1]=='>'&&s[m]=='>'){
		r=f(m+1)+1; return r;
	}
	if(s[m-1]=='<'&&s[m]=='>'){
		r=max(f(m-1),f(m+1))+1; return r;
	}
}

int main(){FIN;
	cin>>s;
	mset(dp,-1);
	ll res=0;
	fore(i,0,SZ(s)+1){
		//cout<<f(i)<<" ";
		res+=f(i);
	}
	//cout<<"\n";
	cout<<res;
	return 0;
}

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

const int dig = 40;

int main() {
  int n;
  long long k;
  cin >> n >> k;
  long long a[n];
  for ( int i = 0; i < n; i++ ) { cin >> a[i]; }

  long long dp[dig+1][2];
  for ( int i = 0; i < dig+1; i++ ) {
    for ( int j = 0; j < 2; j++ ) {  
      dp[i][j] = -1;
    }
  }
  dp[0][0] = 0;

  for ( int d = 0; d < dig; d++ ) {
    long long mask = 1ll << (dig-1 - d);
    
    int ct1 = 0;
    for ( int i = 0; i < n; i++ ) {
      if ( a[i] & mask ) { ct1++; }
    }

    long long select0 = mask * ct1;
    long long select1 = mask * (n-ct1);

    if ( dp[d][1] != -1 ) {
      dp[d+1][1] = max(dp[d+1][1], dp[d][1]+max(select0, select1));
    }
    if ( dp[d][0] != -1 && (k & mask) ) {
      dp[d+1][1] = max(dp[d+1][1], dp[d][0] + select0);
    }
    if ( dp[d][0] != -1 ) {
      if ( k & mask ) {
        dp[d+1][0] = max(dp[d+1][0], dp[d][0]+select1);
      } else {
        dp[d+1][0] = max(dp[d+1][0], dp[d][0]+select0);
      }
    }
  }

  cout << max(dp[dig][0], dp[dig][1]) << endl;
  return 0;
}


Measured memory_bytes: 4400
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll i,j,n,m,w,ans,p[109],wt[109],dp[100009][109],f[100009][109];
ll func(ll w,ll i)
{
    if(dp[w][i]==0&&f[w][i]==0) {dp[w][i]=-1; f[w][i]=1; }
    if(dp[w][i]!=-1) return dp[w][i];
    if(i==n) return 0;
    if(w>=wt[i])
        dp[w][i]=max(p[i]+func(w-wt[i],i+1),func(w,i+1));
    else
        dp[w][i]=func(w,i+1);

    return dp[w][i];
}
int main()
{
  ios_base::sync_with_stdio(false),cin.tie(0);
  cin>>n>>w;
  for(i=0;i<n;i++)
    cin>>wt[i]>>p[i];
  ans=func(w,0);
  cout<<ans<<endl;
}


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

#define y1 as214
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define ll long long
#define oo INT_MAX

const int N = 3e3 + 5;
ll n , res;
ll a[N];
ll dp[N][N];
/// dp[i][j] là số điểm lớn nhất của người chơi thứ 1 có thẻ nhận được nếu khởi đầu trong đoạn [i , j]

int main()
{
    //freopen("L.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i , 1 , n)
    {
        cin >> a[i];
        res += a[i];
    }
    FOR(i , 1 , n)
        dp[i][i] = a[i];
    FOR(i , 1 , n - 1)
        dp[i][i + 1] = max(a[i] , a[i + 1]);
    FOR(r , 3 , n)
        FORD(l , r - 2 , 1)
            dp[l][r] = max(min(dp[l + 2][r] , dp[l + 1][r - 1]) + a[l] , min(dp[l][r - 2] , dp[l + 1][r - 1]) + a[r]);
    cout << dp[1][n] - (res - dp[1][n]) << endl;
}


Measured memory_bytes: 70016
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right, bisect_left
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

# N以下の素数列挙(エラトステネスの篩)
def cal_primes(N):
    # 素数候補をリストでもつ
    candidate = [*range(2, N+1)]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*filter(lambda x: x % candidate[0] != 0, candidate)]
    
    primes.extend(candidate)
    return primes

def main():
    N = int(input())
    primes = cal_primes(55555)
    primes = [*filter(lambda x: x % 5 == 1, primes)]
    
    print(*primes[:N])


if __name__ == "__main__":
    main()


Measured memory_bytes: 11656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1001001001;
const double EPS = 1e-10;
struct Edge { ll from, to, cost; };
using Graph = vector<vector<Edge>>;

int is_prime[101010];

int f(int a){
    if(is_prime[a]!=-1)return is_prime[a];
    for(int i=2;i*i<=a;i++){
        if(a!=i&&a%i==0)return is_prime[a]=false;
    }
    return is_prime[a]=true;
}

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

    fill(is_prime,is_prime+101010,-1);
    is_prime[0]=is_prime[1]=false;
    int c_sum[101010]={};
    for(int x=1;x<101010;x++){
        if(x%2==0){
            c_sum[x]=c_sum[x-1];
            continue;
        }
        int y=(x+1)/2;
        if(f(x)&&f(y))c_sum[x]=(x>1?c_sum[x-2]:0)+1;
        else c_sum[x]=(x>1?c_sum[x-2]:0);
    }
    int q;
    cin>>q;
    for(int i=0,l,r;i<q;i++){
        cin>>l>>r;
        cout<<c_sum[r]-c_sum[l-1]<<endl;
    }
}

Measured memory_bytes: 4376
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define forn(i,n) for(int i=0; i<(int)n; i++)
ll power(ll x,ll n);
bool isprime(ll n);
ll mod=1e9+7;

void test_case()
{
    int x,n;
    cin>>x>>n;
    int a[n];
    map<int,int> mp;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        mp[a[i]]=1;
    }
    int k=x;
    for(int i=0;;i++) {
        if(i&1)
            k-=i;
        else k+=i;
        if(mp.find(k)==mp.end()) {
            cout<<k;
            break;
        }
    }
}

int main()
{
    fastio
//    int t;
//    cin>>t;
//    while(t--)
    test_case();
}
ll power(ll x,ll n)
{
    ll ans=1;
    while(n>0) {
        if(n&1)
            ans*=x;
        n>>=1;
        x*=x;
    }
    return ans;
}

bool isprime(ll n)
{
    if(n==2 || n==3)
        return true;
    if(n<=1 || n%2==0 || (n%6!=1 && n%6!=5))
        return false;
    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0)
            return false;
    }
    return true;
}


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

using ll = long long;

// 組合せを素数で割った値を求める
const int MAX = 2000009;
const ll MOD = 1e9 + 7;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  
  COMinit();
  
  ll ans = 0;
  for(int i = r1; i <= r2; i++){
    ans += COM(i + 1 + c2, c2);
    ans %= MOD;
    ans += MOD;
    ans -= COM(i + 1 + c1 - 1, c1 - 1);
    ans %= MOD;
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 47104
import java.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    public static void main(String[] args)throws IOException{
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        long[] A = new long[L+1];
        for(int i=1;i<=L;i++) A[i]=sc.nextLong();
        // leftBack requires come back at i, while left requires not coming back
        if(L==1){
            System.out.println(0);
            return;
        }
        long[] leftSum = new long[L+1];
        for(int i=1;i<=L;i++) leftSum[i] = leftSum[i-1]+A[i];
        long[] leftBack = new long[L+1],left = new long[L+1];
        for(int i=1;i<=L;i++){
            leftBack[i] = Math.min(leftSum[i],leftBack[i-1]+(A[i]==0?2:A[i]%2));
            left[i] = Math.min(leftBack[i-1],left[i-1])+(1-A[i]%2);
        }
        long[] rightSum = new long[L+2];
        for(int i=L;i>=0;i--) rightSum[i] = rightSum[i+1]+A[i];
        long[] rightBack = new long[L+1], right = new long[L+1];
        for(int i=L-1;i>=0;i--){
            rightBack[i] = Math.min(rightSum[i+1],rightBack[i+1]+(A[i+1]==0?2:A[i+1]%2));
            right[i] = Math.min(rightBack[i+1],right[i+1])+(1-A[i+1]%2);
        }
        long ans = Long.MAX_VALUE;
        for(int i=0;i<=L;i++){
            long cur = Math.min(leftBack[i]+right[i],left[i]+rightBack[i]);
            cur = Math.min(leftBack[i]+rightBack[i],cur);
            ans = Math.min(ans,cur);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 96508
// In the name of God

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
int n;
vector<pair<long long,long long>> points;

inline long long dis(long long x, long long y) {
	return x*x + y*y;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=0;i<n;i++) {
		int x, y;
		cin >> x >> y;
		points.push_back(make_pair(x, y));
	}
	long long ans = 0;
	for(int mul1=0;mul1<2;mul1++) {
		for(int mul2=0;mul2<2;mul2++) {
			int m1 = mul1?mul1:-1;
			int m2 = mul2?mul2:-1;
			vector<pair<long long,long long>> p;
			for(int i=0;i<n;i++) p.push_back(make_pair(points[i].first*m1, points[i].second*m2));
			set<pair<long long,long long>> s;
			s.insert(make_pair(0, 0));
			for(int i=0;i<n;i++) {
				vector<pair<long long,long long>> add;
				for(auto &x : s) {
					pair<long long,long long> go;
					go.first = x.first + p[i].first;
					go.second = x.second + p[i].second;
					add.push_back(go);
				}
				for(int i=0;i<add.size();i++) s.insert(add[i]);
				long long mxsofar= -1e18;
				vector<pair<long long, long long>> dl;
				for(auto it=s.rbegin(); it!=s.rend();++it) {
					if(mxsofar >= it->second) {
						dl.push_back(*it);
					}
					else mxsofar = it->second;
				}
				for(auto x : dl) s.erase(x);
			}
			for(auto x : s) ans=max(ans, dis(x.first, x.second));
		}
	}
	cout << fixed << setprecision(50) << sqrt((long double)ans);
	return 0;
}


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

int main(){
	string A, B;
	cin >> A >> B;
	int x=A.size(), y=B.size(), c=0;
	if(x>y) cout << "GREATER", c++;
	if(x<y) cout << "LESS", c++;
	if(x==y){
		for(int i=0;i<x;i++){
			if(A[i]>B[i]){
				c++;
				cout << "GREATER";
				break;
			} else if(A[i]<B[i]){
				c++;
				cout << "LESS";
				break;
			}
		}
	}
	if(c==0) cout << "EQUAL" ;;
}


Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

typedef pair<int,int> PA;

class Node{
public:
  int cost;
  PA p;
  
  //コストラクタ
  Node(int cost, PA p):cost(cost), p(p){
    
  }
  
  bool operator < (const Node &o)const{
    return cost  > o.cost;
  }

};

typedef priority_queue<Node> PQ;

int field[80][80];
int w,h;

void show(){
  for(int i = 0 ; i < h*2-1; i++){
    for(int j = 0; j < w*2-1; j++){
      cout << field[i][j] << " ";
    }
    cout << endl;
  }

}

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

bool closed[80][80];
int dijkstra(){
  PQ pq;
  pq.push(Node(1,PA(0,0)));
  for(int i = 0 ; i < 80; i++)for(int j = 0 ; j < 80; j++)closed[i][j] = false;

  while(!pq.empty()){
    Node current = pq.top();pq.pop();

    if(closed[current.p.second][current.p.first])continue;

    closed[current.p.second][current.p.first] = true;

    //cout << "(" << current.p.first << "," << current.p.second << ")" << current.cost << endl;
    if(current.p.first == w*2-2 && current.p.second == h*2-2)return current.cost;
    for(int i = 0; i < 4; i++){
      int nx = current.p.first + dx[i];
      int ny = current.p.second + dy[i];

      if(nx < 0 || nx >= w*2-1)continue;
      
      if(ny < 0 || ny >= h*2-1)continue;

      if(field[ny][nx] == 1)continue;
	 nx += dx[i];
	 ny += dy[i];
      if(nx < 0 || nx >= w*2-1)continue;

      if(ny < 0 || ny >= h*2-1)continue;

      if(field[ny][nx] == 1)continue;

	 
      pq.push(Node( current.cost + 1, PA(nx,ny) ));
    }
  }
  return 0;
}

int main(){

  while(cin >> w >> h, w || h){
    for(int i = 0 ; i < h; i++)for(int j = 0; j < w; j++)field[i][j] = 0;
    for(int i = 0; i < h*2-1; i++){
      if(i%2){
	for(int j = 0; j < w; j++){
	  cin >> field[i][j*2];
	}
      }else{
	for(int j = 0; j < w-1; j++){
	  cin >> field[i][1+j*2];
	}
      }
    }

    cout << dijkstra() << endl;
  }
}

Measured memory_bytes: 1224
import itertools
import numpy as np

n, d = [int(_) for _ in input().split()]
a = np.array([[int(_) for _ in input().split()] for _ in range(n)])

L = list(itertools.combinations(a, 2))
cnt = 0
for u, v in L:
    dist = np.sqrt(sum((u-v)**2))
    if dist%1==0:
        cnt +=1
print(cnt)

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

int main(){

  int n,m;
  string s[1000],t[1000];
  bool a = true,b = true,c = true;

  cin >> n;
  for(int i=0;i<n;i++) cin >> s[i];

  cin >> m;
  for(int i=0;i<m;i++) cin >> t[i];

  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
      if(s[j] == t[i] && a == true){
	cout << "Opened by " << t[i] << endl;
	a = false;
	b = false;
	break;
      }
      if(s[j] == t[i] && a == false){
	cout << "Closed by " << t[i] << endl;
	a = true;
	b = false;
	break;
      }
    }
    if(b == true) cout << "Unknown " << t[i] << endl;
    b = true;
  }
}

Measured memory_bytes: 1244