akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    while(N != 0){
        int ans = mod;
        for(int i=0; i<=100; i++){
            for(int j=0; j<=1000; j++){
                if(i*i*i + j*j > N) continue;
                chmin(ans,i+j+(N-i*i*i-j*j));
            }
        }
        cout << ans << endl;
        cin >> N;
    }
    return 0;
}


Measured memory_bytes: 3192
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int b = 1;

struct Graph {
    struct Vertex { int n, v, k; };
    struct Edge { int i, n, d; };
    Graph(int n, int m) : v(n, { -1, 0, 1 << 30 }), e(m), n(n), m(0) {}
    void add_edge(int i, int j, int d) {
        e[m] = { j, v[i].n, d };
        v[i].n = m;
        m++;
    }
    void dfs(int i) {
        if (v[i].v) return; else v[i].v = 1;
        for (int j = v[i].n; j >= 0; j = e[j].n) {
            Edge& o = e[j];
            if (v[o.i].k == 1 << 30) {
                v[o.i].k = v[i].k + o.d;
            } else {
                if (v[o.i].k != v[i].k + o.d) b = 0;
            }
            dfs(o.i);
        }
    }
    vector<Vertex> v;
    vector<Edge> e;
    int n, m;
};

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

    int n, m;
    cin >> n >> m;

    Graph g(n, m * 2);
    for (int i = 0; i < m; i++) {
        int l, r, d;
        cin >> l >> r >> d;
        l--; r--;

        g.add_edge(l, r, d);
        g.add_edge(r, l, -d);
    }

    for (int i = 0; i < n; i++) {
        g.v[i].k = 0;
        g.dfs(i);
    }

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

    return 0;
}

Measured memory_bytes: 7296
import java.util.Scanner;

public class Main {
	public static int[]A;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		A = new int[n];
		for(int i = 0; i < n; i++) {
			A[i] = scan.nextInt();
		}
		scan.close();
		int q = partition(0, n - 1);
		System.out.print(A[0]);
		for(int i = 1; i < n; i++) {
			if(i == q) {
				System.out.print(" [" + A[i] + "]");
			}else {
				System.out.print(" " + A[i]);
			}
		}
		System.out.println();
	}

	public static int partition(int p, int r) {
		int x, i, j, t;
		x = A[r];
		i = p - 1;
		for(j = p; j < r; j++) {
			if(A[j] <= x) {
				i ++;
				t = A[i];
				A[i] = A[j];
				A[j] = t;
			}
		}
		t = A[i + 1];
		A[i + 1] = A[r];
		A[r] = t;
		return i + 1;
	}
}


Measured memory_bytes: 71048
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int n;
vector<pair<int,int>> v[100001];
int a,b,c;
int q,k;
long long d[100001];
int x[100000],y[100000];

void dfs(long long num,int node){
    d[node]=num;
    for(int i=0;i<v[node].size();i++){
        int next=v[node][i].first;
        c=v[node][i].second;
        if(d[next]==-1) dfs(num+c,next);
    }
    return;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)d[i]=-1;
    for(int i=0;i<n-1;i++){
        cin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    cin>>q>>k;
    dfs(0,k);
    for(int i=0;i<q;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<q;i++){
        cout<<d[x[i]]+d[y[i]]<<endl;
    }
    return 0;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl; }}



