akhauriyash/Code-Regression huggingface dataset:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    p = [x for x in map(int,input().split())]
    q = [x for x in map(int,input().split())]
    if p == q:
        print(0)
        return
    nums = [i+1 for i in range(n)]
    cnt = 1
    l = 0
    h = 0
    for x in itertools.permutations(nums):
        y = [z for z in x]
        if y == p:
            l = cnt
        elif y == q:
            h = cnt
        cnt += 1
    print(abs(l-h))
    return

if __name__=='__main__':
    main()


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

int main(){
    string s;
    cin >> s;
    int fn='A';
    int cou=0;
    //cout << fn << endl;
    for(int i=0;i<s.size();i++){
        if(s[i] <= fn )cou++;
        fn=s[i];
    }

    cout << cou << endl;
    return 0;
}

Measured memory_bytes: 3152
#include<bits/stdc++.h>
#define ll long long int

using namespace std;
int main()
{
    ll n;
    cin>>n;
    double p,x;
    p=n/3.00;
    x=p*p*p;
    cout<<fixed<<setprecision(12)<<x<<endl;
    return 0;
}



Measured memory_bytes: 256
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def main():
    num = int(input())
    data_pc = sorted([int(input()) for i in range(num)])
    data_tap = sorted([int(input()) for i in range(num)])

    ans = 1
    mod = 10 ** 9 + 7

    ind_pc = 0
    ind_tap = 0
    count_pc, count_tap = 0, 0

    while ind_pc < num or ind_tap < num:
        if ind_pc >= num:
            if count_pc > 1:
                ans *= count_pc
                count_pc -= 1
            ind_tap += 1
        elif ind_tap >= num:
            if count_tap >= 1:
                ans *= count_tap
                count_tap -= 1
            ind_pc += 1
        elif data_pc[ind_pc] < data_tap[ind_tap]:
            count_pc += 1
            if count_tap >= 1:
                ans *= count_tap
                count_tap -= 1
                count_pc -= 1
            ind_pc += 1
        else:
            count_tap += 1
            if count_pc >= 1:
                ans *= count_pc
                count_pc -= 1
                count_tap -= 1
            ind_tap += 1
        ans %= mod

    print(ans)





if __name__ == '__main__':
    main()
    # test()



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

using namespace std;

const int M=26;

int arr[404];
int n;
int c[26];
int s[404][26];
int las[26];

long long calc()
{
	for(int i=0;i<M;i++) las[i]=0;
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		las[arr[i]-1]=i+1;
		ans+=s[i][arr[i]-1];
		for(int j=0;j<M;j++)
			ans-=c[j]*(i+1-las[j]);
		//cout << ans << endl;
	}
	return ans;
}

long long calcs(vector<int> v,int st)
{
	vector<int> lass;
	for(int i=0;i<M;i++)
		lass.push_back(las[i]);
	long long res=0;
	for(int i=0;i<v.size();i++)
	{
		lass[v[i]]=st+i;
		res+=s[st+i-1][v[i]];
		for(int j=0;j<M;j++)
			res-=c[j]*(st+i-lass[j]);
	}
	return res;
}

vector<long long> calcd()
{
	int lass[M]={0};
	long long prv=0,ans=0;
	vector<long long> v;
	for(int i=0;i<n;i++)
	{
		lass[arr[i]-1]=i+1;
		ans+=s[i][arr[i]-1];
		for(int j=0;j<M;j++)
			ans-=c[j]*(i+1-lass[j]);
		v.push_back(ans-prv);
		prv=ans;
		//cout << ans << endl;
	}
	return v;
}

mt19937 rng(12342);


int getrand(int x,int y)
{
	return uniform_int_distribution<int>(x, y)(rng);

}

int main()
{
	//auto start = std::chrono::system_clock::now();
	cin >> n;
	for(int i=0;i<M;i++) cin >> c[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<M;j++) cin >> s[i][j];
	}
	for(int i=0;i<n;i+=3)
	{
		vector<int> v={0,0,0};
		long long best=calcs(v,1+i);
		arr[i]=1; arr[i+1]=1; arr[i+2]=1;
		for(int x=0;x<26;x++)
		{
			for(int y=0;y<26;y++)
			{
				for(int z=0;z<26;z++)
				{
					v[0]=x;
					v[1]=y;
					v[2]=z;
					long curs=calcs(v,1+i);
					if(curs>best)
					{
						best=curs;
						arr[i]=v[0]+1; arr[i+1]=v[1]+1; arr[i+2]=v[2]+1;
					}
				}
			}
		}
		for(int j=0;j<v.size();j++)
		{
			las[arr[i+j]-1]=i+j+1;
		}
	}
	//std::chrono::duration<double> elp=std::chrono::system_clock::now()-start;
	int t=1000;
	long long curs=calc();
	/*while(t--)
	{
		int x=uniform_int_distribution<int>(0, n-1)(rng);
		int y=uniform_int_distribution<int>(0, M-1)(rng);
		int oldx=arr[x];
		arr[x]=y+1;
		if(calc()<curs)
		{
			arr[x]=oldx;
		}
	}*/
	while(t--)
	{
		if(getrand(0,1))
		{
			vector<long long> cont=calcd();
			int z=0;
			for(int i=1;i<n;i++)
			{
				if(cont[i]<cont[z]) z=i;
			}
			for(int i=0;i<M;i++)
			{
				int x=z;
				int y=i;
				int oldx=arr[x];
				arr[x]=y+1;
				if(calc()<curs)
				{
					arr[x]=oldx;
				}
			}
		}
		else
		{
			int x=uniform_int_distribution<int>(0, n-1)(rng);
			int y=uniform_int_distribution<int>(0, M-1)(rng);
			int oldx=arr[x];
			arr[x]=y+1;
			if(calc()<curs)
			{
				arr[x]=oldx;
			}
		}
	}
	for(int i=0;i<n;i++)
		cout << arr[i] << endl;
}

