akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)

ll solve(vector<ll> a, int b) {
  ll s = 0;
  ll ans = 0;
  rep(i, 0, a.size()) {
    s += a[i];
    if (i % 2 == b) {
      if (s >= 0) {
        ans += s + 1;
        s = -1;
      }
    } else {
      if (s <= 0) {
        ans += abs(s) + 1;
        s = 1;
      }
    }
  }
  return ans;
}

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, 0, n) cin >> a[i];
  cout << min(solve(a, 0), solve(a, 1)) << endl;
  return 0;
}

Measured memory_bytes: 5520
#include"bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int gcd(int a, int b) {
	if (a > b) {
		return gcd(b, a);
	}
	else if (a == 0) {
		return b;
	}
	else {
		return gcd(b % a, a);
	}
}

int main() {
	int A, B;
	cin >> A >> B;
	cout << (int64_t)A / gcd(A, B) * B << endl;
	return 0;
}


Measured memory_bytes: 256
def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    f = [0] * (n + 1)
    b = [0] * (n + 1)
    for i in range(n):
        f[i+1] = fractions.gcd(f[i], a[i])
        b[-i-2] = fractions.gcd(b[-i-1], a[-i-1])
    m_gcd = 0
    for i in range(n):
        m_gcd = max(m_gcd, fractions.gcd(f[i], b[i+1]))
    print(m_gcd)


if __name__ == '__main__':
    slove()


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

static int S[100000], T;
int binarySearch(int ok, int ng, bool f(int n)) {
	while (abs(ng - ok) > 1) { // 差が1以下になるまで繰り返す
		int mid = ok + ng >> 1; // midが調べる値⌊(ok+ng)/2⌋
		if(f(mid)) ok = mid;
		else ng = mid;
	}
	return ok; // okは条件を満たし、境界に接する値
}


bool f(int N) {
	return S[N] <= T;
}
 
int main() {
	int n, q, ans = 0;
    cin >> n;
    for (int i = 0;i < n;++ i) cin >> S[i];
    cin >> q;
    for (int i = 0;i < q;++ i) {
        cin >> T;
        if (S[binarySearch(0, n, f)] == T) ++ ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3468
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class B {
    static StreamWriter Out = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static void Main(string[] args) {
        int N, M;
        Input(out N, out M);
        int[] A;
        Inputs(out A);
        double sum = 0;
        for(int i = 0; i < N; i++) {
            sum += A[i];
        }
        int count = 0;
        for(int i = 0; i < N; i++) {
            if(A[i] >= sum / (4 * M)) {
                count++;
            }
        }
        if(count >= M) {
            Print("Yes");
        } else {
            Print("No");
        }
        Out.Flush();
    }
    static T ChangeT<T>(string s) => (T)Convert.ChangeType(s, typeof(T));
    static void Input<A>(out A a) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
    }
    static void Input<A, B>(out A a, out B b) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
    }
    static void Input<A, B, C>(out A a, out B b, out C c) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
    }
    static void Input<A, B, C, D>(out A a, out B b, out C c, out D d) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
    }
    static void Input<A, B, C, D, E>(out A a, out B b, out C c, out D d, out E e) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
    }
    static void Input<A, B, C, D, E, F>(out A a, out B b, out C c, out D d, out E e, out F f) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
        f = ChangeT<F>(words[5]);
    }
    static void Inputs<T>(out T[] array) {
        array = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries).Select(s => ChangeT<T>(s)).ToArray();
    }
    static void Print<T>(T s) => Out.WriteLine(s);
    static void Print<T>(params T[] s) => Out.WriteLine(string.Join(" ", s));
    static void Print<T>(IEnumerable<T> e) => Out.WriteLine(string.Join(" ", e));
}

Measured memory_bytes: 13268
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)
 
int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
 
typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
 
const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
 
// --------------------------------------
int n;
 
void bfs(int p, vector<vector<P>> g, int ma) {
  vector<int> v(n);
 
  queue<tuple<int, int, int>> que;
 
  que.push(make_tuple(p, -1, 1));
  while(!que.empty()) {
    tuple<int, int, int> tp = que.front(); que.pop();
    int& now = get<0>(tp);
    int& from = get<1>(tp);
    int& count = get<2>(tp);
    REP(i, g[now].size()) {
      if(g[now][i].first != from) {
        v[g[now][i].second] = count++;
        if(count > ma) count = 1;
        que.push(make_tuple(g[now][i].first, now, count));
      }
    }
  }
 
  cout << ma << endl;
  FOR(i, 1, n) {
    cout << v[i] << endl;
  }
}
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  cin >> n;
  vector<vector<P>> g(n + 1);
  vector<int> count(n + 1, 0);
 
  REP(i, n - 1) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(make_pair(b, i + 1));
    g[b].push_back(make_pair(a, i + 1));
 
    count[a]++;
    count[b]++;
  }
 
  int ma = 0, po;
  FOR(i, 1, n + 1) {
    if(ma < count[i]) {
      ma = count[i];
      po = i;
    }
  }
 
  bfs(po, g, ma);
}