signed main(){

    int A, B, C; cin >> A >> B >> C;
    int ans = B + min(C, A + B + 1);
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long a[200005],c[200005];
int b[200005];
long long n,k,num;
struct node{
	long long num;
	int id;
};
node ssum[200010];
bool cmp(node x,node y){
	if(x.num==y.num)return x.id<y.id;
	return x.num<y.num;
}
bool cmp2(node x,node y){
	return x.id<y.id;
}
long long sum(int x){
	long long ans=0;
	for(int i=x;i>=1;i-=(i&-i))ans+=c[i];
	return ans;
}
void add(int x,int y){
	for(int i=x;i<=n;i+=(i&-i))c[i]+=y;
}
int main(){
	while(cin>>n>>k){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i]-=k;
			ssum[i].num=ssum[i-1].num+a[i];
			ssum[i].id=i;
		}
		sort(ssum+1,ssum+1+n,cmp);
		for(int i=1;i<=n;i++){
			b[ssum[i].id]=i;
		}
		sort(ssum+1,ssum+1+n,cmp2);
		num=0;
		for(int i=1;i<=n;i++){
			if(ssum[i].num>=0)
				num++;
			num+=sum(b[i]);
			add(b[i],1);
		} 
		cout<<num<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll = int64_t; using ull = uint64_t; const ll INF = 9e18;
void print() { cout << endl; }
template<typename Head,typename... Tail> void print(Head head,Tail... tail){cout<<head;if(sizeof...(Tail)>0)cout<<" ";print(tail...);}
void print0() {}
template<typename Head,typename... Tail> void print0(Head head,Tail... tail){cout<<head;print0(tail...);}
// clang-format on

int main() {
    ll N, K, C;
    cin >> N >> K >> C;
    string S;
    getline(cin, S);
    getline(cin, S);
    vector<bool> work(N, false);
    for (ll i = 0; i < N; i++) {
        if (S.at(i) == 'o') {
            work[i] = true;
        }
    }
    vector<ll> rightmax(N, 0);
    for (ll i = N - 1; i >= 0; i--) {
        if (work[i]) {
            rightmax[i] = 1;
        }
        if (i == N - 1) {
            continue;
        }
        if (i + C + 1 <= N - 1 && work[i]) {
            rightmax[i] = max(rightmax[i + 1], 1 + rightmax[i + C + 1]);
        } else {
            rightmax[i] = max(rightmax[i], rightmax[i + 1]);
        }
    }

    vector<ll> leftmax(N, 0);
    for (ll i = 0; i < N; i++) {
        if (work[i]) {
            leftmax[i] = 1;
        }
        if (i == 0) {
            continue;
        }
        if (i - C - 1 >= 0 && work[i]) {
            leftmax[i] = max(leftmax[i - 1], 1 + leftmax[i - C - 1]);
        } else {
            leftmax[i] = max(leftmax[i], leftmax[i - 1]);
        }
    }
    for (ll i = 0; i < N; i++) {
        ll total = 0;
        if (i > 0) {
            total += leftmax[i - 1];
        }
        if (i < N - 1) {
            total += rightmax[i + 1];
        }
        if (total < K) {
            print(i + 1);
        }
    }
}


Measured memory_bytes: 6824
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
 
int main () {
  int h, w;	cin >> h >> w;
  string s[100];
  rep(i,h) cin >> s[i];
  rep(i,h)rep(j,w){
    if (s[i][j] == '#') continue;
    s[i][j] = '0';
    
    for(int dx = -1; dx<=1; dx++) {
      for(int dy= -1; dy<=1; dy++) {
        int nx=i+dx, ny=j+dy;
        if(nx >= 0 && nx < h && ny >= 0 && ny < w) {
          if(s[nx][ny] == '#')	s[i][j]++;
        }
      }
    }
  }
  rep(i,h)	cout << s[i] << endl;
}

Measured memory_bytes: 256
fun next() = readLine()!!.split(" ")

fun main(args: Array<String>) {
    val (range_s, sum_s) = next()
    val range = range_s.toInt()
    val sumLimit = sum_s.toLong()
    val array = next().map { it.toLong() }.toMutableList()

    var result = 0L
    for (i in 1 until range) {
        var a1 = array[i - 1]
        var a2 = array[i]
        if (a1 + a2 <= sumLimit) {
            continue
        }
        if (a1 >= sumLimit) {
            result += a1 + a2 - sumLimit
            a2 = 0L
            a1 = sumLimit
        } else {
            result += a2 - (sumLimit - a1)
            a2 = sumLimit - a1
        }
        array[i - 1] = a1
        array[i] = a2
    }
    println(result)
}


Measured memory_bytes: 73976
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    char[] date =  sc.next().toCharArray();
    int month = (date[5] - 48) * 10 + date[6] - 48;
    if(month >= 5){
      System.out.println("TBD");
    }else{
      System.out.println("Heisei");
    }
  }
}

Measured memory_bytes: 21716
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    int n,m,a,max;
    scanf("%d",&n);
    m=sqrt(n);
    a=floor(m);
    max=a*a;
    printf("%d\n",max);
    return 0;
}

Measured memory_bytes: 128
s = input()[::-1]
ls = ['dream', 'dreamer', 'erase', 'eraser']
ls = [ls[i][::-1] for i in range(4)]
ans = 'YES'
i = 0
while i < len(s):
    ng = 1
    for j in range(4):
        if s[i:i+len(ls[j])] == ls[j]:
            i += len(ls[j])
            ng = 0
    if ng:
        ans = 'NO'
        break
print(ans)

Measured memory_bytes: 67596
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    in>>k;
    cout<<a[--k]<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
#define M 1000000
#define L 14
 
char H[M][L];
 
int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}
 
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}
 
int h1(int key){
  key = key%M;
  return key;}


int h2(int key){
  key = 1+key%(M-1);
  return key;}


int find(char str[]){
  long long sum,key2,i;
  sum = getKey(str);
  for(i=0;i<20;i++){
    key2=(h1(sum)+i*h2(sum))%M;
    if(strcmp(H[key2],str)==0)return 1;
    else if(strlen(H[key2])==0)return 0;
  }
  return 0;
}
 
int insert(char str[]){
  long long sum,key2,i;
  sum = getKey(str);
  for(i=0;i<20;i++){
    key2=(h1(sum)+i*h2(sum))%M;
    if(strcmp(H[key2],str)==0)return 1;
    if(strlen(H[key2])==0){
      strcpy(H[key2],str);
      return 0;
    }
  }
}