Measured memory_bytes: 3684
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());
        var n = N;
        var sum = 0;
        while(n > 10)
        {
            var r = n % 10;
            sum += r;
            n /= 10;
        }
        sum += n;
        var res = "";
        if (N % sum == 0)
        {
            res = "Yes";
        }
        else
        {
            res = "No";
        }
        Console.WriteLine(res);
    }
}

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

using namespace std;

int main()
{

   int a,b;
   cin>>a>>b;

     if(a==13 && b==1){
        cout<<"Bob"<<endl;
    }
    else if(a==1 && b==13){
        cout<<"Alice"<<endl;
    }
   else if(a>b){
        cout<<"Alice"<<endl;
    }
    else if(b>a){
        cout<<"Bob"<<endl;
    }
    
    else {
        cout<<"Draw"<<endl;
    }



    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
 
namespace myApp
{
    class Program
    {
        static void Main(string[] args)
        {
            string  day = Console.ReadLine();
          string output = string.Empty;
          
          switch(day)
          {
            case "22":
              output = "Christmas Eve Eve Eve";
              break;
              
            case "23":
              output = "Christmas Eve Eve";
              break;
              
            case "24":
              output = "Christmas Eve";
              break;
              
            case "25":
              output = "Christmas";
              break;
              
          }
          Console.WriteLine(output);
        
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
//long long mo = 1e9 + 7;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    ll N, K, C;
    string S;
    cin >> N >> K >> C;
    cin >> S;
    vector<pair<ll,ll>> L,R;
    ll ind = 1;
    rep(i,N){
        if(S[i] == 'o'){
            L.push_back(make_pair(i, ind));
            ind++;
            if(ind > K){
                break;
            }
            i+=C;
        }
    }
    
    /*if(L.size()>0){
        ind = L[L.size()-1].second;
    }*/
    ind = K;
    rep(i,N){
        if(S[N-1-i] == 'o'){
            R.push_back(make_pair(N-1-i, ind));
            ind--;
            if(ind < 0){
                break;
            }
            i+=C;
        }
    }
    //ll NN = L.size();
    rep(i,K){
        if(L[i].first == R[K-1-i].first && L[i].second == R[K-1-i].second){
            cout << L[i].first+1 <<endl;
        }
    }
    /*
    vector<ll> DP(N+1,0);
    ll nw = 0;
    rep(i,N){
        if(S[i] == 'x'){
            DP[i+1] = -1;//DP[i]; 
        }else{
            nw++;
            if(i-C >= 0){
                DP[i+1] = max(DP[i], DP[i-C]+1);
            }else{
                DP[i+1] = 1;
            }
        }
    }
    ll cnt = 0;
    
    rep(i,N){
        //cout << DP[i+1] <<" ";
        if(DP[i+1] >= K){
            cnt++;
        }
    }
    //cout << endl;
    ll Y = cnt;
    //if(DP)
    //cout << Y << endl;
    //Y -= K;//K-1;
    //for(int i = nw - Y; i<nw-Y;i++){
    //}
    map<ll,ll> mp;
    rep(i,N){
        if(S[i] == 'o'){
            if(i+C*(K-DP[i+1]+1) <= N-1){
                mp[DP[i+1]]++;
            }
        }
    }
    /*
    rep(i,N){
        if(N-i-C-1 >= 0){
            DP[N-i-C-1] = DP[N-i];
        }
    }*/
    /*
    vector<ll> v;
    rep(i,N){
        if(S[i] == 'o'){
            if(mp[DP[i+1]] == 1){
                v.push_back(i+1);
            }
        }
    }
    rep(i,v.size()){
        cout << v[i] <<endl;
    }*/
    //cout << endl;
    /*
    ll cnt = 0;
    rep(i,N){
        if(S[i] == 'o'){
            cnt++;
            i += C;
        }
    }
    ll M = cnt;
    */

    //cout << A <<" "<<B<<" " <<C<<endl;
}

Measured memory_bytes: 12272
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string str;
    cin >> str;

    if (str[1] == str[2] && (str[0] == str[1] || str[2] == str[3]) )
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

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

int merge(int* A,int left,int mid,int right){
  int cnt=0;
  int n1=mid-left;
  int n2=right-mid;
  int L[n1+1],R[n2+1];
  for(int i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(int i=0;i<=n2-1;i++){
    R[i]=A[mid+i];
  }
  L[n1]=1000000000;
  R[n2]=1000000000;
  int i=0;
  int j=0;
  for(int k=left;k<=right-1;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i=i+1;
      cnt++;
    }
    else{
      A[k]=R[j];
      j=j+1;
      cnt++;
    }
  }
  return cnt;
}

int mergeSort(int*A,int left,int right){
  int tmp=0;
  if(left+1<right){
    int mid=(left+right)/2;
    tmp+=mergeSort(A,left,mid);
    tmp+=mergeSort(A,mid,right);
    tmp+=merge(A,left,mid,right);
  }
  return tmp;
}

int main(){
  int n;
  cin>>n;
  int S[n];
  for(int i=0;i<n;i++)cin>>S[i];
  int total=mergeSort(S,0,n);
  for(int i=0;i<n;i++){
    if(i==n-1){cout<<S[i]<<endl;break;}
    cout<<S[i]<<' ';
  }
  cout<<total<<endl;
}


Measured memory_bytes: 6964
# -*- coding: utf-8 -*-

N = int(input())
B = [int(i) for i in input().split()]

A= []
A.append(B[0])
for i in range(1,N):
    if i >= N-1:
        #print(i, "S")
        A.append(B[i-1])
    else:
        #print(i)
        A.append(min(B[i],B[i-1]))
print(sum(A))


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

const int N = 1E5 + 50;

int las, n, m, ans, size[N], vis[N], a[N], b[N], c[N], d[N], f[N];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int u, int v) {
    if(u == v) return ;
    // cout << "Add=" << u << ' ' << v << '\n';
    f[u] = v, size[v] += size[u];
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d", a + i), m ^= a[i], c[i] = a[i], f[i] = i;
    f[n + 1] = n + 1, las = m;
    c[++n] = a[n] = m, m = 0;
    for(int i = 1; i < n; i++) 
        scanf("%d", b + i), m ^= b[i], d[i] = b[i];
    d[n] = b[n] = m;
    sort(c + 1, c + 1 + n), sort(d + 1, d + 1 + n);
    for(int i = 1; i <= n; i++) {
        if(c[i] != d[i]) return 0 * printf("-1\n");
    }
    int len = unique(c + 1, c + 1 + n) - c - 1;
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(c + 1, c + 1 + len, a[i]) - c;
        b[i] = lower_bound(c + 1, c + 1 + len, b[i]) - c;
        if(a[i] != b[i] && i < n) size[b[i]] ++;
    }
    m = las;
    int idx = -1, fuck = lower_bound(c + 1, c + 1 + len, m) - c;
    // cout << fuck << ' ' << m << '\n';
    // for(int i = 1; i <= n; i++) cout << b[i] << ' '; puts("");
    for(int i = 1; i < n; i++) {
        if(a[i] != b[i]) {
            vis[a[i]] = vis[b[i]] = 1;
            if(b[i] == fuck) idx = i;
            // cout << a[i] << ' ' << b[i] << '\n';
            merge(find(a[i]), find(b[i]));
        }
    } 
    // cout << idx << '\n';
    if(idx > 0) ans --;
    for(int i = 1; i <= n; ++i) 
        if(find(i) == i && size[i] > 0) 
            ans += size[i] + 1;
    cout << ans << '\n';
    return 0;
}   

Measured memory_bytes: 4480
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#include<functional>
#define rep(i,n,m) for(int i=(n);i<(int)(m);i++)
#define reps(i,n,m) for(int i=(n);i<=(int)(m);i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define fs first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define LB(a,x) lb(all(a), x) - a.begin()
#define UB(a,x) ub(all(a), x) - a.begin()
#define printfdouble(x) printf("%.12f\n",(x))
#define chartoint(c) (int)((c) - '0')
#define chartoll(c) (long long)((c) - '0')
#define MOD 1000000007
#define itn int
#define enld endl
#define ednl endl
#define icn cin
#define Endl endl
#define stirng string
using namespace std;
typedef long long ll;
const double pi = 3.141592653589793;
using Graph = vector<vector<int>>;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b){if(b<a){a=b; return 1;} return 0;}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

