akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
#define ll long long
using namespace std;

int main() {
    int n, m, x, suma = 0, sumb = 0;
    cin >> n >> m >> x;
    vector<int> a(m);
    rep(i, n) cin >> a[i];
    for(int i = 0; i < m; i++) {
        if(a[i] < x)
            suma++;
        else
            sumb++;
    }

    int ans = min(suma, sumb);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n, m;
    while(1) {
    int count = 0;
        cin >> n >> m;
        if (n == 0 && m == -0) {
            break;
        }
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int p = j + 1; p <= n; p++) {
                        if (i + j + p == m) {
                            count++;
                        }
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}


Measured memory_bytes: 3076
/*
 
dunjen_master
 
*/
 

#include<bits/stdc++.h>

 
using namespace std;
 
const int MAX_N = int(1e6) + 10;
const long long int MOD=1e9+7;
const long long int INF=1e18;

typedef long long int ll;

ll mul(ll a,ll b){

    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll c=a*b;
    c=(c+MOD)%MOD;
    return c;
}
ll add(ll a,ll b){
    a=(a+MOD)%MOD;
    b=(b+MOD)%MOD;
    ll ans=(a+b);
    ans=(ans+MOD)%MOD;
    return ans;
}
ll power(ll a,ll b,ll c=0){
    ll ans=1;
    while(b){
        if(b&1){
            ans=mul(ans,a);
        }
        a=mul(a,a);
        b=b/2;
    }
    return ans;
}


vector<char>v;

char ulta(char c1,char c2){
    
    for(int i=0;i<3;i++){
        if(v[i]==c1 || v[i]==c2){
            ;
        }else{
            return v[i];
        }
    }

    return 'B';
}

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

        v.push_back('R');
    v.push_back('G');
    v.push_back('B');

    int n;
    cin>>n;

    string s;
    cin>>s;

    ll ans=0;

    for(int i=0;i<n;i++){
        map<char,int>mp;
        for(int j=n-1;j>i;j--){
            if(s[i]!=s[j]){
                char ch=ulta(s[i],s[j]);
                ans+=mp[ch];
                if(j+(j-i)<n && s[j+j-i]==ch)ans--;
            }
            mp[s[j]]++;
        }
    }

    cout<<ans<<endl;

    
    
    
    
 
    
}

    

    
 
    



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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;



int main()
{
	int h, w;
	cin >> h >> w;
	string s[h];
	for (int i = 0; i < h; ++i) {
		cin >> s[i];
	}


	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (s[i][j] == '.') {
				continue;
			}
			if (i > 0) {
				if (s[i-1][j]=='#') {
					continue;
				}
			}
			if (i < h) {
				if (s[i+1][j]=='#') {
					continue;
				}

			}
			if (j > 0) {
				if (s[i][j-1]=='#') {
					continue;
				}

			}
			if (j < w) {
				if (s[i][j+1]=='#') {
					continue;
				}
			}
			cout << "No" << "\n";
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Rule{
public:
  bool f;
  string a, b;
};

class Packet{
public:
  string a, b, c;
};

Rule rules[1024];
vector<Packet> ans;
int n, m;

bool check2(string a, string b){
  if(a.size() != b.size()) return false;
  for(int i=0;i<a.size();i++) if(a[i] != '?' && a[i] != b[i]) return false;
  return true;
}

bool check(string a, string b){
  bool res = false;
  for(int i=0;i<n;i++) if(check2(rules[i].a, a) && check2(rules[i].b, b)) res = rules[i].f;
  return res;
}

main(){
  while(cin >> n >> m && (n|m)){
    ans.clear();
    for(int i=0;i<n;i++){
      string in;
      cin >> in;
      if(in == "permit") rules[i].f = true;
      else rules[i].f = false;
      cin >> rules[i].a >> rules[i].b;
    }
    for(int i=0;i<m;i++){
      Packet in;
      cin >> in.a >> in.b >> in.c;
      if(check(in.a, in.b)) ans.push_back(in);
    }
    cout << ans.size() << endl;
    for(int i=0;i<ans.size();i++){
      cout << ans[i].a << ' ' << ans[i].b << ' ' << ans[i].c << endl;
    }
  }
}

Measured memory_bytes: 1048
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
char s[105];
int main()
{
    while(~scanf("%s",&s)){
        int len = strlen(s);
        printf("%c%d%c\n",s[0],len-2,s[len-1]);
    }
}

Measured memory_bytes: 256
def check(n):
    m = 2
    dic = {}
    while n > 1:
        if n%m == 0:
            while n%m == 0:
                if m in dic:
                    dic[m] += 1
                else:
                    dic[m] = 1
                n //= m
        m += 1
    lis = []
    for i in dic.values():
        lis.append(i)
    if len(set(lis)) == 1 and lis[0] != 1:
        return True
    else:
        return False
x = int(input())
if x == 1 or x == 2 or x == 3:
    print(1)
    quit()
for i in range(x+1):
    if check(x-i):
        print(x-i)
        quit()

Measured memory_bytes: 3064
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

std::string GetEncryptedString(std::string s){
  for(char target='b';target<='z';target++){
    for(int i=0;i<s.size();i++){
      if(s[i]==target){
        s[i]=target-1;
        if(s[i]<'a')s[i]='z';
        break;
      }
    }
  }

  return s;
}

void Solve(std::string s){
  std::vector<std::string> substr;
  for(int i=0;i<s.size();i++){
    substr.push_back(s.substr(0,i+1));
  }
  std::vector<std::string> result;

  std::stack<std::string> stack;
  char top=s[0];
  stack.push(std::string{top});
  top++;
  if(top>'z')top='a';
  stack.push(std::string{top});
  while(!stack.empty()){
    std::string curr=stack.top();
    stack.pop();
    if(GetEncryptedString(curr)!=substr[curr.size()-1]){
      continue;
    }
    if(curr.size()==s.size()){
      result.push_back(curr);
      continue;
    }
    char c=s[curr.size()];
    stack.push(curr+std::string{c});
    c++;
    if(c>'z') c='a';
    stack.push(curr+std::string{c});
  }

  std::sort(result.begin(), result.end());
  cout<<result.size()<<endl;
  if(result.size()<=10){
    for(auto& r:result){
      cout<<r<<endl;
    }
  }else{
    for(int i=0;i<5;i++){
      cout<<result[i]<<endl;
    }
    for(int i=0;i<5;i++){
      cout<<result[result.size()-5+i]<<endl;
    }
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  while(true){
    std::string s;
    cin>>s;
    if(s=="#") break;
    Solve(s);
  }




  return 0;
}


Measured memory_bytes: 4192
#include <iostream>
#include <algorithm>
using namespace std;
int c[2][110];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<2;++i)for(int j=0;j<n;++j)cin>>c[i][j];
  int sum=c[0][0];
  for(int i=0;i<n;++i)sum+=c[1][i];
  int res=sum;
  for(int i=1;i<n;++i){
    sum=sum+c[0][i]-c[1][i-1];
    res=max(res,sum);
  }
  cout<<res<<endl;
}