int main(){
  int i, n, h;
  char str[L], com[9];
  for ( i = 0; i < M; i++ ) H[i][0] = '\0';
   
  scanf("%d", &n);
   
  for ( i = 0; i < n; i++){
    scanf("%s %s", com, str);
     
    if ( com[0] == 'i' ){
      insert(str);
    } else {
      if (find(str)){
    printf("yes\n");
      } else {
    printf("no\n");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 14280
items = []
while True:
    item = int(input())
    if item == 0:
        break
    else:
        items.append(item)

for item in items:
    cnt = 0
    tmp = list(range(1, item+1))
    for i in range(2, item+1):
        for j in range(item - i):
            win = tmp[j:j+i]
            win = sum(win)
            if win == item:
                cnt += 1
                break
            elif win > item:
                break
    print(cnt)



Measured memory_bytes: 5612
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, x, y = map(int, readline().split())

total = 0

#
if a + b >= 2*c:    # ABを買う場合
    if (max(x, y) == x and 2*c < a) or (max(x, y) == y and 2*c < b):    # ABのみを買う場合
        total = max(x, y) * 2*c
    else:
        # 足りない方を買い足す場合
        if min(x, y) == x:
            total = x * 2 * c + (y - x) * b
        else:
            total = y * 2 * c + (x - y) * a
else:               # ABを買わない場合
    total = a*x + b*y

print(total)


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

int main () {
    int n, m;
    cin >> n >> m;

    int x, y;

    int ans[n+5];

    for (int i=0 ; i<n+5 ; i++) {
        ans[i] = 0;
    }

    for (int i=0 ; i<m ; i++) {
        cin >> x >> y;

        ans[x]++;
        ans[y+1]--;
    }

    int temp=0;

    for (int i=0 ; i<n+5 ; i++) {
        temp += ans[i];
        ans[i] = temp;
    }

    int total = 0;

    for (int i=0 ; i<n+5 ; i++) {
        if (ans[i]==m) {
            // cout << "i is " << i << endl;
            total++;
        }
    }

    cout << total << endl;
}

Measured memory_bytes: 640
n, k, q = map(int,input().split())
A = [int(input()) for i in range(q)]
S = [k]*n
for a in A:
  S[a-1] += 1
for i in range(n):
  S[i] -= q
  if S[i] <= 0:
    print("No")
  else:
    print("Yes")

Measured memory_bytes: 11752
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define mkp make_pair
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005
using namespace std;
/*
ll bin(ll i,ll j){
	ll mid=(i+j)/2;
	if(a[mid]==x)reutrn mid;
	else if(ans>x)return bin(i,mid-1);
	else return bin(mid+1,j);
}/*
ll power(ll base,ll power){
    ll res=1;
    base=base%mod;
    while(power>0){
    	if(power&1){
    		res=(res*base)%mod;
		}
		power=power>>1;
		base=(base*base)%mod;
	}
	return res;
}
*/
/*
int nCr(int x, int y){
	if(y>x)return 0;
	int num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}
*/
/*bool prime[n+1];
void SieveOfEratosthenes(int n){
	rep(i,0,n+1)prime[i]=true
    for (int p=2;p*p<=n;p++)
        if (prime[p])
            for (int i=p*p;i<=n;i+=p)prime[i]=false;
}*/
/*
int gcd(int a,int b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
*/
int solve(){
    string s;
    cin>>s;
    int n=s.length();
    int a=0,b=n-1,c=(n-2)/2;
    int p=0;
	while(a<b){
    	if(s[a]!=s[b]){
    		p=1;
    		break;
		}
		a++;
		b--;
	}
	if(p==1)return cout<<"No"<<endl,0;
	a=0;
	while(a<c){
		if(s[a]!=s[c]){
			p=1;
			break;
		}
		a++;
		c--;
	}
	if(p==1)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}
int main(){
    waste;
    int t;
    //cin>>t;
    t=1;
    while(t--){
       	solve();
    }
}


Measured memory_bytes: 256
'use strict'
const Main = (input) => {
  let tmp = input.split('\n');
  let r = tmp[0].split(' ').map(Number)[0];
  let D = tmp[0].split(' ').map(Number)[1];
  let x =tmp[0].split(' ').map(Number)[2]

  for (let i = 1; i <= 10; i++){
    x = r * x - D;
    console.log(x);
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7628
n = gets.to_i
v = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

x = 0
y = 0

v.zip(c).each do |v, c|
  if v - c > 0
    x = x + v
    y = y + c
  end
end

puts(x - y)
  

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
const int md = 1e9 + 7;
inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}
inline int mul(int a, int b) {
  return (int)((long long)a * b % md);
}
inline int inv(int a) {
  a %= md;
  if(a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= a * t; swap(a, b);
    u -= v * t; swap(u, v);
  }
  assert(b == 1);
  if(u < 0) u += md;
  return u;
}
#define FMAX 1000000
int fct[FMAX];
void init () {
  fct[0] = 1;
  for (int i = 1; i < FMAX; i++) {
    fct[i] = mul(fct[i - 1], i);
  }
}
int binom (int n, int k) {
  assert(0 <= n && n <= FMAX);
  if (k < 0 || n < k) {
    return 0;
  }
  return mul(fct[n], mul(inv(fct[k]), inv(fct[n - k])));
}
int getPt (int n, int k) {
  return binom(n + k - 1, k - 1);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  int n, m;
  cin >> n >> m;
  int crr = 2;
  int tmp = 0;
  stack<int> stk;
  while (crr * crr <= m || crr == m) {
    if (!(m % crr)) {
      m /= crr;
      tmp++;
    } else {
      if (tmp) {
        stk.push(tmp);
      }
      tmp = 0;
      crr++;
    }
  }
  if (tmp) {
    stk.push(tmp);
  }
  if (m != 1) {
    stk.push(1);
  }
  int ret = 1;
  while (!stk.empty()) {
    int mlt = stk.top();
    stk.pop();
    ret = mul(ret, getPt(mlt, n));
  }
  cout << ret << '\n';
  return 0;
}

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



int main(){
    for(int i = 0; i < 11; i++){
        string s;
        cin >> s;
        if(s == "-"){ break; }
        else{
            int n;
            cin >> n;
            for(int j = 0; j < n; j++){
                string t;
                int m;
                cin >> m;
                for(int k = 0; k < m; k++){
                    t.push_back(s[0]);
                    s.erase(s.begin());
                    s.push_back(t[k]);
                }
            }
            cout << s << endl;
        }
    }
}


Measured memory_bytes: 3208
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define forsn(i,x,y) for(long long i = (x) ; i <= (y) ; ++i)
typedef long long ll;
typedef long double ld;

enum animal {wolf='W', sheep='S', none='N'};

animal nextAnimal(animal prev, animal cur, bool same) {
  if(cur == wolf) {
    if(prev == wolf) {
      if(same) {
        return sheep;
      }
      else {
        return wolf;
      }
    }
    else { // prev == sheep
      if(same) {
        return wolf;
      }
      else {
        return sheep;
      }
    }
  }
  else { // cur == sheep
    if(prev == wolf) {
      if(same) {
        return wolf;
      }
      else {
        return sheep;
      }
    }
    else { // prev == sheep
      if(same) {
        return sheep;
      }
      else {
        return wolf;
      }
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<bool> b;
  forn(n0,n) {
    char c;
    cin >> c;
    b.push_back(c=='o');
  }
  /*
  for(bool e : b) {
    cout << e << " " ;
  }
  */
  vector<vector<animal>> as;
  if(b[0]) {
    vector<animal> a1(n,none);
    a1[0] = sheep;
    a1[1] = sheep;
    a1[n-1] = sheep;
    as.push_back(a1);
    vector<animal> a2(n,none);
    a2[0] = sheep;
    a2[1] = wolf;
    a2[n-1] = wolf;
    as.push_back(a2);
    vector<animal> a3(n,none);
    a3[0] = wolf;
    a3[1] = sheep;
    a3[n-1] = wolf;
    as.push_back(a3);
    vector<animal> a4(n,none);
    a4[0] = wolf;
    a4[1] = wolf;
    a4[n-1] = sheep;
    as.push_back(a4);
  }
  else {
    vector<animal> a1(n,none);
    a1[0] = wolf;
    a1[1] = sheep;
    a1[n-1] = sheep;
    as.push_back(a1);
    vector<animal> a2(n,none);
    a2[0] = wolf;
    a2[1] = wolf;
    a2[n-1] = wolf;
    as.push_back(a2);
    vector<animal> a3(n,none);
    a3[0] = sheep;
    a3[1] = sheep;
    a3[n-1] = wolf;
    as.push_back(a3);
    vector<animal> a4(n,none);
    a4[0] = sheep;
    a4[1] = wolf;
    a4[n-1] = sheep;
    as.push_back(a4);
  }
  int ans = -1;
  forn(k,as.size()) {
    //vector<animal> a = as[k];
    //cout << "k:" << k << endl;
    for(int i = 1; i < n-1; i++) {
      animal next = nextAnimal(as[k][i-1],as[k][i],b[i]);
      //cout << " i:" << i << " " << (char)next << endl;
      if(i+1 == n-1) {
        if(next == as[k][n-1]) {
          animal nextnext = nextAnimal(as[k][i], as[k][i+1],b[i+1]);
          if(nextnext == as[k][0]) {
            ans = k;
          }
        }
      }
      else {
        as[k][i+1] = next;
      }
    }
    if(ans != -1) {
      break;
    }
  }
  if(ans == -1) {
    cout << -1 << endl;
  }
  else {
    for(animal ani : as[ans]) {
      cout << (char)ani;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 3456
def solve():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if sum(A) < sum(B):
        return -1
    AB = [a - b for a, b in zip(A, B)]
    plus = [x for x in AB if x > 0]
    minus = [x for x in AB if x < 0]
    t = sum(minus)
    cnt = 0
    for m in sorted(plus, reverse=True):
        if t >= 0:
            break
        t += m
        cnt += 1
    return cnt + len(minus)
    ans = 0
    return ans
print(solve())


Measured memory_bytes: 18292
def lcs(a, b):
    lengths = [[0] * (len(b) + 1) for i in range(len(a) + 1)]

    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i + 1][j + 1] = lengths[i][j] + 1
            else:
                lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])

    result = []
    x, y = len(a), len(b)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x - 1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y - 1]:
            y -= 1
        else:
            result.append(a[x - 1])
            x -= 1
            y -= 1

    return result[::-1]


print(''.join(lcs(input(), input())))


Measured memory_bytes: 112348
n = int(input())
dp = [0, 0, 0]
for i in range(n):
  a, b, c = map(int, input().split ())
  nxt = [max(dp[1], dp[2]) + a,
         max(dp[0], dp[2]) + b,
         max(dp[1], dp[0]) + c
         ]
  dp = nxt
print(max(dp))

Measured memory_bytes: 3060
n,k = gets.split.map(&:to_i)
nums = {}
n.times do
    a,b = gets.split.map(&:to_i)
    if nums[a] == nil
        nums[a] = b
    else
        nums[a] += b
    end
end

nums = Hash[nums.sort]

cnt = 0
nums.each do |i,v|
    cnt += v
    if cnt >= k
        puts i
        exit
    end
end

Measured memory_bytes: 13576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


int main(){
    ll n,m; cin>>n>>m;
    vector<pair<ll,ll>> drink(n);
    rep(i,n) cin>>drink[i].first>>drink[i].second;
    sort(drink.begin(), drink.end());
    ll res=0, cnt=0, i=0;
    while(cnt<m){
        if(drink[i].second>(m-cnt)){
            res+=drink[i].first*(m-cnt);
            break;
        }else{
            res+=drink[i].second*drink[i].first;
            cnt+=drink[i].second;
            i++;
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;



int main() {
	
	int n, d;
	cin >> n >> d;
	int x[15][15] = {};

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < d; j++) {
			cin >> x[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int z = 0;
		double r = 0;
		for (int j = i + 1; j < n; j++) {
			int z = 0;
			double r = 0;

			for (int k = 0; k < d; k++) {
				z += abs(x[i][k] - x[j][k])*abs(x[i][k] - x[j][k]);
				r += abs(x[i][k] - x[j][k])*abs(x[i][k] - x[j][k]);
				//cout << x[i][k] << " " << x[j][k];
			}
			int p = sqrt((double)z);
			double v = sqrt(r);
		//	cout << v;
			if (p*p==v*v)ans++;
		

		}
	}
	cout << ans << endl;

	return 0;



}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
int main()
{
	string str;
	getline(cin, str);
	for (int i = 0; i < str.length(); i++)
	{
		if (isupper(str[i]))str[i] = tolower(str[i]);
		else if (islower(str[i]))str[i] = toupper(str[i]);
		else;
		cout << str[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3200
n,*a=map(int,open(0).read().split());b={};M=10**9+7;p=n+1;q=r=1
for i,x in enumerate(a):
 if x in b:d=i-b[x];break
 b[x]=i
for k in range(n+1):print((p-q)%M);q=q*(n-d-k)*r%M;r=pow(k+2,M-2,M);p=p*(n-k)*r%M

Measured memory_bytes: 20448
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, c[100];
inline int solve() {
	int ret = 0, u = 1;
	for(int i = 0; i < m - 1; i++) u *= c[i];
	for(int i = m - 1; i < n; i++) u *= c[i], ret = max(ret, u), u /= c[i - m + 1];
	return ret;
}
int main() {
	while(scanf("%d%d", &n, &m), n) {
		for(int i = 0; i < n; i++) scanf("%d", c + i);
		int ret = 0, res = solve();
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				swap(c[i], c[j]);
				ret = max(ret, solve());
				swap(c[i], c[j]);
			}
		}
		if(ret < res) puts("NO GAME");
		else printf("%d\n", ret - res);
	}
}

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

int main(){
    string str = "";
    vector<string::size_type> peach;
    vector<string::size_type> apple;
    getline(cin, str);
    string::size_type pos;
    string find_str = "apple";
    for(pos=str.find(find_str); pos!=string::npos; pos=str.find(find_str, find_str.length()+pos)){
        apple.push_back(pos);
    }
    find_str = "peach";
    for(pos=str.find(find_str); pos!=string::npos; pos=str.find(find_str, find_str.length()+pos)){
        peach.push_back(pos);
    }
    for(int i=0; i<peach.size(); i++){
        str.replace(peach[i], 5, "apple");
    }
    for(int i=0; i<apple.size(); i++){
        str.replace(apple[i], 5, "peach");
    }
    cout << str << endl;
    return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		char[] str = sc.next().toCharArray();
		int n = str.length;

		long result = 0;
		int prevBlack = n;

		if(str[n - 1] == 'B'){
			prevBlack = n - 1;
		}
		for(int i = n - 2; i >= 0; i--){
			if(str[i] == 'B' && str[i + 1] == 'W'){
				result += prevBlack - i - 1;
				prevBlack--;
				str[i] = 'W';
			}
			else if(str[i] == 'B'){
				prevBlack = i;
			}
		}

		System.out.println(result);
	}
}


Measured memory_bytes: 31496
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,-1};
const int dy[6] = {0, 1, 0, -1,1,-1};
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; }
// ---------------------------------------------------------------------------


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(1){
        int n,m,p,a,b;
        cin >> n >> m >> p >> a >> b;
        if(n == 0) break;
        a--;b--;
        vector<int> t(n);
        for(int i=0; i<n; i++) cin >> t[i];
        vector<vector<P>> G(m);
        for(int i=0; i<p; i++){
            int x,y,z;
            cin >> x >> y >> z;
            x--;y--;
            G[x].emplace_back(y,z);
            G[y].emplace_back(x,z);
        }
        vector<vector<double>> dp(1LL<<n, vector<double> (m,inf));
        dp[0][a] = 0;
        for(int bit=0; bit<(1LL<<n); bit++){
            for(int k=0; k<n; k++){
                if(bit & (1LL<<k)) continue;
                int nbit = bit | (1LL<<k);
                for(int v=0; v<m; v++){
                    for(auto hoge: G[v]){
                        int nv = hoge.first;
                        int cost = hoge.second;
                        chmin(dp[nbit][nv],dp[bit][v] + (double)cost/t[k]);        
                    }
                }
            }
        }
        double ans = inf;
        for(int i=0; i<(1LL<<n); i++){
            chmin(ans,dp[i][b]);
        }
        if(ans == inf){
            cout << "Impossible" << enld;
        }else{
            cout << fixed << setprecision(10) << ans << enld;
        }
    }
    return 0;
}


Measured memory_bytes: 3364
n = int(input())
a = input().strip().split()

# bubble sort
b = a[:]
for i in range(n):
    for j in range(n - 1, i, -1):
        if b[j][1] < b[j - 1][1]:
            b[j], b[j - 1] = b[j - 1], b[j]

print(' '.join(b))
print('Stable')

# selection sort
for i in range(n):
    mini = i
    for j in range(i, n):
        if a[j][1] < a[mini][1]:
            mini = j
    a[i], a[mini] = a[mini], a[i]
print(' '.join(a))
print('Stable' if a == b else 'Not stable')

Measured memory_bytes: 6728
k = int(input())
if k < 10:
    print(k)
else:
    d = [[str(i)] for i in range(10)]
    n = 9
    while True:
        dd = [None for _ in range(10)]
        dd[0] = ['0' + j for j in d[0]] + ['0' + j for j in d[1]]
        for i in range(1, 9):
            si = str(i)
            dd[i] = [si + j for j in d[i - 1]] + [si + j for j in d[i]] + [si + j for j in d[i + 1]]
            n += len(dd[i])
            if n >= k:
                break
        else:
            i += 1
            dd[9] = ['9' + j for j in d[8]] + ['9' + j for j in d[9]]
            n += len(dd[i])
        if n >= k:
            print(dd[i][k - n - 1])
            break
        d = dd


Measured memory_bytes: 10228
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++){
            list.add(sc.nextInt());
        }

        int answer = 0;
        boolean endFlag = false;

        while (true){
            for(int number : list){
                if (number % Math.pow(2, answer + 1) != 0){
                    endFlag = true;
                    break;
                }
            }
            if (endFlag){
                break;
            }
            answer += 1;
        }
        System.out.println(answer);

    }
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
int biter(int x,int y){
  int ans = 0;
  while(x){
    ans += x%y;x /= y;
  }
  return ans;
}
int main(){
  int n,i,ans = 100000,a,b,c;cin >> n;
  for(i=0;i*9<=n;i++){
    c = i*9;a = (n-c)%6;b = n-a-c;
    ans = min(ans,a+biter(b/6,6)+biter(c/9,9));
  }
  cout << ans << "\n";
}
  

Measured memory_bytes: 256
def main():
    N = int(input())
    S = input()

    left = 0
    right = 0
    for s in S:
        if s == '(':
            right += 1
        else:
            if right <= 0:
                left += 1
            else:
                right -= 1

    ans = left * '(' + S + right * ')'
    print(ans)


if __name__ == "__main__":
    main()

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

int main() {
	int i, j, k;
	int	n, m, h, g, a, b, c, d, l, r;
	int f = 0;
	int w;
	int aa[110000];
	int bb[110000];

	scanf("%d", &n);

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

	i = 0;
	bb[i] = 0;
	f = 0;
	w = 0;
	for (j = i;w < n;j++) {
		if (j < n) {
		}
		else {
			j = 0;
		}
		if (f == 0) {
			bb[i] = bb[i] + aa[j];
			f = 1;
			w++;
		}
		else {
			bb[i] = bb[i] - aa[j];
			f = 0;
			w++;
		}
	}
	for (i = 1;i < n;i++) {
		bb[i] = (aa[i-1] - (bb[i - 1] / 2))*2;
	}

	for (i = 0;i < n;i++) {
		printf("%d ", bb[i]);
	}


	return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int N, x[100010], y[100010];
vector<int> s[100010], t[100010];
bool used[100010];

void dfs(int idx, set<int>& xs, set<int>& ys){
    if(used[idx]) return;
    used[idx] = true;
    xs.insert(x[idx]);
    ys.insert(y[idx]);

    for(auto u : s[x[idx]]){
        dfs(u, xs, ys);
    }

    for(auto u : t[y[idx]]){
        dfs(u, xs, ys);
    }
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
        s[x[i]].push_back(i);
        t[y[i]].push_back(i);
    }

    ll ans = 0;
    for(int i = 0; i < N; i++){
        if(used[i]) continue;
        set<int> xs, ys;
        dfs(i, xs, ys);
        ll a = xs.size(), b = ys.size();
        
        ans += a * b;
    }
    cout << ans - N << endl;
    return 0;
}

Measured memory_bytes: 18304
#include <stdio.h>
#include <string.h>
int main()
{
    int a[15],maxx=0,c=0;
    for(int i=1;i<=3;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>maxx)
            maxx=a[i];
        c=c+a[i];
    }


    printf("%d\n",c-maxx);
    return 0;
}


Measured memory_bytes: 760
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define VECV(a,n,m) vector<vector<int>> a(n, vector<int>(m));
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin>>N;
  string A[N];
  rep(i,N){
    cin>>A[i];
  }
  sort(A,A+N);
  int ans=1;
  rep(i,N-1){
    if(A[i]!=A[i+1])
      ans+=1;
  }
  
  cout<<ans<<endl;

}

Measured memory_bytes: 9912
$dx = [1,1,0,-1,-1,-1,0,1]
$dy = [0,1,1,1,0,-1,-1,-1]
$maxW = 0
$maxH = 0
$seen = []
$islandsMap = []
$ans = []

def HowManyLslands()
  $islandsMap = []
  $seen = Array.new($maxH).map{Array.new($maxW, false)}
  $maxH.times do
    $islandsMap << gets.split().map(&:to_i)
  end
  doSearch($maxH, $maxW)
end

def dfs(h, w)
  $seen[h][w] = true
  8.times do |i|
    nw = $dx[i] + w
    nh = $dy[i] + h
    next if nw < 0 || nw >= $maxW || nh < 0 || nh >= $maxH
    next if $islandsMap[nh][nw] == 0
    next if $seen[nh][nw]
    dfs(nh, nw)
  end
end

def doSearch(h, w)
  count = 0
  h.times do |i|
    w.times do |j|
      if $islandsMap[i][j] == 0
        $seen[i][j] = true
        next
      end
      next if $seen[i][j]
      dfs(i, j)
      count += 1
    end
  end
  $ans << count
end


loop do
  $maxW, $maxH = gets.split().map(&:to_i)
  break if $maxW == 0 && $maxH == 0
  HowManyLslands()
end

$ans.each{|i| puts i}


Measured memory_bytes: 13276
#include<stdio.h>

int main(){

  int  i, j;
  double x[3], y[3], xp, yp, str[3], stock;

  while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2],&xp,&yp) != EOF){

    for(i = 0; i < 2; i++){
      for(j = i; j < 3; j++){
	if(x[i] > x[j]){
	  stock = x[i];
	  x[i] = x[j];
	  x[j] = stock;
	  stock = y[i];
	  y[i] = y[j];
	  y[j] = stock;
	}
      }
    }

    if(x[0] - x[1] != 0){
      str[0] = (y[1] - y[0]) / (x[1] - x[0]) * (xp - x[0]) + y[0];
    }else{
      str[0] = y[1];
    }

    if(x[1] - x[2] != 0){
      str[1] = (y[1] - y[2]) / (x[1] - x[2]) * (xp - x[1]) + y[1];
    }else{
      str[1] = y[1];
    }

    if(x[2] - x[0] != 0){
      str[2] = (y[2] - y[0]) / (x[2] - x[0]) * (xp - x[0]) + y[0];
    }else{
      str[2] = y[2];
    }

    if(y[0] < y[1]){


      if(xp < x[0] || xp > x[2]){
	printf("NO\n");
	continue;
      }else if(yp >= str[0]){
	printf("NO\n");
	continue;
      }else if(yp >= str[1]){
	printf("NO\n");
      continue;
      }else if(yp <= str[2]){
	printf("NO\n");
	continue;
      }else{
	printf("YES\n");
      }


    }else{
     if(xp < x[0] || xp > x[2]){
	printf("NO\n");
	continue;
      }else if(yp <= str[0]){
	printf("NO\n");
	continue;
      }else if(yp <= str[1]){
	printf("NO\n");
      continue;
      }else if(yp >= str[2]){
	printf("NO\n");
	continue;
      }else{
	printf("YES\n");
      }

    }
  }
  return 0;
  
  }