const ll INFLL = 100100100100100100;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    ll a[1005];
    ll b[1005];
    ll c[1005];
    Fill(c, 0);
    rep(i,0,M){
        cin >> a[i] >> b[i];
        rep(j,0,b[i]){
            ll k; cin >> k;
            k--;
            c[i] += (1<<k);
        }
    }

    ll dp[1005][5000];
    Fill(dp, INFLL);
    dp[0][0] = 0;

    rep(i,0,M){
        rep(j,0,(1<<N)){
            chmin(dp[i+1][j], dp[i][j]);
            chmin(dp[i+1][j|c[i]], dp[i][j] + a[i]);
        }
    }

    if(dp[M][(1<<N)-1] < INFLL){
        cout << dp[M][(1<<N)-1] << ednl;
    }else{
        cout << -1 << enld;
    }
    return 0;
}


Measured memory_bytes: 42928
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<59)

#define int ll

#define MAX (10000000000LL)


int n,a,b,x;

bool solve(int mid, vector<int> h){
    rep(i,h.size()){
        h[i] = max<ll>(-1,h[i]-b*mid);
    }
    
    int ans = 0;
    rep(i,h.size()){
        if(h[i]<=0)continue;
        
        ans += (h[i]+(x-1))/x;
    }
    
    if(ans<=mid)return true;
    else return false;
}