Measured memory_bytes: 256
"""
Writer: SPD_9X2
https://atcoder.jp/contests/apc001/tasks/apc001_e

厳密な照明は難しいが…
直径を取る
直径の端点からbfs

全ての頂点に関して、部分木に少なくとも一つのアンテナを持つかのフラグを管理
子の数をkとする。その内x個がtrueの場合、k-1-x個のアンテナを追加。自分のflagをtrueにする
子がfalseで、子が0 or 1つしかない場合のみfalse継続

簡単な木では最適になることを実験したがどうだろうか…？
"""
import sys
sys.setrecursionlimit(3*10**5)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis,now

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    lis[a].append(b)
    lis[b].append(a)

td,tp,stp = NC_Dij(lis,0)


ans = 0

def dfs(v,p):

    x = 0
    c = 0
    retflag = False
    for nex in lis[v]:

        if nex != p:
            c += 1
            have = dfs(nex,v)
            retflag = have or retflag
            if have:
                x += 1

    if c-1-x > 0:
        retflag = True
    global ans
    ans += max(0,c-1-x)

    return retflag

dfs(stp,stp)
print (ans+1)



Measured memory_bytes: 114636
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer X = sc.nextInt();
        Integer N = sc.nextInt();
        List<Integer> p = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            p.add(sc.nextInt());
        }
        sc.close();

        if (N == 0) {
            System.out.println(X);
            return;
        }

        Collections.sort(p);

        for (int i = 0; i < 100; i++) {
            if (!p.contains(X - i)) {
                System.out.println(X - i);
                return;
            }
            if (!p.contains(X + i)) {
                System.out.println(X + i);
                return;
            }
        }
    }
}


Measured memory_bytes: 35868
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.Set;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class CGacha {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();

            Set<String> items = new HashSet<>();

            for (int i = 0; i < n; i++) {
                String item = in.next();
                items.add(item);
            }

            out.println(items.size());
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }
}



Measured memory_bytes: 71728
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e2 + 10;
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string str;
	cin >> str;
	sort(str.begin(), str.end());
	if (str == "abc") puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct P{
  int rank; char suit;
};

P card[4][16];
int  point[2];
char trump;
map<char, int>m;

P add_card(string s){ return (P){m[s[0]], s[1]}; }

int solve(int sm, vector<P> v){
  int winner = -1;
  rep(i,4){
    if(trump == v[i].suit && ( winner == -1 || v[winner].rank < v[i].rank)) winner = i;
  }

  if(winner!=-1) return winner;

  rep(i,4){
    if(v[sm].suit == v[i].suit && (winner == -1 || v[winner].rank < v[i].rank)) winner = i;
  }

  return winner;
}

int main(){
  m['A']=14;m['2']=2;m['3']=3;m['4']=4;m['5']=5;m['6']=6;m['7']=7;m['8']=8;m['9']=9;m['T']=10;m['J']=11;m['Q']=12;m['K']=13;
  while(cin >> trump && trump != '#'){
    rep(i,4) rep(j,13){
      string s; cin >> s;
      card[i][j] = add_card(s);
    }
    //    rep(i,4){ rep(j,13) cout << card[i][j].rank << " " << card[i][j].suit << " "; cout << endl; }

    point[0]=point[1]=0;
    int sm=0;// start member
    rep(i,13){
      vector<P>v; rep(j, 4) v.push_back(card[j][i]); 
      int winner = solve(sm, v);
      point[winner%2]++;
      sm = winner;
     }

    if(point[0]>point[1]) cout << "NS " << point[0]-6 << endl;
    else cout << "EW " << point[1]-6 << endl;
  }
  return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define SLL(x, n) ((x) << (n))
#define SRL(x, n) ((x) >> (n))
#define MIN2(a, b) ((a) < (b)) ? (a) : (b)
#define MAX2(a, b) ((a) > (b)) ? (a) : (b)
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

template<typename T> inline void fill(T array[], T value) {for(T t: array) t = value;}
inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}