Measured memory_bytes: 0
from collections import deque


def submit():
    s = input()

    # 出来上がる文字列をdequeで管理
    curr = deque()
    for c in s:
        curr.append(c)

    # 先頭sideを管理する 1 = left, -1 = right
    front = 1

    # Queryを処理する
    q = int(input())
    for _ in range(q):
        query = input()
        if query[0] == '1':
            front *= -1
        else:
            _, f, c = query.split()
            if f == '1': # 先頭にcを追加
                if front == 1: # 先頭はleft
                    curr.appendleft(c)
                else:
                    curr.append(c)
            else:   # 末尾にcを追加
                if front == 1: #末尾はright
                    curr.append(c)
                else:
                    curr.appendleft(c)

    # 出力処理
    results = ""
    while len(curr) > 0:
        if front == 1:
            results += curr.popleft()
        else:
            results += curr.pop()

    print(results)
        


if __name__ == "__main__":
    submit()

Measured memory_bytes: 6636
#include<stdio.h>
int main(){
  int n,i;
  scanf("%d",&n);
  double x,sum=0;
  char u[3];
  for(i=0;i<n;i++){
    scanf("%lg%s",&x,u);
    if(u[0]=='B') x*=380000;
    sum+=x;
  }
  printf("%lg",sum);
}