signed main(){
    cin>>n;
    cin>>a>>b;
    
    x = a-b;
    
    vector<int> h(n);
    rep(i,n)cin>>h[i];
    
    ll left=0, right=MAX, mid=(left+right)/2LL;
    while(left+1<right){
        bool res = solve(mid,h);
        
        if(!res) left = mid;
        else    right= mid;
        
        mid = (left+right)/2LL;
    }
    
    cout<<mid+1<<endl;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
class E { static void Main() { new K(); } }
class K
{
	public K()
	{
		var N = int.Parse(Console.ReadLine());
		var ps = GetPrimes(99991);
		var p2 = new Dictionary<long, int>();
		foreach (var p in ps) p2.Add(p * (long)p, p);
		var z = new long[N];
		var cnt = new Dictionary<long, int>();
		var w = new Dictionary<long, long>();
		for (var i = 0; i < N; i++)
		{
			var num = long.Parse(Console.ReadLine());
			var fact = new List<int>();
			var t = 1L;
			for (var j = 0; j < ps.Count; j++)
			{
				var x = ps[j];
				var cube = x * (long)x * x;
				if (cube > num) break;
				if (num % x == 0)
				{
					fact.Add(x);
					while (num % cube == 0) num /= cube;
					if (num % (x * (long)x) == 0) t *= x;
					else if (num % x == 0) t *= x * (long)x;
				}
			}
			z[i] = num;
			if (!w.ContainsKey(z[i]))
			{
				foreach (var p in fact) while (num % p == 0) num /= p;
				if (p2.ContainsKey(num))  t *= p2[num];
				else { if (num <= 100000) t *= num * num; else t = -1; }
				w[z[i]] = t;
				cnt[z[i]] = 1;
			}
			else cnt[z[i]]++;
		}
		var sum = 0;
		var set = new HashSet<long>(z);
		var done = new HashSet<long>();
		if (set.Contains(1)) { sum++; set.Remove(1); }
		foreach (var x in set)
		{
			if (done.Contains(x)) continue;
			var y = w[x];
			if (cnt.ContainsKey(y)) sum += Math.Max(cnt[x], cnt[y]);
			else sum += cnt[x];
			done.Add(x);
			done.Add(y);
		}
		Console.WriteLine(sum);
	}
	List<int> GetPrimes(int n)
	{
		var m = (n - 1) >> 1;
		var primes = new List<int>((int)(n / Math.Log(n)));
		primes.Add(2);
		var composites = new bool[m];
		composites[0] = false;
		for (var p = 0; p < m; p++)
			if (!composites[p])
			{
				var pnum = 2 * p + 3;
				primes.Add(pnum);
				for (var k = 3 * p + 3; k < m; k += pnum) composites[k] = true;
			}
		return primes;
	}
}

Measured memory_bytes: 28288
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str,str1,str2;
        int n;
        String BREAKW = "-";

        while(true){
            str = sc.next();
            if(str.equals(BREAKW))break;
            n = sc.nextInt();

            for(int i=0;i<n;i++){
            	int h=sc.nextInt();
            	str1=str.substring(0,h);
            	str2=str.substring(h);
            	str=str2+str1;
            }
            System.out.println(str);
        }
        sc.close();
    }
}


Measured memory_bytes: 26340
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>


     
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;


ll dp[100100];
int main(){
    ll n, m;
    cin >> n >> m;
    vector<int> a(100100, 0);
    rep(i, m){
        ll tmp;
        cin >> tmp;
        a[tmp] = 1;
    }
    dp[0] = 1;
    rep(i, n){
        if(a[i] == 1)continue;
        dp[i] %= MOD;
        if(a[i + 1] != 1)(dp[i + 1] += dp[i]) % MOD;
        if(a[i + 2] != 1)(dp[i + 2] += dp[i]) % MOD;
        dp[i + 1] %= MOD;
        if(dp[i + 1] < 0)dp[i + 1] += MOD;
        dp[i + 2] %= MOD;
        if(dp[i + 2] < 0)dp[i + 2] += MOD;
    }
    dp[n] %= MOD;
    cout << dp[n] << endl;
}





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

using namespace std;

int main() {
    int x;
    cin >> x;
    vector<bool> count(1010, false);
    count.at(1) = true;
    for (int b = 2; b <= x; b++) {
        for (int p = 2; pow(b, p) <= x; p++) {
            count.at(int(pow(b, p))) = true;
        }
    }
    for (int i = x; i >= 1; i--) {
        if (count.at(i) == true) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 4128
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;



int main(){
     
    string s,str;
    int pos=0;
    
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'||s[i]=='1'){
            str[pos]=s[i];
            pos++;
        }
        else{
            if(pos!=0){
                str[pos-1]=' ';
                pos--;
            }
        }
    }
    for(int i=0;i<pos;i++){
        cout<<str[i];
    }
    cout<<endl;
     
    return 0;
}
 

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

const int maxn = 200010;
int h, w, n, x[maxn], y[maxn];
vector<int> G[maxn];
bool chk[maxn];