Measured memory_bytes: 13312
import java.util.*;
class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int ar[]=new int[n];
    for(int x=0;x<n-1;x++)
    {
      int a=sc.nextInt();
      ar[a-1]++;
    }
    for(int x=0;x<n;x++)
    {
      System.out.println(ar[x]);
    }
  }
}

Measured memory_bytes: 61596
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	int N, a[110];
	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	sort(a, a + N);
	cout << a[N - 1] - a[0] << endl;
}


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

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

#define T 1
#define S 2
#define E 3
#define W 4
#define N 5
#define B 6

int sai[10] ={0,T,S,E,W,N,B};

void turn(string s)
{
	int t=0;
	if(s=="North")
	{
		t = sai[N];
		sai[N] = sai[T];
		sai[T] = sai[S];
		sai[S] = sai[B];
		sai[B] = t;
	}
	if(s=="South")
	{
		t = sai[S];
		sai[S] = sai[T];
		sai[T] = sai[N];
		sai[N] = sai[B];
		sai[B] = t;
	}
	if(s=="West")
	{
		t = sai[W];
		sai[W] = sai[T];
		sai[T] = sai[E];
		sai[E] = sai[B];
		sai[B] = t;
	}
	if(s=="East")
	{
		t = sai[E];
		sai[E] = sai[T];
		sai[T] = sai[W];
		sai[W] = sai[B];
		sai[B] = t;
	}
	if(s=="Right")
	{
		t = sai[E];
		sai[E] = sai[N];
		sai[N] = sai[W];
		sai[W] = sai[S];
		sai[S] = t;
	}
	if(s=="Left")
	{
		t = sai[W];
		sai[W] = sai[N];
		sai[N] = sai[E];
		sai[E] = sai[S];
		sai[S] = t;
	}
	//debug
	//cout << "T,N,E:" << sai[T] <<"," << sai[N] <<"<" << sai[E]  << endl;

}


int main()
{
	int n;
	while(cin >> n && n)
	{
		REP(8) sai[i] = i;
		string ss;
		int ans = 1;
		REP(n)
		{
			cin >> ss;
			turn(ss);
			ans += sai[T];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define ALL(v) v.begin(),v.end()
#define mp make_pair
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}}
template <class X> void prrr(X test){int f=0;for(auto it:test){cout<<(f++!=0?" ":"")<<it;}cout<<endl;}
template<typename X>
istream&operator>>(istream&i,vector<X>&v){for(X&x:v)i>>x;return i;}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(l, r); // 0 <= l, r <= n-1
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

// return sorted 約数list 1 <= x <= n
vector<ll> divv(ll n) {
  vector<ll> v;
  for(ll i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.push_back(i);
      if(i*i != n) v.push_back(n/i);
    }
  }
  sort(ALL(v));
  return v;
}

int main() {
    ll n, ans = 0;

    cin>>n;
    pr(n*n*n);
    
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;


public class Main {
    char s;
    private void solve() {
        s = next().charAt(0);

        if (s == 'A' || s == 'T') {
            out.println(s == 'A' ? 'T' : 'A');
        } else {
            out.println(s == 'G' ? 'C' : 'G');
        }
    }

    public static void main(String[] args) {
        out.flush();
        new Main().solve();
        out.close();
    }

    /* Input */
    private static final InputStream in = System.in;
    private static final PrintWriter out = new PrintWriter(System.out);
    private final byte[] buffer = new byte[4096];
    private int p = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (p < buflen)
            return true;
        p = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buflen <= 0)
            return false;
        return true;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrint(buffer[p])) {
            p++;
        }
        return hasNextByte();
    }

    private boolean isPrint(int ch) {
        if (ch >= '!' && ch <= '~')
            return true;
        return false;
    }

    private int nextByte() {
        if (!hasNextByte())
            return -1;
        return buffer[p++];
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = -1;
        while (isPrint((b = nextByte()))) {
            sb.appendCodePoint(b);
        }
        return sb.toString();
    }

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

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 20692
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200+10,M=10000000+10;