Measured memory_bytes: 128
N = gets.to_i
abc = Array.new(N)
N.times do |i|
  abc[i] = gets.split.map(&:to_i)
end

dp = Array.new(N)
dp[0] = [0,0,0]

(1..N).each do |i|
  dp[i] = []
  dp[i][0] = abc[i-1][0] + (dp[i-1][1] < dp[i-1][2] ? dp[i-1][2] : dp[i-1][1])
  dp[i][1] = abc[i-1][1] + (dp[i-1][2] < dp[i-1][0] ? dp[i-1][0] : dp[i-1][2])
  dp[i][2] = abc[i-1][2] + (dp[i-1][0] < dp[i-1][1] ? dp[i-1][1] : dp[i-1][0])
end

puts dp[N].max


Measured memory_bytes: 12028
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
typedef pair<int,int> pii;

int main(){
  int n,k;
  cin>>n>>k;
  vector<int> x,y;
  int t;
  
  for(int i=0;i<n;i++){
    cin>>t;
    if(t==0) k--;
    else{
      x.pb(t);
    }
  }
  //x.pb(0);
  sort(x.begin(),x.end());
  if(k==0){
    cout<<0<<endl;
    return 0;
  }

  int l,r;
  l=0;
  r=k-1;
  int res=1e9;
  for(int i=0;i<=n-k;i++){
    if(x[l]<0 && x[r]<0) res=min(res,-x[l]);
    else if(x[l]>0 && x[r]>0) res=min(res,x[r]);
    else res=min(res,min(-x[l],x[r])*2+max(-x[l],x[r]));
    //cout<<l<<" "<<r<<" : "<<x[l]<<" "<<x[r]<<" "<<res<<endl;
    l++;
    r++;
  }
  cout<<res<<endl;
  return 0;
}



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