int main() {
    scanf("%d %d %d", &h, &w, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &x[i], &y[i]), G[y[i]].push_back(x[i]);
    }
    for (int i = 1; i <= w; i++) {
        G[i].push_back(h + 1);
    }
    sort(G[1].begin(), G[1].end());
    int ans = G[1][0] - 1, t = 0;
    for (int i = 2; i <= w; i++) {
        sort(G[i].begin(), G[i].end());
        int mx = 0;
        for (int j = 0; j < G[i].size(); j++) {
            if (G[i][j] <= i + t || chk[G[i][j] - 1]) {
                chk[G[i][j]] = 1, mx = max(mx, G[i][j]);
            } else {
                ans = min(ans, G[i][j] - 1); break;
            }
        }
        t = max(t, mx - i + 1);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 13056
def main():
    N = int(input())
    A = list(map(int, input().split()))

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            if (A[i] >> b) & 1 == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
                bs += 1
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()


Measured memory_bytes: 122940
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 3e3 + 5;

ll R,C,K,a[N][N],f[N][N][4];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>R>>C>>K;
    for(int i=1;i<=K;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	a[u][v]=w;
    }
    ll ans=0;
    for(int i=1;i<=R;i++)
    	for(int j=1;j<=C;j++)
    		for(int k=1;k<=3;k++)
    			f[i][j][k]=max(f[i-1][j][3]+a[i][j],max(f[i][j-1][k-1]+a[i][j],f[i][j-1][k]));
    cout<<f[R][C][3]<<'\n';
    return 0;
}

Measured memory_bytes: 355664
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int n, q, m, pre[100010];
char c;
int find(int x)
{
	while(x != pre[x]){
		x = pre[x];
	}
	return x;
}
int main()
{
	IO;
	while(cin >> n >> q){ 
		if(!n&&!q) break;
		ll sum=0;
		for(int i = 1; i <= n; i++){
			pre[i] = i;
		}
		for(int i = 2; i <= n; i++){
			cin >> pre[i];
		}
		for(int i = 0; i < q; i++){
			cin >> c >> m;
			if(c == 'Q') 
				sum += find(m);
			else {
				pre[m] = m;
			}
		}
		cout << sum << endl;
	}
	return 0;
}


Measured memory_bytes: 3580
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll n;
    cin>>n;
    V vec(n);
    ll res=0;
    rep(i,n)cin>>vec[i];
    map<ll,ll> mp;
    rep(i,n){
        mp[vec[i]]++;
        res+=vec[i];
    }
    ll q;
    cin>>q;
    rep(i,q){
        ll b,c;
        cin>>b>>c;
        ll k=mp[b];
        mp[b]=0;
        mp[c]+=k;
        res+=(c-b)*k;
        cout<<res<<endl;
    }
}


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

main() {
    char A[100],B[100],C[100];
    int a,b,c;
    cin>>A;
    cin>>B;
    cin>>C;

    a=strlen(A);
    b=strlen(B);
    c=strlen(C);

    if(A[a-1]==B[0] && B[b-1]==C[0])
        cout<<"YES";
    else
        cout<<"NO";
}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    ll ans = 0;
    rep(i,n){
        ll a; cin>>a;
        ans += --a;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  map<ll,ll> count;
  for(ll i=0;i<n;i++) {
    cin >> a[i];
    count[a[i]]++;
  }
  ll sum=0;
  for(auto p: count) {
    sum+=p.second*(p.second-1)/2;
  }
  for(ll i=0;i<n;i++) {
    ll t=count[a[i]];
    ll ans=sum-t*(t-1)/2;
    if(t>1) ans+=(t-1)*(t-2)/2;
    if(ans<0) ans=0;
    cout << ans << endl;
  }
}

Measured memory_bytes: 11008
N = int(input())
As = list(map(int, input().split()))
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
gcdsl = [0]*(N+1)
for i in range(N):
  a = gcdsl[i]
  b = As[i]
  gcdsl[i+1] = calcgcd(a, b)
#print(gcdsl)
gcdsr = [0]*(N+1)
for i in reversed(range(N)):
  a = gcdsr[i+1]
  b = As[i]
  gcdsr[i] = calcgcd(a, b)
#print(gcdsr)
gcds = [0]*N
for i in range(N):
  a = gcdsl[i]
  b = gcdsr[i+1]
  gcds[i] = calcgcd(a, b)
#print(gcds)
print(max(gcds))


Measured memory_bytes: 14080
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		int N = sc.nextInt();
		long[] vals = new long[N+1];
		for (int i = 0; i < N + 1; i++) {
			vals[i] = sc.nextLong();
		}
		boolean can = true;
		long ans = 0;
		long[] cant = new long[N + 2];
		cant[0] = 1;
		long totSum = 1;
		int from = 0, to = 1;
		for (int i = 0; i < N + 1 && can; i++) {
			while (vals[i] > 0 && from < to) {
				long min = Math.min(vals[i], cant[from]);
				ans += min * (to - from);
				vals[i] -= min;
				cant[from] -= min;
				totSum -= min;
				if (cant[from] == 0) from++;
			}
			if (vals[i] > 0) can = false;
			cant[to++] = totSum;
			totSum *= 2;
			totSum = Math.min(totSum, Long.MAX_VALUE / 4);
		}
		out.println(can ? ans : -1);
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}