int p[M],v[M],cnt=0;
void sieve(int n) {
	v[1]=1;
	for (int i=2;i<=n;++i) {
		if (!v[i]) p[++cnt]=i;
		for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
			v[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}

int n,a[M];
vector<int> L,R,E[N];

int vis[N],lnk[N];
bool dfs(int u) {
	for (int v:E[u]) {
		if (vis[v]) continue;
		vis[v]=1;
		if (!lnk[v]||dfs(lnk[v])) { lnk[v]=u; return 1; }
	}
	return 0;
}
int Hungary() {
	int res=0;
	for (int i=1;i<=L.size();++i) {
		memset(vis,0,sizeof(vis));
		if (dfs(i)) ++res;
	}
	return res;
}

int main() {
	sieve(10000000);
	n=read();
	for (int i=1;i<=n;++i) a[read()]=1;
	for (int i=1;i<M;++i) {
		if (a[i]==a[i-1]) continue;
		if (i&1) L.emplace_back(i);
		else R.emplace_back(i);
	}
	for (int i=0;i<L.size();++i)
		for (int j=0;j<R.size();++j) {
			if (v[abs(L[i]-R[j])]) continue;
			E[i+1].emplace_back(j+1);
		}
	int f=Hungary();
	printf("%d\n",f+(L.size()-f)/2*2+(R.size()-f)/2*2+((L.size()-f)&1)*3);
	return 0;
} 

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

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 1e5 + 5, LN = 17, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

string s;
ll ret;

void solve(int i, ll sum) {
    if (i == s.length()) {
        ret += sum;
    }
    for (int j = i; j < s.length(); j++) {
        solve(j + 1, sum + stoll(s.substr(i, j - i + 1)));
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    cin >> s;
    solve(0, 0);
    cout << ret << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
int nums[100111];

int main()
{
    int i;
    int ans=0;

    scanf("%d",&n);

    n*=2;

    for (i=1;i<=n;i++)
    {
        scanf("%d",&nums[i]);
    }

    sort(nums+1,nums+1+n);

    for (i=1;i<=n;i+=2)
    {
        ans+=nums[i];
    }

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

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
    string s,ans;
    cin >> s;
    
    for(int i=0;i<s.size();i++){

        if(s[i]=='0' || s[i]=='1'){
            ans.push_back(s[i]);
        }else{
            if(ans.size()>0){
                ans.pop_back();
            }
            
        }
    }
    cout << ans << endl;
    return 0;
} 

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

int main(){
    int n;
    cin >> n;
    map<char, int> mp;
    for(int i=0;i<n;++i){
        char c;
        cin >> c;
        mp[c]++;
    }
    int cnt = 0;
    for(auto e : mp){
        if(e.second > 0)cnt++;
    }

    if(cnt == 3)cout << "Three" << endl;
    else cout << "Four" << endl;

    return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

class Process{
	private:
		string _name;
		int _time;
	public:
		@property{
			string name() const { return _name; }
			int time() const { return _time; }
		}

		this(string n, int t){
			_name = n;
			_time = t;
		}
		void print(int t) {
			writeln(name, " ", t);
		}
		void sub(int a){
			_time -= a;
		}
}

int main(char[][]argv)
{
	string[] str = readln.split();
	int n = str[0].to!int(), q = str[1].to!int(), t = 0;

	Process[] p;
	for(int i = 0; i < n; ++i){
		str = readln.split();
		p ~= new Process(str[0], str[1].to!int());
	}

	while(p.length != 0){
		//writeln("t : ", t);
		//foreach(e; p){
		//    writeln("p.name : ", e.name, " p.time : ", e.time);
		//}
		//writeln();
		p[0].sub(q);
		if(p[0].time <= 0){
			p[0].print(p[0].time + t + q);
			t += p[0].time + q;
			p = p[1..$];
		}
		else{
			t += q;
			auto tmp = p[0];
			p = p[1..$];
			p ~= tmp;
		}
	}

    return 0;
}

Measured memory_bytes: 11988
#include <stdio.h>
    
#define PutChar(c) ; *p = (char)(c); ++p;
    
#define MAX_N (2000001)
#define MAX_Ai (10001)
#define STR_SIZE (10000010)
    
int getNum(void);
void putNum(int n);
void CountingSort(int A[], int B[], int k, int len);
    
int A[MAX_N];
int B[MAX_N];
char str[STR_SIZE];
char *p = str;
    
int main(void) {
    register int i;
    int n;
    
    fread(str, 1, STR_SIZE, stdin);
        
    n = getNum();
    for (i = 1; i <= n; ++i) {
        A[i] = getNum();
    }
        
    CountingSort(A, B, MAX_Ai, n);
        
    p = str;
    --n;
    for (i = 1; i <= n; ++i) {
        putNum(B[i]);
        PutChar(' ');
    }
    putNum(B[i]);
    PutChar('\0');
        
    puts(str);
        
    return 0;
}
    
int getNum(void) {
    int n = 0;
    while ((*p >= '0') && (*p <= '9')) {
        n = n * 10 + (int)(*p - '0');
        ++p;
    }
    ++p;
    return n;
}
    
void putNum(int n) {
    int d;
    if (n < 10) {
        PutChar('0' + n);
        return;
    }
    d = n / 10;
    if (d) putNum(d);
    PutChar('0' + (n - (d * 10)));
}
    
void CountingSort(int A[], int B[], int k, int len) {
    int C[MAX_Ai] = { 0 };
    int i, j;
    for (j = 1; j <= len; ++j) {
        ++C[A[j]];
    }
    for (i = 1; i <= k; ++i) {
        C[i] += C[i - 1];
    }
    for (j = len; j > 0; --j) {
        B[C[A[j]]] = A[j];
        --C[A[j]];
    }
}

Measured memory_bytes: 26648
n, ww = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (100100) for i in range(110)]

for i in range(n):
    for j in range(ww + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[n][ww])

Measured memory_bytes: 120984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int main(){
  int n;
  cin>>n;
  double x[n];
  string s[n];
  rep(i,n)cin>>x[i]>>s[i];
  rep(i,n)if(s[i]=="BTC") x[i]=x[i]*380000.0;
  double sum=0.0;
  rep(i,n)sum+=x[i];
  cout << sum <<endl;
}

Measured memory_bytes: 256
package main

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

const Mod = 1000000007

func main() {
	io, flush := NewIO()
	defer flush()

	n := io.ScanInt()
	a := io.ScanInts(n)

	var curSum, sum int
	for i := 1; i < n; i++ {
		curSum += a[i-1] % Mod
		sum += ((curSum%Mod) * (a[i] % Mod)) % Mod
		sum %= Mod
	}
	fmt.Println(sum)
}

type IO struct {
	scanner *bufio.Scanner
	writer  *bufio.Writer
}

func NewIO() (*IO, func()) {
	io := &IO{
		scanner: newScanner(),
		writer:  newWriter(),
	}
	return io, func() { io.writer.Flush() }
}

func newScanner() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Buffer(make([]byte, 10000000), 10000000)
	s.Split(bufio.ScanWords)
	return s
}

func newWriter() *bufio.Writer {
	return bufio.NewWriter(os.Stdout)
}

func (io *IO) ScanBytes() []byte {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Bytes()
}

func (io *IO) ScanString() string {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Text()
}

func (io *IO) ScanStrings(n int) []string {
	strs := make([]string, n)
	for i := 0; i < n; i++ {
		strs[i] = io.ScanString()
	}
	return strs
}

func (io *IO) Scan2DStrings(y, x int) [][]string {
	strings := make([][]string, y)
	for i := 0; i < y; i++ {
		strings[i] = io.ScanStrings(x)
	}
	return strings
}

func (io *IO) Scan2DGraph(y int) [][]string {
	strs := make([][]string, y)
	for i := 0; i < y; i++ {
		strs[i] = strings.Split(io.ScanString(), "")
	}
	return strs
}

func (io *IO) ScanInt() int {
	return int(io.ScanInt64())
}

func (io *IO) ScanInt2() (int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt3() (int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt4() (int, int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = io.ScanInt()
	}
	return ints
}

func (io *IO) Scan2DInts(y, x int) [][]int {
	ints := make([][]int, y)
	for i := 0; i < y; i++ {
		ints[i] = io.ScanInts(x)
	}
	return ints
}

func (io *IO) ScanInt64() int64 {
	i, err := strconv.ParseInt(io.ScanString(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *IO) ScanFloat64() float64 {
	i, _ := strconv.ParseFloat(io.ScanString(), 64)
	return i
}

func (io *IO) ScanFloat64s(n int) []float64 {
	floats := make([]float64, n)
	for i := 0; i < n; i++ {
		floats[i] = io.ScanFloat64()
	}
	return floats
}

func (io *IO) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


Measured memory_bytes: 9160
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

def main():
    N = int(input())
    H = list(map(int, input().split()))

    n_max = 0
    count = 0
    for i in range(N-1):
        if H[i] >= H[i + 1]:
            count += 1
            if count > n_max:
                n_max = count
        else:
            count = 0
    print(n_max)


if __name__ == '__main__':
    main()

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

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

using namespace std;

pair<string, int> cipher(const string& s, int pos = 0);

pair<char, int> letter(const string& s, int pos) {
  if (s[pos] == '+') {
    char res;
    tie(res, pos) = letter(s, pos+1);
    if (res == '?') {
      return make_pair(res, pos);
    } else if (res == 'Z') {
      return make_pair('A', pos);
    } else {
      return make_pair(res+1, pos);
    }
  } else if (s[pos] == '-') {
    char res;
    tie(res, pos) = letter(s, pos+1);
    if (res == '?') {
      return make_pair(res, pos);
    } else if (res == 'A') {
      return make_pair('Z', pos);
    } else {
      return make_pair(res-1, pos);
    }
  } else {
    return make_pair(s[pos], pos+1);
  }
}

pair<string, int> string_p(const string& s, int pos) {
  if (s[pos] == '[') {
    string res;
    tie(res, pos) = cipher(s, pos+1);
    reverse(begin(res),end(res));
    return make_pair(res, pos+1);
  } else {
    auto res = letter(s, pos);
    return make_pair(string(1, res.first), res.second);
  }
}

pair<string, int> cipher(const string& s, int pos) {
  string res;
  string str;
  do {
    tie(str, pos) = string_p(s, pos);
    res += str;
  } while(pos < s.size() && s[pos] != ']');
  return make_pair(res, pos);
}

string convert(const string& s) {
  auto p = cipher(s).first;
  replace(begin(p),end(p),'?','A');
  return p;
}

int main() {
  while(1){
    string s;
    cin>>s;
    if (s == ".") break;
    cout << convert(s) << endl;
  }
  return 0;
}

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

	lst = {}

	for num in A:
		if num in lst:
			lst[num] += 1
		else:
			lst[num] = 1

	lst_sorted = sorted(lst.items(), key = lambda x: x[1])

	len_lst_sorted = len(lst_sorted)

	if len_lst_sorted <= K:
		print(0)
		return
	else:
		ans = 0
		for i in range(len_lst_sorted - K):
			ans += lst_sorted[i][1]
		print(ans)
		return

  
if __name__ == "__main__":
  	main()

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

using namespace std;

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

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


int main(){

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

    sort(all(a), greater<int>());

    ll ans = 0;
    for(int i = 1; i < n; ++i){
        ans += a[i / 2];
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 4020
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	if (C <= A + B) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
while true
	n = gets.to_i
	break if n == 0

	p, b = 0, "1" + gets.chomp
	sum = add = b.to_i(2)
	while true
		m = ((9007199254740992 - sum) / add.to_f).ceil
		sum += add * [m, n].min
		break if m > n
		sum /= 2
		add /= 2
		p += 1
		n -= m
		break if add == 0 || n == 0
	end
	puts sprintf("%012b", p) + sprintf("%b", sum)[1..-1]
end



Measured memory_bytes: 6940
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();
            
            int[] Z = new int[10];
            Z[A]++;
            Z[B]++;
            Z[C]++;
            
            for (int i=1;i<=9;i++) {
                if (Z[i]==2) {
                    System.out.println("Yes");
                    return;
                }
            }
            
            System.out.println("No");
        }
    }

}


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

int main() {
  using namespace std;
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int H, W;
  cin >> H >> W;
  int N;
  cin >> N;
  deque<int> A;
  copy_n(istream_iterator<int>(cin), N, back_inserter(A));
  vector<vector<int>> grid(H, vector<int>(W));
  for (int h = 0, color = 1; h < H; ++h)
    for (int w = 0; w < W; ++w) {
      grid[h][h % 2 ? W - 1 - w : w] = color;
      if (--A.front() == 0) A.pop_front(), ++color;
    }
  for (const auto& row : grid) {
  	for (const auto& e : row) cout << e << ' ';
  	cout << '\n';
  }
}


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

int main(){
	string card, s;
	int m, h, i;
	cin >> card;
	while(card != "-"){
		cin >> m;
		for(int i = 1; i <= m; i++){
			cin >> h;
			s.assign(card, 0, h);
			card.erase(0, h);
			card += s;
		}
		cout << card << endl;
		cin >> card;
	}

	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	string s, t;
	cin >> s >> t;
	t += s;
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
  struct node *left;
  struct node *right;
  struct node *parent;
  int key;
};
struct node *T;
void Insert(int);
void Inorder(struct node*);
void Preorder(struct node*);
int main(){
  int n, i, key;
  char func[6];
  T = (struct node *)malloc(sizeof(struct node) * 1);
  T->parent = T->left = T->right = NULL;
  T->key = -1;
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%s",&func);
    if(strcmp(func,"insert") == 0){
      scanf("%d",&key);
      Insert(key);
    }
    else if(strcmp(func,"print") == 0){
      Inorder(T);
      printf("\n");
      Preorder(T);
      printf("\n");
    }
  }
  return 0;
}

void Inorder(struct node* X){
  if(X != NULL){
    Inorder(X->left);
    printf(" %d",X->key);
    Inorder(X->right);
  }
}

void Preorder(struct node* X){
  if(X != NULL){
    printf(" %d",X->key);
    Preorder(X->left);
    Preorder(X->right);
  }
}

void Insert(int key){
  struct node *x, *y, *S;
  if(T->key == -1){
    T->key = key;
    return;
  }
  S = (struct node *)malloc(sizeof(struct node) * 1);
  S->key = key;
  S->parent = S->left = S->right = NULL;
  x = T;
  while(x != NULL){
    y = x;
    if(key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  S->parent = y;
  if(S->key < y->key)
    y->left = S;
  else
    y->right = S;
}

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

using namespace std;

#define mod 1000000007
#define ll long long

ll fact[200000 + 5];


long long power(long long a, long long b) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%mod;
        a = (a * a)%mod;
        b >>= 1;
    }
    return res;
}

ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2); 
} 
  

ll nCr(ll n, ll r){
	if(r == 0 || n - r == 0) return 1;
	ll ret = fact[n] * modInverse(fact[n - r], mod);
	ret %= mod;
	ret *= modInverse(fact[r], mod);
	ret %= mod;
	return ret;
}

int
main(void){
	int H, W, a, b;
	cin >> H >> W >> a >> b;
	
	fact[0] = 1;
	for(int i = 1; i <= 200000; i++) fact[i] = (fact[i - 1] * i)%mod;
	
	int h1 = H - a, w1 = b + 1;
	int h2 = H - h1 + 1, w2 = W - w1 + 1;
	ll ans = 0;
	//cout << nCr(6, 3) << ".\n"; 
	while(w1 <= W && h2 <= H){
		//cout << h1 << " " << w1 << " " << h2 << " " << w2 << " \n";
		ans += (nCr(h1 + w1 - 2, h1 - 1) * nCr(h2 + w2 - 2, h2 - 1))%mod;
		ans %= mod;
		w1++; w2--;
		h1--; h2++;
	}
	cout << ans;
}



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

int main(){
  ll n, q, i=0, s=0;
  cin >> n; 
  

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

  return 0;
}

Measured memory_bytes: 6428
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) throws Exception{
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x ;
		x = Integer.parseInt(br.readLine());
		
		System.out.println(x*x*x);
	}

}