int main(){
    int L;
    cin >> L;
    double ans = (L*L*L)/27.0;
    cout << fixed << setprecision(10);
    cout << ans << endl;
}   

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stdint.h>

int as[3005];
int64_t dp[3005][3005];

int main(){
  int N;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&as[i]);
  }
  for(int i=0;i<=N;i++){
    dp[i][i]=0;
  }
  for(int i=N-1;i>=0;i--){
    for(int j=i+1;j<=N;j++){
      dp[i][j]=std::max(as[i]-dp[i+1][j],as[j-1]-dp[i][j-1]);
    }
  }
  printf("%ld\n",dp[0][N]);
  return 0;
}


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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) for(int i = 0 ; i < n ; ++i)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort((x).begin(), (x).end())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n;
int league[9][9];
int win[9];

int solve(int team, int opp){
    if(team == n){
        bool flag = true;
        rep(i, n){
            if(win[i] != 0){
                flag = false;
                break;
            }
        }
        if(flag){
            return 1;
        }else{
            return 0;
        }
    }
    if(opp == n){
        return solve(team + 1, 0);
    }
    if(league[team][opp] != -1){
        return solve(team, opp + 1);
    }
    int res = 0;
    if(win[team] > 0){
        league[team][opp] = 1;
        league[opp][team] = 0;
        --win[team];
        res += solve(team, opp + 1);
        league[team][opp] = -1;
        league[opp][team] = -1;
        ++win[team];
    }
    if(win[opp] > 0){
        league[team][opp] = 0;
        league[opp][team] = 1;
        --win[opp];
        res += solve(team, opp + 1);
        league[team][opp] = -1;
        league[team][opp] = -1;
        ++win[opp];
    }
    return res;
}