Measured memory_bytes: 45192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi acos(-1)
double eps=1e-8;
main(){
    double a,b;int h,m;
    cin>>a>>b>>h>>m;
    int hour=h%12,minute=m;
    hour=double(hour),minute=double(minute);
    double angle=fabs(hour*30.0+minute/2.0-minute*6.0)*pi/double(180);
    printf("%.20f",sqrt(a*a+b*b-2.0*a*b*cos(angle)));
}


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

// Template Headers {{{
using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long; using vll = vector<long long>;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
template <class T> struct Inf { static constexpr T inf() { return std::numeric_limits<T>::has_infinity ? std::numeric_limits<T>::infinity() : std::numeric_limits<T>::max(); } };
template <> struct Inf<int> { static constexpr int inf() { return 0x3f3f3f3f; } };
template <> struct Inf<long long> { static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; } };
constexpr int INF = Inf<int>::inf(); constexpr ll BINF = Inf<ll>::inf();
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}

int solve() {
	ll x; cin >> x;
	ll now = 100;
	int ans = 0;
	while (now < x) {
		now += now / 100;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

// Template Main {{{
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	// precompute();
	// int t; cin >> t; for (int i=1;i<=t;i++)
	solve();
	// cout << "Case #" << i << ": ", solve();
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker


Measured memory_bytes: 3648
import numpy as np

N = int(input())
A = np.array([int(input()) for _ in range(N)])

total = A.sum()
if total%10 == 0:
  if np.any(A%10 != 0):
    total -= A[A%10 != 0].min()
  else:
    total = 0
print(total)    

Measured memory_bytes: 12520
/**
*	created: 24.08.2020 21:32:00
**/
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
using ll = long long;
using P = pair<int,int>;
// #define endl '\n'
#define int long long
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rep2(i,s,n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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 long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1ll << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;



signed main() {

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

    int n; cin >> n;
    vector<int> v;
    v.push_back(2);
    rep2(i,3,55556) {
        bool ok = true;
        rep2(j,2,sqrt(i)+1) if (i % j == 0) ok = false;
        if (ok) v.push_back(i);
    }
    vector<int> v1;
    for (auto p : v) if (p % 5 == 1) v1.push_back(p);
    rep(i,n) {
        if (i == 0) cout << v1[i];
        else cout << " " << v1[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3708
#include<iostream>
using namespace std;
int main(){
    int n,i,t=0;
    string s;
    cin>>n>>s;
    for(i=0;i<n;i++){
    if(s[i]=='A'){
            if(s[i+1]=='B'){
                if(s[i+2]=='C'){
                    t++;
                }
            }
        }
}
    cout<<t<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define FASTIO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define ll long long int
#define F first
#define S second
#define pll pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vpii vector<pair<int,int> >
#define vvpii vector<vpii >
#define vpll vector<pair<ll,ll> >
#define vvpll vector<vpll >
#define pb push_back
#define MOD 1000000007

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;

struct compare {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		if ((a.S - a.F) != (b.S - b.F)) return ((a.S - a.F) > (b.S - b.F));
		else return (a.F < b.F);
	}
};

const int mx = 305;
double p[mx][mx][mx], ev[mx][mx][mx];
int n;

int main() {
/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/
	FASTIO;
	cin >> n;
	vi cnt(4);
	for (int i = 0; i < n; i++) {
		int temp; cin >> temp;
		cnt[temp]++;
	}
	p[ cnt[1]][cnt[2]][cnt[3]] = 1;
	for (int c = n; c >= 0; c--) {
		for (int b = n; b >= 0; b--) {
			for (int a = n; a >= 0; a--) {
				if (a == 0 && b == 0 && c == 0) continue;
				if (a + b + c > n) continue;
				double p_waste = (double)(n - (a + b + c)) / n;
				ev[a][b][c] += p_waste / (1 - p_waste) * p[a][b][c];
				if (a != 0) {
					p[a - 1][b][c] += p[a][b][c] * a / (a + b + c);
					ev[a - 1][b][c] += ev[a][b][c] * a / (a + b + c);
				}
				if (b != 0) {
					p[a + 1][b - 1][c] += p[a][b][c] * b / (a + b + c);
					ev[a + 1][b - 1][c] += ev[a][b][c] * b / (a + b + c);
				}
				if (c != 0) {
					p[a][b + 1][c - 1] += p[a][b][c] * c / (a + b + c);
					ev[a][b + 1][c - 1] += ev[a][b][c] * c / (a + b + c);
				}
			}
		}
	}
	double ans = ev[0][0][0] + cnt[1] + 2 * cnt[2] + 3 * cnt[3];
	// cout << ev[0][0][0] + cnt[1] + 2 * cnt[2] + 3 * cnt[3] << endl;
	printf("%.10lf\n", ans);

}

Measured memory_bytes: 438528
#include <stdio.h>
#include <math.h>

typedef struct{
  double x;
  double y;
}Point;

void koho(int, Point, Point);

int main () {
  int n = 0;
  Point p1, p2;

  p1.x = 0.0;
  p1.y = 0.0;
  p2.x = 100.0;
  p2.y = 0.0;

  scanf("%d",&n);

  printf("%.8lf %.8lf\n",p1.x,p1.y);
  koho(n, p1, p2);
  printf("%.8lf %.8lf\n",p2.x,p2.y);

  return 0;
}


void koho(int n, Point p1, Point p2) {
  Point s, t, u;
  if(n == 0) return;

  s.x = (2*p1.x + p2.x) / 3;
  s.y = (2*p1.y + p2.y) / 3;
  t.x = (p1.x + 2*p2.x) / 3;
  t.y = (p1.y + 2*p2.y) / 3;
  u.x = cos(M_PI/3) * (t.x - s.x) - sin(M_PI/3) * (t.y - s.y) + s.x;
  u.y = sin(M_PI/3) * (t.x - s.x) + cos(M_PI/3) * (t.y - s.y) + s.y;

  koho(n - 1, p1, s);

  printf("%.8lf %.8lf\n",s.x,s.y);
  koho(n - 1, s, u);
 
  printf("%.8lf %.8lf\n",u.x,u.y);
  koho(n - 1, u, t);
  
  
  printf("%.8lf %.8lf\n",t.x,t.y);
  koho(n - 1, t, p2);
 
  
}



Measured memory_bytes: 2104
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

#define FOR(i,m,n) for(ll (i)=(m); (i)<(ll)(n); ++(i))
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin,(a).end

ll gcd(ll a, ll b){
  return a%b ? gcd(b, a%b) : b;
}

ll lcm(ll a, ll b){
  return a / gcd(a, b) * b; // prevent from overflowing
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  cout << lcm(n, 2) << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func fizz(ary []int) int {
	var count int
	for i := range ary {
		if ary[i] % 2 == 0{
			count +=1
		}else{
			break
		}
	}
	return count
}

func division(ary []int) []int {
	var tmp []int
	for i := range ary {
		tmp = append(tmp, ary[i]/2)
	}
	return tmp
}

func main()  {
	var n int
	count := 0
	fmt.Scan(&n)
	// 1, 2, 3 ... の入力法
	ary := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ary[i])
	}
	for {
		if len(ary) == fizz(ary) {
			ary = division(ary)
			count +=1
		}else{
			break
		}
	}
	fmt.Println(count)
}


Measured memory_bytes: 640
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)
	var q int
	fmt.Scan(&q)
	var t, f int
	var c string
	var reverseTime int
	isReverse := true
	set := make([]string, 2*q+1)
	set[q] = s
	for i := 0; i < q; i++ {
		fmt.Scan(&t)
		if t == 1 {
			reverseTime++
			isReverse = !isReverse
		} else {
			fmt.Scanf("%d %s", &f, &c)
			if (f == 1 && isReverse) || (f == 2 && !isReverse) {
				set[q-i-1] = c
			} else {
				set[q+i+1] = c
			}
		}
	}
	if reverseTime%2 == 1 {
		set = reverse(set)
		set[q] = reverseString(s)
	}
	result := strings.Join(set, "")
	fmt.Println(result)
}

func reverseString(s string) string {
	rs := []rune(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		rs[i], rs[j] = rs[j], rs[i]
	}
	return string(rs)
}

func reverse(input []string) []string {
	if len(input) == 0 {
		return input
	}
	return append(reverse(input[1:]), input[0])
}


Measured memory_bytes: 130048
//https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_a
//A - Thumbnail
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
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;}
int main() {
    ll N; cin>>N;
    vector<ll> an(N);
    double ave=0;
    for(auto&& a:an){
        cin>>a;
        ave += a;
    }
    ave /= (double)(N);
    ll ans=0;
    double dist=INT64_MAX;
    FOR(i,0,N){
        if (chmin(dist,abs((double)an.at(i)-ave))) {
            ans = i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define MOD 998244353
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
#define ar array
#define ld long double
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
char c[4]={'D' , 'R' , 'U' , 'L'};
const ll maxN=3e3+5;
ll n , dp[maxN][maxN][2] , a[maxN] , sum;
void solve(){
	cin>> n ;
	for(ll i=0;i<n ; i++)cin>>a[i] , sum+=a[i];

	for(ll i=0;i<n ; i++){
		dp[i][i][0]=a[i];
		dp[i][i][1]=0;
	}
	for(ll i=1;i<n ;i++){
		for(ll j=0 ; j+i<n ; j++){
			ll L= j , R=L+i;
			dp[L][R][0]=max(a[L]+dp[L+1][R][1] , a[R]+dp[L][R-1][1]);
			dp[L][R][1]=min(dp[L+1][R][0] , dp[L][R-1][0]); 
		}
	}
	ll ans= 2*dp[0][n-1][0]-sum;
	cout<<ans<<endl;
}

int main(){
	//mahakal();
	fast;
	ll t =1 ;
	//cin>> t ; 
	while(t--)solve();
	//cerr << "\ntime taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
	return 0;
}

Measured memory_bytes: 85428
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func floatScanner() float64 {
	n, _ := strconv.ParseFloat(Scanner(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func stringSliceScanner(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scanner()
	}
	return a
}
func intSliceScanner(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = intScanner()
	}
	return a
}

var mod int

func main() {
	mod = 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	s := Scanner()
	x := []int{0, 0, 0}
	for _, r := range s {
		x[r-97]++
	}
	sort.Ints(x)
	if x[2]-x[0] <= 1 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 896
import collections

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n-1)]
px = [list(map(int, input().split())) for _ in range(q)]

c = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)

point = [0] * n
for p, x in px:
    point[p-1] += x

parents = [0] * n
ans = [0] * n
q = collections.deque()
q.append(0)
while q:
    v = q.pop()
    ans[v] = ans[parents[v]] + point[v]
    for i in c[v]:
        if i == parents[v]:
            continue
        parents[i] = v
        q.append(i)
print(' '.join(list(map(str, ans))))

Measured memory_bytes: 150052
#include<stdio.h>
#include<stdlib.h>        //何に使うの？

int top, num[1000];     //S[100]にしたらエラー起こった　1000にしたら解決した

void push(int x){
    top++;
    num[top]=x;        //2行をまとめてS[++top]=xとしてもよい
}

int pop(){
    top--;
    return num[top+1];
}

int main(){
    int a,b;
    top=0;
    char s[100];

    while(scanf("%s", s) != EOF){    //これ何？
        if(s[0] == '+'){
            b=pop();
            a=pop();
            push(a+b);
        }else if(s[0] == '-'){
            b=pop();
            a=pop();
            push(a-b);
        }else if(s[0] == '*'){
            b=pop();
            a=pop();
            push(a*b);
        }else{
            push(atoi(s));            //これ何？
        }
    }
    printf("%d\n", pop());
    return 0;
}


Measured memory_bytes: 2112
#include <iostream>
#include <string>
#include <stddef.h>
#include <stack>
#include <queue>

using namespace std;

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

}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define dd double
#define f0(i, n) for(int i = 0; i < n; i++)
#define fab(i,a,b) for(int i=a;i<b;i++)
#define f1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second


int n, m;
int dp[100005];
int vis[100005];
vector<int>adj[100006];


void dfs(int v) {

	vis[v] = 1;

	for (auto u : adj[v]) {

		if (!vis[u]) {
			dfs(u);
		}
		dp[v] = max(dp[v], dp[u] + 1);
	}
}


int main() {


	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif


//ios_base& scientific (ios_base& str);
	cin >> n >> m;

	for (int i = 0; i < m; i++) {

		int x, y;
		cin >> x >> y;

		adj[x].pb(y);

	}


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

		if (!vis[i]) {
			dfs(i);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {

		ans = max(ans, dp[i]);
	}
	cout << ans << endl;




	return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 1e3;
const lli INF = 1e18;
const lli MOD = 200003;

vi m;
vi primes(1,2);
vector<vector<ld>>nk;
void sieve(){
	m = vi(N+1,0);
	for(int i = 4; i<N; i+=2)m[i]=1;
	for(int i = 3; i*i<=N; i+=2)if(!m[i])for(int j = i*i; j<N; j+=i)m[j]=1;
	for(int i = 3; i<N; i+=2)if(!m[i])primes.pb(i);
}

void pascal(){
	nk =vector<vector<ld>>(N,vector<ld>(N,0.0));
	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;
	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];
}

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

lli lcm(lli a, lli b){
	if(a<b)swap(a,b);
	lli c = gcd(a,b);
	a/=c;
	return a*b;
}

int popcount(lli x) { return __builtin_popcountll(x); }

lli poww(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = res * a;
		a = a*a;
		b/=2;
	}
	return res;
}

lli powm(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = (res * a)%MOD;
		a = (a*a)%MOD;
		b/=2;
	}
	return res;
}

bool isPrime(lli x){
	if(x==1)return 0;
	for(auto i:primes){
		if(i*i>x)return 1;
		if(x%i==0)return 0;
	}
	return 1;
}

// ---- コーディングはここから！ ('-')7

int main(){_
	string s; cin>>s;
	int mx = 0;
	fore(i,0,sz(s)){
		int r = 0;
		fore(j,i,sz(s))if(s[j]=='S')break;else r++;
		mx = max(mx,r);
	}
	cout<<mx<<ENDL;


}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

const int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int N;
    cin >> N;
    vector<string> s(N);
    rep(i, N) cin >> s[i];

    int res = 0, as = 0, bs = 0, ab = 0;

    rep(i, N) {
        int n = s[i].size();
        for (int j = 0; j < n-1; j++) {
            if (s[i][j] == 'A' && s[i][j+1] == 'B') res++;
        }
        if (s[i][0] == 'B' && s[i][n-1] != 'A') bs++;
        if (s[i][n-1] == 'A' && s[i][0] != 'B') as++;
        if (s[i][0] == 'B' && s[i][n-1] == 'A') ab++;
    }

    if (ab == 0) {
        res += min(as, bs);
    }
    else {
        if (as == 0 && bs == 0) {
            res += ab-1;
        }
        else {
            res += ab + min(as, bs);
        }
    }

    cout << res << endl;
    return 0;
}


Measured memory_bytes: 768