Measured memory_bytes: 24200
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct State {
    int no_;
    int cost_;
    int ticket_;
    State(int no, int cost, int ticket) 
        : no_(no), cost_(cost), ticket_(ticket) {} 
    
};

struct Edge {
    int to_;
    int cost_;
    Edge(int to, int cost) 
        : to_(to), cost_(cost) {}
};

int c, n, m, s, d;

auto dijkstra(vector<vector<Edge>> &g, vector<vector<int>> &dm) -> int {
    auto comp = [](auto& lhs, auto& rhs){return lhs.cost_ > rhs.cost_;};
    priority_queue<State, vector<State>, decltype(comp)> que(comp);

    que.push(State(s, 0, c));
    for (auto &e : dm[s]) {
        e = 0;
    }
    while (!que.empty()) {
        State s = que.top();
        que.pop();
        int current_no = s.no_;
        int current_cost = s.cost_;
        int current_ticket = s.ticket_;
        for (auto &e : g[current_no]) {
            int to = e.to_;
            int cost = e.cost_;
            if (current_ticket > 0) {
                // not use ticket
                if (dm[to][current_ticket] > dm[current_no][current_ticket] + cost) {
                    que.push(State(to, dm[current_no][current_ticket] + cost, current_ticket));
                    dm[to][current_ticket] = dm[current_no][current_ticket] + cost;
                }
                // use ticket
                if (dm[to][current_ticket-1] > dm[current_no][current_ticket] + cost/2) {
                    que.push(State(to, dm[current_no][current_ticket] + cost/2, current_ticket-1));
                    dm[to][current_ticket-1] = dm[current_no][current_ticket] + cost/2;
                }
            }else {
                if (dm[to][current_ticket] > dm[current_no][current_ticket] + cost) {
                    que.push(State(to, dm[current_no][current_ticket] + cost, current_ticket));
                    dm[to][current_ticket] = dm[current_no][current_ticket] + cost;
                }
            }
        }
    }

    int ans = 1e8;
    for (auto &e : dm[d]) {
        ans = min(ans, e);
    }
    return ans;
}