using namespace std;
using ll = long long;
using pint = pair<int, int>;

int N, M;
vector<int> V;
vector<pint> U;

signed main(){
    int A, B, C;
    in(N); in(M);
    REP(i, N){
        in(A);
        V.push_back(A);
    }
    REP(i, M){
        in(B);
        in(C);
        U.push_back(MP(B, C));
    }
    sort(ALL(V), greater<int>());
    sort(ALL(U), [](pint x, pint y) -> bool{return (x.second > y.second);});
    ll sum = 0;
    auto iv = V.begin();
    auto iu = U.begin();
    REP(i, N){
        B = iu->first; C = iu->second;
        if(iu < U.end() && *iv < C){
            int j;
            for(j = i; j < i + B; j++){
                if(j >= N) break;
                sum += C;
            }
            i = j - 1;
            iu++;
        }else{
            sum += *iv;
            iv++;
        }
    }
    PRINT(sum);
    return 0;
}

Measured memory_bytes: 1784
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
 
 
 
 
 
 
 


int n;
ll a,b;
int main()
{
     cin>>n>>a>>b;
     vector<ll> ar(n);rep(i,n)cin>>ar[i];
     int l=0,r=1e17;
     int mid;
     while(l<r){
          mid=l+(r-l)/2;
          ll sum=0;
          for(int i=0;i<n;i++){
              if(ar[i]-mid*b>0){
                   sum+=(ar[i]-mid*b+a-b-1)/(a-b);
              }
              if(sum>mid)break;
          }
          if(mid<sum)l=mid+1;
          else r=mid;
          
     }
     cout<<r;
}























Measured memory_bytes: 3984
A, B = map(int, input().split())
ans = 0


def kaibun(x):

    half = len(x) // 2
    front = x[:half][::-1]
    back = x[half+1:]

    if front == back:
        return True

    else:
        return False


for i in range(A, B+1):
    list_i = list(str(i))
    func = kaibun(list_i)

    if func:
        ans += 1

print(ans)


Measured memory_bytes: 3060
N, W = map(int, input().split())

wv = []
for i in range(N):
    wv.append(list(map(int, input().split())))
    
dp = [[10**15 for i in range(10**5+1)] for j in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for sum_v in range(10**5+1):
        if sum_v - wv[i][1] >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v - wv[i][1]] + wv[i][0], dp[i][sum_v])
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

ans = 0
for sum_v in range(10**5+1):
    if dp[N][sum_v] <= W:
        ans = sum_v

print(ans)

Measured memory_bytes: 171528
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  int N;
  cin >> N;
  int x,y;
  int sum = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> x >> y;
    sum += y - x + 1;
  }
  
  cout << sum << endl;
 
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

int A, B;
string S;