int main(){
    while(cin >> n, n){
        fill(league[0], league[n], -1);
        fill(win, win + n, n / 2);
        int m;
        cin >> m;
        rep(i, m){
            int x, y;
            cin >> x >> y;
            --x;
            --y;
            league[x][y] = 1;
            league[y][x] = 0;
            --win[x];
        }
        rep(i, n){
            league[i][i] = 2;
        }
        int ans = solve(0, 0);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3068
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    ll L, R, d;
    cin >> L >> R >> d;

    ll ans = 0;
    exrep(i, L, R) {
        if(i%d == 0) {
            ans++;
        }
    }
    
    out(ans);
    re0;
}

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

int max(int a,int b){
  if(a>b) return a;
  else return b;
}
double min(double a,double b){
  if(a<b) return a;
  else return b;
}
int absolute(int a,int b){
  if(a-b<0) return -(a-b);
  else return a-b;
}
int sum_keta(int n){
  if(n==0) return 0;
  return n%10 + sum_keta(n/10);
}
int main(void){
  int D,N,keta; cin >> D >> N;
  
  if(D==0) keta = 1;
  if(D==1) keta = 100;
  if(D==2) keta = 10000;
  
  if(N==100) N++;
  cout << N * keta << endl;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author dyominov
 */
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);
    AFrog1 solver = new AFrog1();
    solver.solve(1, in, out);
    out.close();
  }

  static class AFrog1 {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
      }
      int[] res = new int[n];
      Arrays.fill(res, Integer.MAX_VALUE);
      res[0] = 0;
      for (int i = 1; i < n; i++) {
        res[i] = Math.min(res[i], res[i - 1] + Math.abs(arr[i] - arr[i - 1]));
        if (i - 2 >= 0) res[i] = Math.min(res[i], res[i - 2] + Math.abs(arr[i] - arr[i - 2]));
      }
      out.println(res[n - 1]);
    }

  }

  static class InputReader implements AutoCloseable {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      //reader = new BufferedReader(new FileReader(stream), 32768);
      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());
    }

    public void close() {
    }

  }
}



Measured memory_bytes: 32172