auto main(int argc, char const *argv[]) -> int {
    constexpr int INF = 1e8;

    while(cin>>c>>n>>m>>s>>d, c||n||m||s||d) {
        vector<vector<Edge>> g(n+1);
        vector<vector<int>> dm(n+1);
        for (auto &e : dm) {
            for (int i = 0; i < c + 1; ++i) {
                e.push_back(INF);
            }
        }

        for (int i = 0; i < m; ++i) {
            int a, b, f;
            cin>>a>>b>>f;
            g[a].push_back(Edge(b, f));
            g[b].push_back(Edge(a, f));
        }
        cout<<dijkstra(g, dm)<<endl;
    }
    return 0;
}

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

dp = [ [0]*10 for _ in range(10) ]

all_count = 0
for first_num in range(10):
    for second_num in range(10):
        cache = []
        is_first = False
        is_second = False
        for i in range(N):
            target = int(S[i])
            if target == first_num and not is_first:
                is_first = True
                continue
            if is_first and target == second_num and not is_second:
                is_second = True
                continue
            if is_first and is_second:
                #print(first_num,second_num,target)
                if not target in cache:
                    all_count +=1
                    cache.append(target)
print(all_count)



Measured memory_bytes: 45404
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
//---------------------------------------------------------------------------------------------------
typedef pair<int,int> P;