int main() {
  cin >> A >> B;
  cin >> S;
  repe(i, 1, A + B + 1) {
    if (i == A + 1) {
      if (S[i - 1] != '-') {
        cout << "No" << endl;
        return 0;
      }
      continue;
    }

    char c = S[i - 1] - '0';
    if (c < 0 || c > 9) {
      cout << "No" << endl;
      return 0;
    }
    continue;
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i, 0, n) {
        cin >> a[i];
    }
    vector<ll> sum(n + 1, 0);
    REP(i, 0, n) {
        sum[i + 1] = sum[i] + a[i];
    }
    const ll inf = 1LL << 60;
    // [l, r)
    auto func = [&](int l, int r) -> int {
        int bl = l, br = r - 2;
        ll diff = inf;
        int res = -1;
        while (bl <= br) {
            int mid = (bl + br) / 2;
            ll lsum = sum[mid + 1] - sum[l];
            ll rsum = sum[r] - sum[mid + 1];
            ll d = abs(lsum - rsum);
            if (diff > d) {
                diff = d;
                res = mid;
            }
            if (lsum > rsum) {
                br = mid - 1;
            } else {
                bl = mid + 1;
            }
        }
        return res + 1;
    };
    ll ans = inf;
    REP(i2, 2, n - 1) {
        int i1 = func(0, i2);
        int i3 = func(i2, n);
        vector<ll> pos = {sum[n] - sum[i3], sum[i3] - sum[i2], sum[i2] - sum[i1], sum[i1]};
        ll vmin = *min_element(pos.begin(), pos.end());
        ll vmax = *max_element(pos.begin(), pos.end());
        chmin(ans, vmax - vmin);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int n, q;
string s;
vector<string> vec;

int end(int it){
    for(auto i : vec){
        if(s[it] == i[0]){
            if(i[1] == 'L')
                it --;
            else
                it ++;
        }
        if(it<0)
            return -1;
        if(it>=n)
            return n;
    }
    return 0;
}

int main(){
    cin >> n >> q >> s;
    for(int i=0 ; i<q ; i++){
        char c, cc;cin >> c >> cc;
        string t;
        t.push_back(c);
        t.push_back(cc);
        vec.push_back(t);
    }
    int l=-1, r=n;
    while(r-l>1){
        int mid = (l + r)/2;
        //check left
        if(end(mid) == -1)
            l = mid;
        else
            r = mid;
    }
    int cnt = l+1;
    l = -1;
    r = n;
    while(r-l>1){
        int mid = (l + r)/2;
        //check right
        if(end(mid) == n)
            r = mid;
        else
            l = mid;
    }
    cnt += n-r;
    cout << n-cnt << "\n";
    return 0;
}



Measured memory_bytes: 13372
from collections import Counter
from functools import reduce
import fractions
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


s = IS()
if s[0] == 'A' and s[2:len(s)-1].count('C') == 1 and ''.join([s[i] for i in range(1, len(s)) if not i == s.index('C')]).islower():
    print('AC')
else:
    print('WA')



Measured memory_bytes: 5184
#include<bits/stdc++.h>
#define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++)
#define all(v) (v).begin(), (v).end()
#define SZ(v) (int)((v).size())
#define pb push_back
#define ft first
#define sd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const long long INF = 1e18L + 1;
const int IINF = 1e9 + 1;

using namespace std;

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int main() {
	#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	#endif
	int n;
	cin >> n;
	vector<int> v(n);
	rep (i, 0, n) {
		cin >> v[i];
	}
	int w = 0;
	rep (i, 1, n) {
		if (v[i - 1] == v[i]) {
			w++;
			i++;
		}
	}
	cout << w;
}


Measured memory_bytes: 256
from collections import deque

N = int(input())

q = deque([i for i in range(1,10)])

for _ in range(N-1):
  i = q.popleft()
  if i % 10 == 0:
    q.append(i*10)
    q.append(i*10+1)
  elif i % 10 == 9:
    q.append(i*10+8)
    q.append(i*10+9)
  else:
    q.append(i*10+i%10-1)
    q.append(i*10+i%10)
    q.append(i*10+i%10+1)
    
print(q[0])

Measured memory_bytes: 83252
#include<iostream>
using namespace std;
int main(){
  int n,walk,sum,walk_p,p,d1,d2;
  cin >> n;
  while(n!=0){
    walk=-1;
    walk_p=-1;
    for(int i=0;i<n;i++){
      cin >> p >> d1 >> d2;
      sum=d1+d2;
      if(sum>walk){
	walk_p=p;
	walk=sum;
      }
    }
    cout << walk_p << " " <<walk<<endl;
    cin >> n;
  }
  return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
 
using namespace std;
 
#define sf(n) scanf("%d", &n)
#define pd(n) printf("%.10lf", n)
#define pf(n) printf("%d", n)
#define p() printf("\n")
#define ps() printf(" ")
#define ll long long
#define ull unsigned long long
#define MAX 1e9
const int mod = 1000 * 1000 * 1000 + 7;
#define ex 1e18
#define dbl 2e09
#define qu(q) queue<int> q
#define pqu(q) priority_queue<int> q
#define len(s) s.length()
#define sz(x) int(x.size())
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define clr(x) x.clear()
#define LOG(x) std::cout << x << std::endl;
 
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.14159265359;
 
int dx[6] = {-1,-1,0,0,1,1};
int dy[6] = {-1,0,-1,1,0,1};

const int N=2e5+5;
int a[N];
map<int,int>mp;

int main(){
    int n,q;
    cin>>n;
    ll sum=0;
    for(int i=0;i<n;++i){
        cin>>a[i];
        mp[a[i]]+=1;
        sum+=a[i];
    }
    cin>>q;
    while(q--){
        int b,c;
        cin>>b>>c;
        //cout<<b<<" "<<c<<endl;
        //cout<<mp[b]<<" "<<mp[c]<<endl;
        sum-=b*1LL*mp[b];
        sum+=c*1LL*(mp[b]);
        mp[c]+=mp[b];
        mp[b]=0;
        cout<<sum<<endl;
        //cout<<mp[b]<<" "<<mp[c]<<endl;
    }
    return 0;
}







Measured memory_bytes: 8432
#include <stdio.h>
typedef long long ll;
#define MOD 1000000007
int main() {
	int n, m;
	ll ans = 0;
	scanf("%d%d", &n, &m);
	if (n == m || n - 1 == m || n == m - 1) {
		if (n == m)
			ans = 2;
		else
			ans = 1;
		for (int i = 1; i <= n; i++) {
			ans *= i;
			ans %= MOD;
		}
		for (int i = 1; i <= m; i++) {
			ans *= i;
			ans %= MOD;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

#define int long long
#define all(s) s.begin(), s.end()
#define vi vector<int>
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second

const int N = 5005;

int d[N], a[N];
int cnt[N];

main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int k, q;
    cin >> k >> q;
    for (int i = 0; i < k; i++) cin >> d[i];
    while (q--) {
        int n, x, m;
        cin >> n >> x >> m;
        a[0] = d[0] % m;
        cnt[0] = (d[0] % m == 0);
        for (int i = 1; i < k; i++) {
            a[i] = d[i] % m;
            cnt[i] = (d[i] % m == 0);
            a[i] = a[i - 1] + a[i];
            cnt[i] = cnt[i - 1] + cnt[i];
        }
        int sum = 0;
        int sumcnt = 0;
        int foo = (n - 2) / k;
        sum = foo * a[k - 1];
        sumcnt = foo * cnt[k - 1];
        sum += a[(n - 2) % k];
        sumcnt += cnt[(n - 2) % k];
        sum += (x % m);
        cout << n - 1 - sum / m - sumcnt << '\n';
    }
    return 0;
}

Measured memory_bytes: 384
def call(n):
    for i in range(1, n + 1):
        x = i
        if x % 3 == 0:
            print(" %d" % (i), end="")
            continue
        while x:
            if x % 10 == 3:
                print(" %d" % (i), end="")
                break
            x //= 10
    print()


n = int(input())
call(n)



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

using namespace std;

int N, K;
int X[10000], Y[10000];

void beet() {
  cin >> K;
  vector< int > vs;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    vs.push_back(Y[i]);
  }
  double sq3 = sqrt(3);
  vector< int > latte(N), malta(N);
  iota(begin(latte), end(latte), 0);
  iota(begin(malta), end(malta), 0);
  sort(begin(latte), end(latte), [&](int a, int b) {
    return X[a] - Y[a] / sq3 < X[b] - Y[b] / sq3;
  });
  sort(begin(malta), end(malta), [&](int a, int b) {
    return X[a] + Y[a] / sq3 < X[b] + Y[b] / sq3;
  });

  int need1 = N - K;
  sort(begin(vs), end(vs));
  vs.erase(unique(begin(vs), end(vs)), end(vs));
  double ret = 1e30;
  vector< int > st(N), inner(N);
  for(int y_0 : vs) {
    vector< pair< double, int > > hidari;
    vector< pair< double, int > > migi;
    for(auto &i : latte) {
      if(y_0 > Y[i]) {}
      else if(Y[i] == y_0) {
        hidari.emplace_back(X[i], i);
      } else {
        double dist = Y[i] - y_0;
        hidari.emplace_back(X[i] - dist / sq3, i);
      }
    }
    for(auto &i : malta) {
      if(y_0 > Y[i]) {}
      else if(Y[i] == y_0) {
        migi.emplace_back(X[i], i);
      } else {
        double dist = Y[i] - y_0;
        migi.emplace_back(X[i] + dist / sq3, i);
      }
    }

    int ptr = 0;
    double last = -1e9;
    int add = 0;
    for(int i = 0; i < hidari.size(); i++) {
      st[hidari[i].second] = true;
    }

    for(int i = 0; i < hidari.size(); i++) {

      while(ptr < migi.size() && add < need1) {
        if(st[migi[ptr].second]) {
          inner[migi[ptr].second] = true;
          last = migi[ptr].first;
          ++add;
        }
        ++ptr;
      }

      if(add >= need1) {
        ret = min(ret, last - hidari[i].first);
      }

      if(inner[hidari[i].second]) {
        inner[hidari[i].second] = false;
        --add;
      }
      st[hidari[i].second] = false;
    }
  }
  cout << fixed << setprecision(15) << ret * 3 << endl;
}

int main() {
  while(cin >> N, N) beet();
}


Measured memory_bytes: 3904
using System;
using System.Linq;

class Program
    {
        static void Main(string[] args)
        {
            // 入力
            var N = int.Parse(Console.ReadLine());
            var K = int.Parse(Console.ReadLine());
            var nums = Console.ReadLine().Split(' ').Select(s => int.Parse(s));

            // ロボットの動く距離
            var count = 0;

            // 計算
            foreach (var x in nums)
            {
                if (2 * x < K)
                    count += 2 * x;
                else
                    count += 2 * (K - x);
            }

            // 出力
            Console.WriteLine(count.ToString());

            Console.ReadLine();
        }
    }

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
  cin >> n;

  int mi = 2*100000;
  int count = 0;
  for(int i=0 ; i<n ; i++){
    int p;  cin >> p;
    if(mi >= p){
      mi = p;
      count++;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lsk 998244353
bitset<4005> c,d,GCD;
int C[4005];
int n;
int F(bitset<4005> A){
	for(int i=4000;i;--i)if(A[i])return i;return 0;
}
void gcd(){
	while(1){
		if(F(c)>F(GCD))swap(c,GCD);
		int cc=F(c),GG=F(GCD);
		for(int i=GG;i>=cc;--i){
			if(GCD[i])GCD^=(c<<(i-cc));
		}
		if(GCD.none()){swap(c,GCD);break;}
	}
}
int main(){
	C[0]=1;
	for(int i=1;i<=4000;++i)C[i]=(C[i-1]<<1)%lsk;
	scanf("%d",&n);
	cin>>d;cin>>GCD;
	for(int i=2;i<=n;++i)cin>>c,gcd();
	int res=0,G=F(GCD);
	c.reset();
	for(int i=4000;i>=G;--i){
		if(d[i])res=(res+C[i-G])%lsk;
		if(d[i]!=c[i])c^=GCD<<(i-G);
	}
	int F=0;
	for(int i=G;~i;--i)if(d[i]>c[i])break;else if(d[i]<c[i])F=1;
	if(!F)res++;
	cout<<res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod=1e9+7,N=2e5+5;
ll c[N],dp[N],sum[N];
int main(){
    cin.tie(NULL); cout.tie(NULL);
    ios_base:: sync_with_stdio(false);
    ll n;cin>>n;
    for(ll i=1;i<=n;i++)cin>>c[i];
    sum[c[1]]=dp[1]=1;
    for(ll i=2;i<=n;i++){
        if(c[i-1]!=c[i]){
            sum[c[i]]+=dp[i-1];
            sum[c[i]]%=mod;
        }
        dp[i]=sum[c[i]];
    }
    cout<<dp[n];
}




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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int X, K;
    cin >> K >> X;
    REP(i, (K - 1)*2 + 1) {
        cout << X - K + i + 1 << " ";
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
#include <string>
#include <stack>
#include <queue>

#define INT_MAX 2147483647
#define INT_MIN -2147483647

#define NUM 10000
#define INVALID_IDX -1
using namespace std;

struct BTree
{
private:
	struct BTreeNode{
		int p, l, r;
	};
	BTreeNode data[25];
	int len;
	int D[25], H[25];

	void getDepth(int idx, int depth)
	{
		D[idx] = depth;
		if (data[idx].l != INVALID_IDX) getDepth(data[idx].l, depth + 1);
		if (data[idx].r != INVALID_IDX) getDepth(data[idx].r, depth + 1);
	}

	int getHeight(int idx)
	{
		if (idx == INVALID_IDX) return -1;

		int hl = getHeight(data[idx].l);
		int hr = getHeight(data[idx].r);

		H[idx] = max(hl, hr) + 1;
		return H[idx];
	}

	int getSibling(int idx)
	{
		int pIdx = data[idx].p;

		if (pIdx == INVALID_IDX) return INVALID_IDX;
		if (idx == data[pIdx].l && data[pIdx].r != INVALID_IDX)
			return data[pIdx].r;
		if (idx == data[pIdx].r && data[pIdx].l != INVALID_IDX)
			return data[pIdx].l;
		return INVALID_IDX;
	}

	void markHead()
	{
		for (int i = 0; i < len; ++i)
		{
			if (data[i].p == INVALID_IDX)
			{
				rootIdx = i;
				break;
			}
		}
	}

	void printNode(int idx)
	{
		cout << "node " << idx << ": ";
		cout << "parent = " << data[idx].p << ", ";
		cout << "sibling = " << getSibling(idx) << ", ";
		
		int degree = 0;
		if (data[idx].l != INVALID_IDX) degree++;
		if (data[idx].r != INVALID_IDX) degree++;
		cout << "degree = " << degree << ", ";

		cout << "depth = " << D[idx] << ", ";
		cout << "height = " << H[idx] << ", ";

		string type = "";
		if (data[idx].p == INVALID_IDX) type = "root";
		else if (data[idx].l != INVALID_IDX || data[idx].r != INVALID_IDX) type = "internal node";
		else type = "leaf";
		cout << type << endl;
	}

public:
	int rootIdx;

	BTree()
	{
		for (int i = 0; i < 25; ++i)
		{
			data[i].l = data[i].r = data[i].p = INVALID_IDX;
		}
	}

	void FiTraverse(int idx)
	{
		if (idx == INVALID_IDX) return;

		cout << " " << idx;
		FiTraverse(data[idx].l);
		FiTraverse(data[idx].r);
	}

	void InTraverse(int idx)
	{
		if (idx == INVALID_IDX) return;

		InTraverse(data[idx].l);
		cout << " " << idx;
		InTraverse(data[idx].r);
	}

	void PoTraverse(int idx)
	{
		if (idx == INVALID_IDX) return;

		PoTraverse(data[idx].l);
		PoTraverse(data[idx].r);
		cout << " " << idx;
	}

	void construct()
	{
		int idx, lc, rc;
		cin >> len;
		for (int i = 0; i < len; ++i)
		{
			cin >> idx >> lc >> rc;
			data[idx].l = lc;
			data[idx].r = rc;

			data[lc].p = idx;
			data[rc].p = idx;
		}
		markHead();
		getDepth(rootIdx, 0);
		getHeight(rootIdx);
	}

	void print()
	{
		for (int i = 0; i < len; ++i)
			printNode(i);
	}
};


int main()
{
	BTree t;
	t.construct();
	//t.print();
	cout << "Preorder" << endl;
	t.FiTraverse(t.rootIdx);
	cout << endl;

	cout << "Inorder" << endl;
	t.InTraverse(t.rootIdx);
	cout << endl;

	cout << "Postorder" << endl;
	t.PoTraverse(t.rootIdx);
	cout << endl;

}

Measured memory_bytes: 3092
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main() {
	string a;
	int n;
	while (cin >> n &&n!=0) {
		cin >> a;
		int b[100][2];
		for (int i = 0; i < n; i++) {
			cin >> b[i][0] >> b[i][1];
			b[i][0]--;
			b[i][1]--;
		}
		for (int i = n - 1; i >= 0; i--) {
			int c = b[i][1] - b[i][0];
			int d = (int)a[b[i][0]] + c;
			char e, f;
			while (d > 'z') {
				d -= 26;
			}
			e = (char)d;
			d = (int)a[b[i][1]] + c;
			while (d > 'z') {
				d -= 26;
			}
			f = (char)d;
			a[b[i][1]] = e;
			a[b[i][0]] = f;
		}
		cout << a << endl;
	}
}

Measured memory_bytes: 3120
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T t){t=new T(n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(ElementType!T);r.popFront;}}
void readM(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=readln.splitter;foreach(ref v;t){v[i]=r.front.to!(ElementType!(typeof(v)));r.popFront;}}}
void readS(T)(size_t n,ref T t){t=new T(n);foreach(ref v;t){auto r=readln.splitter;foreach(ref j;v.tupleof){j=r.front.to!(typeof(j));r.popFront;}}}

void main()
{
  int m; readV(m);
  writeln(24-m+24);
}


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

int frogBU(int h[],int n, int k,int dp[]){
    dp[0] = 0;
    dp[1] = abs(h[1]-h[0]);

    for(int i=2;i<n;i++){
        int ans = INT_MAX;
        for(int j=1;j<=k && i-j>=0;j++){
            dp[i] = min(ans,dp[i-j]+abs(h[i]-h[i-j]));
            ans = dp[i];
        }
    }
    return dp[n-1];
}

int main() {
  int n,k;
  cin >> n >> k;
  
  int *dp = new int[n+1]{0};
  int *arr = new int[n];
  for(int i=0;i<n;i++){
  	cin >> arr[i];
  }
  
  cout <<frogBU(arr, n,k, dp) << endl;
}


Measured memory_bytes: 1024
// Test
#include<iostream>
#include<cstdio>
using namespace std;

int n,k,ans=0;
int tot=0,h[100005],a[100005];
struct Edge{
    int x,next;
}e[200005];

inline void add_edge(int x,int y){
    e[++tot].x=y;
    e[tot].next=h[x],h[x]=tot;
}

int dfs(int x,int deep){
    int ret=deep;
    for(int i=h[x];i;i=e[i].next)
        ret=max(ret,dfs(e[i].x,deep+1));
    if(a[x]!=1&&ret-deep==k-1)return ans++,0;
    else return ret;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    if(a[1]!=1)ans=a[1]=1;
    for(int i=2;i<=n;i++)add_edge(a[i],i);
    dfs(1,0),printf("%d",ans);
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,cnt,ch[1000010][26],id[1000010],sz[1000010],g[1000010],f[1000010][26];
ll ans;
void ins(char s[]){
	int i,op,now=0;
	//puts("!");
	for(i=0;s[i];i++){
		//printf("%c",s[i]);
		op=s[i]-'a';
		if(!ch[now][op]){
			ch[now][op]=++cnt;id[ch[now][op]]=op;
		}
		now=ch[now][op];
	}
	sz[now]++;g[now]++;
	//puts("");
}
void dfs(int x){
	int i,j;
	for(i=0;i<26;i++)if(ch[x][i]){
		//printf("%d %d %d\n",x,i,ch[x][i]);
		dfs(ch[x][i]);sz[x]+=sz[ch[x][i]];
		for(j=0;j<26;j++)f[x][j]+=f[ch[x][i]][j];
	}
	//f[x][id[x]]=sz[id[x]];
	for(i=0;i<26;i++)if(ch[x][i]){
		//printf("%lld %lld %lld %lld %lld\n",x,id[x],i,g[ch[x][i]],f[x][i]);
		ans+=1ll*g[ch[x][i]]*f[x][i];
		ans-=g[ch[x][i]];
	}
	f[x][id[x]]=sz[x];
}
char s[1000010];
int main(){
	int i,len,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%s",s+1);
		len=strlen(s+1);
		for(j=1;j<=len/2;j++)swap(s[j],s[len-j+1]);
		//for(j=1;j<=len;j++)printf("%c",s[j]);puts("");
		ins(s+1);
	}
	dfs(0);
	printf("%lld",ans);
}

Measured memory_bytes: 288868
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll memo[3001][3001];

ll sol(int n,ll *arr,int i,int j)
{
   if(j<i)
   	return 0;
//   if(i==j)
//   	return memo[i][j]=arr[i];
   if(memo[i][j]!=-1)
   	return memo[i][j];

   ll op1=arr[i]-sol(n,arr,i+1,j);
   ll op2=arr[j]-sol(n,arr,i,j-1);

   return memo[i][j]=max(op1,op2);
}

int main()
{
	int n;
	cin>>n;
	ll arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];
    // ll dp[n+1][n+1];
    

    // for(int i=n-2;i>=0;i--)
    // {
    // 	for(int j=i;j<n;j++)
    // 	{
    // 		if(i==j)
    // 			dp[i][j]=arr[i];
    // 		else
    // 		dp[i][j]=max(arr[i]-dp[i+1][j],arr[j]-dp[i][j-1]);
    // 	}
    // }
    // cout<<dp[0][n-1];
    memset(memo,-1,sizeof memo);
    cout<<sol(n,arr,0,n-1);
}

Measured memory_bytes: 70912
import java.util.Scanner


object Main {
  def read() = {
    val sc = new Scanner(System.in)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    (a,b,c)
  }


  def main(args: Array[String]): Unit = {
    val (a,b,c) = read()
    println(Math.min(b/a, c))
  }
}

Measured memory_bytes: 25416
#include<stdio.h>
  int main(void){
    int a,b,sum,sub,pro;
    scanf("%d",&a);
    scanf("%d",&b);
 
    sum = a+b;
    sub = a-b;
    pro = a*b;
 
    if(sum > sub){
      if(sum > pro){
        printf("%d",sum);
      }
      else{
        printf("%d",pro);
      }
    }else{
      if(sub>pro){
        printf("%d",sub);
      }else{
        printf("%d",pro);
      }
    }
 
    return 0;
  }

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

using namespace std;

#define INF 0x3f3f3f3f

int N,M;

int cost[1001]; //custo de cada chave
int key_treasure[1001]; // baus que cada chave abre
int memo[1001][9000];
int total; // bits de baus

int dp(int key, int treasures){

    if (key == M){
        if(treasures == total) return 0;
        else return INF;
    }
    
    if(memo[key][treasures] != -1) return memo[key][treasures];

    int a = dp(key+1, treasures | key_treasure[key]) + cost[key];
    
    int b = dp(key+1, treasures);
    
    int ans = min(a,b);
    memo[key][treasures] = ans;
    
    return ans;
}


int main(){

    cin >> N >> M;
    memset(memo, -1, sizeof(memo));
    
    for(int i=0; i<N; i++){
        total |= 1 << i;
    }
    
    for(int i=0; i< M; i++){
        int custo, qtd;
        
        cin >> custo >> qtd;
        cost[i] = custo;

        int bau;
        for(int x=0; x<qtd; x++){
            cin >> bau;
            key_treasure[i] |= 1 << (bau - 1);
        }
    
    }

    int res = dp(0,0);
    if(res == INF) cout << -1 << endl;
    else cout << res << endl;

}

Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second
#define mod 1e9+7
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rof(i,a,b) for(ll i=a;i>b;i--)

ll lcm(ll a, ll b){
    return a / __gcd(a, b) * b;
}
//memset can initialize to 0 or -1 ONLY
// memset(a,0,sizeof(a[0][0])*n*n); //2D array
//memset(a, 0, sizeof(a));  //1D array
//memset(str, 't', sizeof(str)); // string
void solve()
{
    int n;cin>>n;
    double i=n/3.0;
    //cout<<i<<" ";
    i=i*i*i;
    
    cout<<fixed<<setprecision(12)<<i<<endl;
    
}


int main()
{

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

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

}

Measured memory_bytes: 384
package main

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

const pi = math.Pi

var mod int = pow(10, 9) + 7
var Umod uint64 = 1000000007
var ans, cnt int

func main() {
	reader.Split(bufio.ScanWords)
	N, _ := strconv.Atoi(read())
	K, _ := strconv.Atoi(read())
	for i := 1; i <= K; i++ {
		fmt.Println(combination(N-K+1, i) * combination(K-1, i-1) % mod)
	}
}

/*  ----------------------------------------  */

var reader = bufio.NewScanner(os.Stdin)

func read() string {
	reader.Scan()
	return reader.Text()
}

func lcm(x, y int) int {
	return (x / gcd(x, y)) * y
}

func gcd(x, y int) int {
	if x%y == 0 {
		return y
	} else {
		r := x % y
		return gcd(y, r)
	}
}

var fac [1000000]int
var finv [1000000]int
var inv [1000000]int

func combination_init() {
	fac[0], fac[1] = 1, 1
	finv[0], finv[1] = 1, 1
	inv[1] = 1

	// invは a^(-1) mod p
	// pをaで割ることを考える

	// p/a*(a) + p%a = p
	// p/a*(a) + p%a = 0          (mod p)
	// -p%a = p/a*(a)             (mod p)
	// -p%a *a^(-1)= p/a          (mod p)
	// a^(-1)= p/a * (-p%a)^(-1)  (mod p)
	// a^(-1) =

	for i := 2; i < 1000000; 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
	}
}

func combination(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[y] * finv[x-y] % mod) % mod
	//return fac[x] / (fac[y] * fac[x-y])
}

func permutation(x, y int) int {
	if x < y {
		return 0
	}
	if fac[0] != 1 {
		combination_init()
	}
	return fac[x] * (finv[x-y] % mod) % mod
	//return fac[x] / fac[x-y]
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }
func ceil(x int) int   { return int(math.Ceil(float64(x))) }

type SortBy [][]int

func (a SortBy) Len() int      { return len(a) }
func (a SortBy) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool {
	return a[i][1] < a[j][1]
}

type PriorityQueue []int

func (h PriorityQueue) Len() int            { return len(h) }
func (h PriorityQueue) Less(i, j int) bool  { return h[i] < h[j] }
func (h PriorityQueue) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *PriorityQueue) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *PriorityQueue) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


Measured memory_bytes: 24064
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define mod 1000000007
int main() 
{
    ll n;
    cin>>n;
    long double ans = 2*((double)3.141592653589793238)*n;
    cout<<setprecision(9)<<ans;
}


Measured memory_bytes: 3800
//2つの整数x, yを小さい順に表示する

#include<stdio.h>

int main(void){

    int i = 0;          //for文用      
    int x = 0, y = 0;   

    for(i = 1; ; i++){
        scanf("%d %d", &x, &y);

        if(x <= 0 && x > 10000 && y <= 0 && y > 10000){ 
            //エラーメッセージを表示して終了する
            printf("Invalid Input\n");
            return 0;

        }

        if (x != 0 || y != 0){
            if(x < y)       //x < yに並べ替えて出力
                printf("%d %d\n", x, y);
            else
                printf("%d %d\n", y, x);
        }else
            break;
    }

    return 0;
}


Measured memory_bytes: 2060