int main(void){
    // Your code here!
    int k; cin >> k;
    int odd = (k+1)/2;
    int even = (k)/2;
    cout << odd*even << endl;
}


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


int POW[13];
int table[12],answer[12],W;

char func(int x){
	if(x == 1)return '+';
	else if(x == -1)return '-';
	else return '0';
}

void calc(int index){

	if(index == 12){
		int sum = 0;
		for(int i=0; i < 12; i++){
			if(table[i] == 1)sum += POW[i];
			else if(table[i] == -1){
				sum -= POW[i];
			}
		}
		if(sum == W){
			for(int i=0; i < 12; i++)answer[i] = table[i];
		}
		return;
	}

	table[index] = 0;
	calc(index+1);
	table[index] = 1;
	calc(index+1);
	table[index] = -1;
	calc(index+1);
}

int main(){

	for(int i = 0; i < 13; i++){
		POW[i] = pow(3,i);
	}

	for(int i = 0; i < 12; i++){
		table[i] = 0;
	}

	scanf("%d",&W);

	calc(0);

	for(int i = 11; i >= 0; i--){
		if(answer[i] != 0){
			for(int k=i; k >= 0; k--){
				printf("%c",func(answer[k]));
			}
			printf("\n");
			break;
		}
	}

    return 0;
}



Measured memory_bytes: 3248
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;

void solve() {
  int a, b, c;
  scanf("%lld %lld.%lld", &a, &b, &c);

  int ans = a * b + a*c/100;
  cout << ans << endl;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 3180
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define input freopen("/Users/peteryuanpan/data.txt","r",stdin)

const double eps = 1e-9, pi = acos(-1.0);
int sgn(double x){
    if(abs(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}

#define N 10010
int n;
struct Maze{
    int x1, y1;
    int x2, y2;
}ma[N];

struct Seg{
    double l, r;
}seg[N << 1], seg1[N << 1];
bool cmp1(const Seg a, const Seg b){
    if(sgn(a.r - b.r) != 0) return sgn(a.r - b.r) < 0;
    else return sgn(a.l - b.l) < 0;
}

double getangle(int x1, int y1){
    double a = atan2(y1, x1);
    if(sgn(a) < 0) a += 2 * pi;
    return a;
}

int solve(Seg *seg, int fr, int to){
    int ans = 0;
    for(int i = fr, j = fr; i <= to;){
        for(; j <= to && sgn(seg[j].l - seg[i].r) <= 0; j++);
        ans++;
        i = j;
    }
    return ans;
}

int main(){
    //input;
    while(scanf("%d",&n) == 1){
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d%d",&ma[i].x1, &ma[i].y1, &ma[i].x2, &ma[i].y2);
        }
        for(int i = 1; i <= n; i++){
            double rad[10];
            rad[1] = getangle(ma[i].x1, ma[i].y1);
            rad[2] = getangle(ma[i].x1, ma[i].y2);
            rad[3] = getangle(ma[i].x2, ma[i].y1);
            rad[4] = getangle(ma[i].x2, ma[i].y2);
            sort(rad + 1, rad + 1 + 4);
            double d = 0.0;
            int w1 = 1, w2 = 2;
            for(int i1 = 1; i1 <= 4; i1++){
                for(int i2 = i1 + 1; i2 <= 4; i2++){
                    double d1 = abs(rad[i1] - rad[i2]);
                    d1 = min(d1, 2 * pi - d1);
                    if(sgn(d1 - d) > 0){
                        d = d1;
                        w1 = i1, w2 = i2;
                    }
                }
            }
            double a1 = rad[w1], a2 = rad[w2];
            if(sgn(a1 - a2) > 0) swap(a1, a2);
            if(sgn((a2 - a1) - d) != 0) swap(a1, a2);
            if(sgn(a1 - a2) > 0) a2 += 2 * pi;
            seg[i].l = a1, seg[i].r = a2;
        }
        
        sort(seg + 1, seg + 1 + n, cmp1);
        for(int i = n + 1; i <= 2 * n; i++){
            if(sgn(seg[i - n].r - 2 * pi) < 0 && sgn(seg[i - n].l - 2 * pi) < 0){
                seg[i].l = seg[i - n].l + 2 * pi;
                seg[i].r = seg[i - n].r + 2 * pi;
            }
            else{
                seg[i].l = seg[i - n].l;
                seg[i].r = seg[i - n].r;
            }
            
            seg[i].l = seg[i - n].l + 2 * pi;
            seg[i].r = seg[i - n].r + 2 * pi;
        }
        int ans = n;
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= i + n - 1; j++) seg1[j] = seg[j];
            sort(seg1 + i, seg1 + i + n, cmp1);
            int ans1 = solve(seg1, i, i + n - 1);
            ans = min(ans, ans1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 1460
#include <stdio.h>

int main() {
	int a, b;
	char s[20];

	scanf("%d %d", &a, &b);
	scanf("%s", &s);

	bool ok = true;//合っていればtrue

	//数列の量の判定

	for (int i = 0; i < a; i++) {
		if (s[i] == '-') ok = false;
	}//最初の数字の部分

	if (s[a] != '-') ok = false;//ハイフンの部分

	for (int i = a + 1; i < b + a + 1; i++) {
		if (s[i] == '-') ok = false;
	}

	if (ok) printf("Yes\n");
	else printf("No\n");

}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
long long dp[3001][3001];
int a[3001],n;
long long fun(int s,int e,bool turn)
{
    if(s>e) return 0;
    long long &ret=dp[s][e];
    if(~ret)
        return ret;
    if(!turn)
    {
        return ret=max(a[s]+fun(s+1,e,!turn),a[e]+fun(s,e-1,!turn));
    }
    return ret=min(-a[s]+fun(s+1,e,!turn),-a[e]+fun(s,e-1,!turn));
}
int main()
{
    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
 cout<<fun(0,n-1,0)<<endl;
}


Measured memory_bytes: 74088
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

int a0, l;

int vec_int(vector<int> &y) {
    int now = 1;
    int res = 0;
    for(int i = 0; i < l; ++i) {
        res += y[i]*now;
        now *= 10;
    }
    return res;
}

int ai(int x) {
    vector<int> xvec(l, 0);
    int tenmax = pow(10, l);
    for(int i = 0; i < l; ++i) {
        int xch = x%tenmax;
        tenmax /= 10;
        int inx = xch/tenmax;
        xvec[i] = inx;
        x -= tenmax*inx;
    }
    sort(xvec.begin(), xvec.end());
    int xmax = vec_int(xvec);
    sort(xvec.begin(), xvec.end(), greater<int>());
    int xmin = vec_int(xvec);
    return xmax-xmin;
}

int main() {
    while(1) {
        cin >> a0 >> l;
        if(a0 == 0 && l == 0) break;
        map<int, int> mcnt;
        int ch = 1;
        mcnt[a0] = ch;
        int xans = 0, jans = 0, ijans = 0;
        while(1) {
            a0 = ai(a0);
            if(mcnt[a0] != 0) {
                xans = a0;
                jans = mcnt[a0]-1;
                ijans = ch+1-mcnt[a0];
                break;
            }else mcnt[a0] = ch+1;
            ch++;
        }
        cout << jans << " " << xans << " " << ijans << endl;
    }
}


Measured memory_bytes: 3200
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAX_N = 100010;
const int inf = 2147483647;
int dat[MAX_N * 4];
int n;

void init(int n_){
    n = 1;
    while(n < n_) n *= 2; // 2のn乗に切り上げる
    for(int i = 0; i < n*2; i++){
        dat[i] = inf;
    }
    // 配列 a の要素で初期化したいとき
    // for(int i = n; i < n+n; i++){
    //     dat[i] = a[i-n];
    // }
    // for(int i=n-1; i>=1; i--){
    //     dat[i] = min(dat[i*2], dat[i*2+1]);
    // }
}

void update(int i, int x){
    i += n;
    dat[i] = x;
    while(i > 1){
        dat[i/2] = min(dat[i], dat[i^1]);
        i /= 2;
    }
}

int query(int a, int b, int i, int l, int r){
    if(r <= a || b <= l) return inf;
    if(a <= l && r <= b) return dat[i];
    return min(query(a,b,i*2,l,(l+r)/2), query(a,b,i*2+1,(l+r)/2,r));
}

int query(int a, int b){
    return query(a,b,1,0,n);
}

int main(){
    int n, q;
    while(cin >> n >> q){
        init(n);
        for(int i = 0; i < q; i++){
            char c;
            int x, y;
            cin >> c >> x >> y;
            if(c == '0'){
                update(x,y);
            } else {
                cout << query(x,y+1) << endl;
            }
        }
    }
}

Measured memory_bytes: 2184
// スタックサイズ: 100MB

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
using namespace std;

typedef int64_t ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ll INF = 1000000000000000000;
#define fori(i, a, b) for (ll i = (a); i < (b); ++i)
#define ford(i, a, b) for (ll i = (b - 1); (a) <= i; --i)
#define rep(i, n) fori(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define fst first
#define snd second
ll pw(ll x, ll y) { ll r = 1;  rep(i, y) { r *= x; }; return r; }


int main() {
	
	vll arr; arr.push_back(1);
	fori(i, 2, 32) {
		ll tmp = i;
		while (tmp * i <= 1000) {
			tmp *= i;
			arr.push_back(tmp);
		}
	}
	sort(all(arr));
	arr.erase(unique(all(arr)), arr.end());

	ll x;
	cin >> x;
	cout << *(upper_bound(all(arr), x) - 1) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define F first
#define s second
#define int long long		
int a[214514];
int b[214514];
signed main(){
	ic(n)
	if(n<10)c(n)
	else if(n<100&&n>9)c(9)
	else if(n<1000&&n>99)c(n-90)
	else if(n<10000&&n>999)c(909)
	else if(n<100000&&n>9999)c(n-9090)
	else c(90909)
}	

Measured memory_bytes: 256
#include <cstdio>

const int MAXN = (int)2e5;

int p[MAXN];

double solve(int n, int k) {
  double cur_exp_val = 0.0;
  int index = 0;
  for (; index < k; ++index) {
    cur_exp_val += (1.0 + p[index]) / 2.0;
  }
  double max_exp_val = cur_exp_val;
  for (; index < n; ++index) {
    cur_exp_val += (1.0 + p[index]) / 2.0;
    cur_exp_val -= (1.0 + p[index - k]) / 2.0;
    if (cur_exp_val > max_exp_val) {
      max_exp_val = cur_exp_val;
    }
  }
  return max_exp_val;
}

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", p + i);
  }
  printf("%.6lf\n", solve(n, k));
  return 0;
}


Measured memory_bytes: 896
from collections import Counter
n=int(input())
s=input()
c=Counter(s)
ans = c['R'] * c['G'] * c['B']
for i in range(n-2):
	for j in range(i+1,n-1):
		k=j+(j-i)
		if k>=n:
			break
		if s[i]!=s[j]!=s[k]!=s[i]:
			ans -=1
print(ans)


Measured memory_bytes: 9464
import queue

INF = 10000000

h, w = map(int, input().split())

d = [[INF for i in range(w)] for i in range(h)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

sy = 0
sx = 0
gy = h - 1
gx = w - 1

map = [[] for i in range(h)]
for i in range(h):
    map[i] = input()

# BFS: Breadth-First Search
que = queue.Queue()
que.put([sy,sx])
d[sy][sx] = 0

while not que.empty():
    p = que.get()
    if p[0] == gy and p[1] == gx:
        break
    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if nx<w and nx>=0 and ny<h and ny>=0 and map[ny][nx]!="#" \
            and d[ny][nx]==INF:
            d[ny][nx] = d[p[0]][p[1]] + 1
            que.put([ny, nx])

if d[gy][gx] == INF:
    print(-1)
else:
    count = 0
    for i in range(h):
        for j in range(w):
            if map[i][j] == ".":
                count += 1
    print(count - d[gy][gx] - 1)



Measured memory_bytes: 3944