akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
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;}
typedef pair<int, int> P;
typedef pair<ll,ll> PLL;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    ll X;
    cin >> X;
    ll hoge = X / 11;
    if (X - hoge * 11 == 0) cout << hoge * 2 << endl;
    else if (X - hoge * 11 <= 6) cout << hoge * 2 + 1 << endl;
    else cout << hoge * 2 + 2 << endl;
    return 0;
}


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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string S, T;
	cin >> S >> T;
	for (int i = 0;i<S.size();++i) {
		if (S == T) {
			cout << "Yes" << endl;
			return 0;
		}
		char s = S[S.size() - 1];
		S.pop_back();
		S = s + S;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

class CountBit {
	std::vector<int> vec;
public:
	CountBit(int size) : vec(size, 0) {};
	void increment(int position) {
		while (position < vec.size()) {
			vec[position]++;
			position += ((position + 1) & ~position);
		}
	}
	void decrement(int position) {
		while (position < vec.size()) {
			vec[position]--;
			position += ((position + 1) & ~position);
		}
	}
	int operator[](int position) const {
		int result = 0;
		while (position >= 0) {
			result += vec[position];
			position -= ((position + 1) & ~position);
		}
		return result;
	}
};

class Count2DBit {
	std::vector<CountBit> vec;
public:
	Count2DBit(int height, int width) : vec(height, CountBit(width)) {};
	void increment(int x, int y) {
		while (y < vec.size()) {
			vec[y].increment(x);
			y += ((y + 1) & ~y);
		}
	}
	void decrement(int x, int y) {
		while (y < vec.size()) {
			vec[y].decrement(x);
			y += ((y + 1) & ~y);
		}
	}
	int apply(int x, int y) {
		int result = 0;
		while (y >= 0) {
			result += vec[y][x];
			y -= ((y + 1) & ~y);
		}
		return result;
	}
};
int main() {
	int height, width, bake_time, q; std::cin >> height >> width >> bake_time >> q;
	Count2DBit bake(height, width), baking(height, width);
	std::vector<std::vector<int>> put_time(height, std::vector<int>(width, -1));
	std::queue<std::tuple<int, int, int>> delay;
	for (auto _i = 0; _i < q; ++_i) {
		int t, c, h, w; std::cin >> t >> c >> h >> w; --h; --w;
		switch (c) {
		case 0:
			if (put_time[h][w] == -1) {
				put_time[h][w] = t;
				baking.increment(w, h);
				delay.push(std::make_tuple(t, h, w));
			}
			break;
		case 1:
			if (put_time[h][w] != -1 && put_time[h][w] + bake_time <= t) {
				put_time[h][w] = -1;
				bake.decrement(w, h);
			}
			break;
		default: int h2, w2; std::cin >> h2 >> w2; --h2; --w2;
			while (!delay.empty() && std::get<0>(delay.front()) + bake_time <= t) {
				auto time = std::get<0>(delay.front());
				auto y = std::get<1>(delay.front());
				auto x = std::get<2>(delay.front());
				delay.pop();
				baking.decrement(x, y);
				bake.increment(x, y);
			}
			std::cout << (bake.apply(w2, h2) - bake.apply(w - 1, h2) - bake.apply(w2, h - 1) + bake.apply(w - 1, h - 1)) << ' ' << (baking.apply(w2, h2) - baking.apply(w - 1, h2) - baking.apply(w2, h - 1) + baking.apply(w - 1, h - 1)) << '\n';
			break;
		}
	}
}


Measured memory_bytes: 51172
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	alpha := make([]int, 26)

	for _, v := range s {
		alpha[int(v)-97]++
	}

	for k, v := range alpha {
		if v == 0 {
			fmt.Println(string(k + 97))
			return
		}
	}

	fmt.Println("None")
}

Measured memory_bytes: 1280
read N
read W

sum=0
for x in $W
do
    sum=$(($sum+$x))
done

acc=0
ans=''
for x in $W
do
    acc=$(($acc+$x))
    rest=$(($sum-$acc))
    if [ $acc -gt $rest ]; then
        V=$(($acc-$rest))
    else
        V=$(($rest-$acc))
    fi
    ans="$ans $V"
done

echo $ans | tr ' ' '\n' | sort -n | head -n1

Measured memory_bytes: 988
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<set>
#include<ctime>
#define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#define PERE(r,x,y) for(register int r=(x); r>=(y); r--)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__),fflush(stdout)
#else
#define DBG(...) (void)0
#endif
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

char ch; int si;
char buf[1<<21],*p1=buf,*p2=buf;
int beof = 0;
#define gc() (beof?EOF:(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(beof=EOF):*p1++))
#define gl(x) {char*s=x;while(isspace(*s=gc()));s++;while(!isspace(*s=gc()))s++;*s=0;}

template<class T>
inline void read(T &x) {
    x=0; si=1; for(ch=gc();!isdigit(ch) && ch!='-';ch=gc()) if(beof) return;
    if(ch=='-'){si=-1,ch=gc();} for(;isdigit(ch);ch=gc())x=x*10+ch-'0';
    x*=si;
}
template<class T, class...A> inline void read(T &x, A&...a){read(x); read(a...);}


int main() {
#ifdef sahdsg
    freopen("in.txt","r",stdin);
#endif
    int a,b,c,n; read(a,b,c,n);
    int ans=0;
    for(int i=0; i*a<=n; i++) {
        for(int j=0; i*a+j*b<=n; j++) {
            int k=n-(i*a+j*b);
            if(k%c==0) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


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

int main() {
    string s;
    cin >> s;
    int a = -1, b = -1;
    for (int i = 0; i < (int) s.length() - 1; ++i) {
        if (s[i] == s[i + 1]) a = i + 1, b = i + 2;
    }
    for (int i = 0; i < (int) s.length() - 2; ++i) {
        if (s[i] == s[i + 2]) a = i + 1, b = i + 3;
    }
    cout << a << " " << b << endl;
    return 0;
}

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

int main() {
    string s;
    cin >> s;
    string ans = "No";
    if (s[0] == '9' || s[1] == '9') ans = "Yes";
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Easy Linear Programming.
 */
public class Main {
    public static void main(String[] args) {
        var scanner = new Scanner(System.in);
        var a = scanner.nextInt();
        var b = scanner.nextInt();
        var c = scanner.nextInt();
        var k = scanner.nextInt();

        var sum = Math.min(k, a);
        var remaining = Math.min(k - a - b, c);
        sum += remaining > 0 ? -1 * remaining : 0;
        System.out.println(sum);
    }
}


Measured memory_bytes: 35700
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(N + 2);
  A[0] = 0;
  REP(i, 1, N + 1) cin >> A[i];
  A[N + 1] = 0;

  ll sum = 0;
  REP(i, 0, N + 1) sum += abs(A[i + 1] - A[i]);

  REP(i, 1, N + 1) {
    cout << sum - (abs(A[i] - A[i - 1]) + abs(A[i + 1] - A[i])) + abs(A[i + 1] - A[i - 1]) << endl;
  }
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    set<string>s;
    while (n--){
        string t;
        cin>>t;
        s.insert(t);
    }
    cout<<s.size()<<endl;
    return 0;
}

Measured memory_bytes: 19236
#include <stdio.h>

int main(void) {
    int a, b, c;
    int tmp;
    scanf("%d %d %d", &a, &b, &c);

    tmp = a;
    a = b;
    b = tmp;

    tmp = c;
    c = a;
    a = tmp;

    printf("%d %d %d\n", a, b, c);

    return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

void insertionsort(int* A,int n)
{
	for (int i = 1; i < n; ++i)
	{
		for (int i = 0; i < n; ++i)
		{
			cout<<A[i];
			if(i<n-1)
			{
				cout<<" ";
			}
		}
		cout<<endl;

		int v=A[i];
		int j=i-1;
		while(j>=0&&A[j]>v)
		{
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=v;
	}
	for (int i = 0; i < n; ++i)
	{
		cout<<A[i];
		if(i<n-1)
		{
			cout<<" ";;
		}
	}
	cout<<endl;
}

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	int A[n];

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

	insertionsort(A,n);

	return 0;
}


Measured memory_bytes: 3064
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const long long INFL = 2e18;
const int MOD = 1000000007;
int main(){
	int t1,t2;
	cin >> t1 >> t2;
	ll a1,a2,b1,b2;
	cin >> a1 >> a2 >> b1 >> b2;

	if(t1 * a1 + t2 * a2 == t1 * b1 + t2 * b2){
		cout << "infinity" << endl;
		return 0;
	}

	if(t1 * a1 + t2 * a2 < t1 * b1 + t2 * b2){
		swap(a1,b1);
		swap(a2,b2);
	}


	ll sub = t1 * a1 + t2 * a2 - t1 * b1 - t2 * b2;

	ll ans = 0;
	if(b1 > a1){
		ans += (t1 * (b1 - a1)) / sub;
	}

	if(b2 - a2 > 0){
		ll l = t1 * (b2 - a2) - t1 * (a1 - a2 - b1 + b2);
		ll r = (t1 + t2) * (b2 - a2) - t1 * (a1 - a2 - b1 + b2);

		if(l < 0){
			l = - (- l + sub - 1) / sub;
		}
		else l /= sub;

		if(r < 0){
			r = - (- r + sub - 1) / sub;
		}
		else r = (r + sub - 1) / sub - 1;

		if(r >= 0)ans += r - max(0LL,l) + 1;
	}
	else{
		ll r = t1 * (b2 - a2) - t1 * (a1 - a2 - b1 + b2);
		ll l = (t1 + t2) * (b2 - a2) - t1 * (a1 - a2 - b1 + b2);

		if(l < 0){
			l = - (- l + sub - 1) / sub;
		}
		else l /= sub;

		if(r < 0){
			r = - (- r + sub - 1) / sub;
		}
		else r = (r + sub - 1) / sub - 1;

		if(r >= 0)ans += r - max(0LL,l) + 1;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
static const long long INF = INT64_MAX;
static const long long MOD = (ll)1e9+7;

#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i, n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)((v).size())
#define WHOLE(v) (v).begin(), (v).end()
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).begin(), (v).end())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define CUMSUML(src, dst) FOLDL(src, dst, [](auto a, auto b) {return a+b;})
#define CUMSUMR(src, dst) FOLDR(src, dst, [](auto a, auto b) {return a+b;})
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define SUM(v, d0) ACCUM(v, d0, [](auto a, auto b) {return a+b;})
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);v.erase(unique(v.begin(), v.end()), v.end())

template <typename T>void debug(T t) {cerr << t << endl;}
template <typename T, typename ...Args>void debug(T t, Args ...args) {cerr << t << " ";debug(args...);}
template <typename T>void out(T t) {cout << t << endl;}
template <typename T, typename ...Args>void out(T t, Args ...args) {cout << t << " ";out(args...);}

void solve() {
    str S;
    cin >> S;
    INV(S);
    ll w = 0, ans = 0;
    REP(i, S.size()) {
        if(S[i] == 'W') {
            w++;
        }else {
            ans += w;
        }
    }
    out(ans);
}

int main() {
    fast_io;
    solve();
    return 0;
}


Measured memory_bytes: 720
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

MOD = 10**9 + 7


def f(ls):
    n = len(ls)
    s = 0
    for i, x in enumerate(ls):
        s += (i + 1) * (n - i) * x
        s %= MOD
    return s


n, m = ril()
ls0 = ril()
ls1 = ril()
ls0 = [b - a for a, b in zip(ls0, ls0[1:])]
ls1 = [b - a for a, b in zip(ls1, ls1[1:])]
print(f(ls0) * f(ls1) % MOD)

Measured memory_bytes: 19324
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ll n; cin >> n;
	ll a[n * n + 1] = {}, b[n + 1];
	vector<pair<ll, ll>> v;
	map<ll, ll> m;
	for(ll i = 0; i < n; i++){
		ll po; cin >> po;
		a[po] = i + 1;
		b[i + 1] = n - 1;
		v.push_back(pair<ll, ll>(po, i + 1));
		m[i + 1] = po;
	}
	sort(v.begin(), v.end());
	queue<ll> q;
	for(ll i = 0; i < n; ++i) q.push(v[i].second);
	ll flag = 1;
	for(ll i = 1; i <= n * n; i++){
		if(!a[i]) continue;
		ll po = a[i] - 1;
		for(; flag < i && po; flag++){
			if(a[flag]) continue;
			a[flag] = a[i];
			b[a[i]]--;
			po--;
		}
		if(po){
			cout << "No\n";
			return 0;
		}
	}
	for(ll i = 1; i <= n * n; i++){
		if(a[i]) continue;
		while(!b[q.front()]) q.pop();
		if(m.find(q.front())->second > i){
			cout << "No\n";
			return 0;
		}
		a[i] = q.front();
		b[q.front()]--;
	}
	cout << "Yes\n";
	for(ll i = 1; i <= n * n; i++) cout << a[i] << " ";
	cout << endl;
	return 0;
}

Measured memory_bytes: 3200
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = [int(item) for item in input().split()]
d = [item for item in input().split()]
for i in range(n, n+10**5):
    si = str(i)
    ok = True
    for item in d:
        if item in si:
            ok = False
            break
    if ok:
        print(i)
        exit()

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;
typedef vector<pi> vpi;
typedef set<ll> si;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define f first
#define s second
ll INF = 1e18;
ll MOD = 1e9+7;
#define lb lower_bound
#define ub upper_bound
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
vi V;
vpi A;
ll N,a,b;
char res[40];

int main(){
  cin >> N;
  for (int i=0;i<N;++i){
    cin>>a>>b;
    A.pb(mp(a,b));
  }
  int p = abs(A[0].f + A[0].s)%2;
  for (auto i : A){
    if (abs(i.f + i.s)%2 != p){
      cout<<-1;
      return 0;
    }
  }
  if (!p)V.pb(1);
  V.pb(1);
  for (int i=1;i<=30;++i)V.pb((1LL)<<i);
  cout<<SZ(V)<<'\n';
  for (auto i : V)cout<<i<<' ';cout<<'\n';
  for (auto it : A){
    for (int i=0;i<SZ(V);++i)res[i] = 'X';
    ll a = it.f, b = it.s;
    for (int i=30; i >= 0; --i){
      if (abs(a) > abs(b)){
        if (abs(a) >= (1<<i)){
          if (a > 0){
            res[i+1] = 'R';
            a -= (1<<i);
          }else {
            res[i+1] = 'L';
            a += (1<<i);
          }
        }else{
          if (a > 0){
            res[i+1] = 'R';
            a  = a - (1<<i);
          }else{
            res[i+1] = 'L';
            a = a + (1<<i);
          }
        }
      }else{
        if (abs(b) >= (1<<i)){
          if (b > 0){
            res[i+1] = 'U';
            b -= (1<<i);
          }else {
            res[i+1] = 'D';
            b += (1<<i);
          }
        }else{
          if (b > 0){
            res[i+1] = 'U';
            b  = b - (1<<i);
          }else{
            res[i+1] = 'D';
            b = b + (1<<i);
          }
        }
      }
    }
    if(!p){
      int u = 0, r = 0;
      for (int i=0;i<31;++i){
        if (res[i+1] == 'L')r -= (1<<i);
        if (res[i+1]=='R')r+=(1<<i);
        if (res[i+1] == 'U')u += (1<<i);
        if (res[i+1] == 'D')u -= (1<<i);
      }
      //cout<<r<<' '<<u<<'\n';
      if (r + 1 == it.f)cout<<'R';
      else if (r - 1 == it.f)cout<<'L';
      else if (u + 1 == it.s)cout<<'U';
      else cout<<'D';
    }
    for (int i=1;i<=31;++i)cout<<res[i];cout<<'\n';
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N,T;
  cin>>N>>T;
  vector<int> c(N);
  vector<int> t(N);
  for(int i=0;i<N;i++){
      cin>>c[i]>>t[i];
  }
  int cost = 10000;
  int flag = 0;
  for(int i=0;i<N;i++){
      if(t[i]<=T){
          cost = min(cost,c[i]);
          flag = 1;
      }
  }  
  if(flag==0){
      cout<<"TLE"<<endl;
  }
  else{
      cout<<cost<<endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a/b+" "+a%b+" "+String.format("%.8f",1.0*a/b));  //商 余り 浮動少数8桁
    }
}


Measured memory_bytes: 26520
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        if a != 0 and b != 0:
            g = gcd(a, b) * a // abs(a)
        elif a != 0:
            g = a
        else:
            g = b
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Measured memory_bytes: 135036
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;
const int N = 1e6 + 10;

long long modpow(long long n, long long k, long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}
ll a[3010][3010];
ll dp[3010][3010][5];
void solve(){
    ll r,c,kk;
    cin >> r >> c >> kk;
    //ll a[r+10][c+10];
    memset(a,0,sizeof(a));
    for(int i = 0;i<kk;i++){
        ll v,u,val;
        cin >> v >> u >> val;
        a[v][u] = val;
    }
    //ll dp[r+10][c+10][5];
    memset(dp,0,sizeof(dp));
    for(int i = 0;i<=r;i++){
        for(int j = 0;j<=c;j++){
           for(int k = 1;k<=3;k++){
                ll now = dp[i][j][k];
               if(i<r)dp[i+1][j][1] = max(dp[i+1][j][1],now+a[i+1][j]);
               if(j<c) dp[i][j+1][k] = max(dp[i][j+1][k],now);
                if(k<3&&j<c){
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1],now+a[i][j+1]);
                }
           }
        }
    }
    ll ans = max(dp[r][c][1],max(dp[r][c][2],dp[r][c][3]));
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 428352
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N, pos[400001], sz[400001], ind[400001], ran[26], NEX = 1;
string ne[MX];
map<char,int> nex[400001];
pair<int,char> pre[400001];

void ins(int num, string x) {
    int cur = 0; sz[cur] ++;
    for (char c: x) {
        if (!nex[cur].count(c)) {
            nex[cur][c] = NEX ++;
            pre[nex[cur][c]] = {cur,c};
        }
        cur = nex[cur][c]; sz[cur] ++;
    }
    ind[cur] = num;
}

void compress() {
    FOR(i,1,NEX) if (!ind[i] && sz(nex[i]) == 1) {
        // cout << "HI " << i << "\n";
        nex[pre[i].f][pre[i].s] = nex[i].begin()->s;
        pre[nex[i].begin()->s] = pre[i];
    }
    FOR(i,1,NEX) if (ind[i]) {
        string cur;
        int I = i; 
        while (I != 0) {
            cur += pre[I].s;
            I = pre[I].f;
        }
        reverse(all(cur));
        ne[ind[i]] = cur;
        // cout << ind[i] << " " << cur << "\n";
    }
}

void solve() {
    int x; string y; cin >> x >> y;
    F0R(i,26) ran[y[i]-'a'] = i;
    
    int cur = 0, ans = 1;
    for (char c: ne[x]) {
        // cout << "OH " << cur << "\n";
        for (auto a: nex[cur]) if (ran[a.f-'a'] < ran[c-'a']) ans += sz[a.s]; 
        if (ind[cur]) ans ++;
        cur = nex[cur][c];
    }
    cout << ans << "\n";
}

int main() {
    // freopen("05.txt","r",stdin);
    // freopen("Output.txt","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) {
        string S; cin >> S;
        ins(i,S);
    }
    compress();
    int Q; cin >> Q;
    F0R(i,Q) solve();
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS

Measured memory_bytes: 46364
#include <cstdio>
#include <cctype>
#include <utility>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

const auto gcu = getchar_unlocked;
const auto pcu = putchar_unlocked;
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _sc _il bool scan
_T T in(int c){T n=0;int m=1;while(isspace(c)){c=gcu();}if(c=='-')m=-1,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
_il int in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _ot _il void out
#define _ol _il void outl
_ot(bool b) {pcu('0'+b);}
_ot(const char *s){while(*s)pcu(*s++);}
_ot(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_ot(string s){for(char c:s)pcu(c);}
#endif
_T _ot(T n){static char b[20];char *p=b,m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=n%10*m+'0',n/=10;while(p!=b)pcu(*--p);}
_ol(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _ot(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _ot(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _ol(T&&... t){out(move(t)...);outl();}

int elect() {
	int c = gcu();
	switch(c) {
	case '[':
		{
		vector<int> v;
		for (int r; (r = elect());)
			v.push_back(r);
		auto m = v.begin() + v.size() / 2 + 1;
		nth_element(v.begin(), m, v.end());
		return accumulate(v.begin(), m, 0);
		}
	case ']':
		return 0;
	default:
		ungetc(c, stdin);
		scanf("%d", &c);
		return c / 2 + 1;
	}
}

int main() {
	for (int n = in(); n--; gcu())
		outl(elect());
}


Measured memory_bytes: 2644
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int long long int
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(), (x).end()
#define capi(x) int x;cin>>x
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using vi = vector<int>;

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

#define P (1'000'000'007)

int dp[3003][3003] = {0};

signed main() {
    capi(n);
    vi vh;

    rep(i, n) {
        capi(h);
        vh.push_back(h);
    }

    vi dp(n, INT_MAX);

    dp[0] = 0;

    rep(i, n) {
        chmin(dp[i + 1], dp[i] + abs(vh[i] - vh[i + 1]));
        if (i - 1 >= 0) {
            chmin(dp[i + 1], dp[i - 1] + abs(vh[i - 1] - vh[i + 1]));
        }
    }

    cout << dp[n - 1];

    return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    int b[n];
    int c[n-1];
    for(int i = 0; i < n; i++){
        cin >>a[i];
    }
    for(int i = 0; i < n; i++){
        cin >>b[i];
    }
    for(int i = 0; i < n-1; i++){
        cin >>c[i];
    }
    int ans = 0;
    int tmp = -10;
    for(int i = 0; i < n; i++){
        ans += b[a[i] - 1];
        if(a[i] - tmp == 1){
            ans += c[tmp-1];
        }
        tmp = a[i];
    }
    cout << ans <<endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int A = Integer.parseInt(scanner.next());
        int B = Integer.parseInt(scanner.next());
        System.out.println(A / (double) B);
    }
}



Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define kika "kika"
#define tam 10
#define mod (long long)(1e09) + 7LL
#define ll long long
#define ii pair <int, int>
#define dl pair <ll, ll>
#define vi vector <int>
#define vl vector <ll>
#define vii vector <ii>
#define graph vector <vi>

using namespace std;

int n;
int a[tam];
int b[tam];
int temp[tam];
int x, y;
int cont;
int mask;

void per(int in) {
	if (in == n) {
		bool band = true;
		for (int i = 0; i < n; ++i)
		{
			if (temp[i] != a[i]) {
				band = false;
				break;
			}
		}
		if (band) x = cont;
			band = true;
			for (int i = 0; i < n; ++i)
			{
				if (temp[i] != b[i]) {band = false; break;}
			}
			if (band) y = cont;
		cont++;
		return;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (mask & (1 << i)) continue;
		temp[in] = i;
		mask |= (1 << i);
		per(in + 1);
		mask &= ~(1 << i);
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i)
	{
		cin >> b[i];
	}
	cont = 1;
	per(0);
	cout << abs(x - y) << "\n";
	return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
ans = [1] * n
for i in range(m):
    if (h[a[i] - 1] == h[b[i] - 1]):
        ans[a[i] - 1] = 0
        ans[b[i] - 1] = 0
    elif (h[a[i] - 1] > h[b[i] - 1]):
        ans[b[i] - 1] = 0
    else:
        ans[a[i] - 1] = 0

result = sum(i == 1 for i in ans)
print(result)

Measured memory_bytes: 66984
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main() {
    int a, p; cin >> a >> p;
    int ans = (a * 3 + p) / 2;
    cout << ans << endl;
	return 0;
} 

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

using namespace std;


int vacationcost(vector<vector<int>> &arr,int day,int activity,vector<vector<int>> &dp){
    if(day==arr.size()){
        return 0;
    }

    if(dp[day][activity]!= -1){
        return dp[day][activity];
    }

    if(activity==0){
     dp[day][activity] =  max(arr[day][1] + vacationcost(arr,day+1,1,dp),max(arr[day][2] + vacationcost(arr,day+1,2,dp),arr[day][3] + vacationcost(arr,day+1,3,dp)));
    }
    else if(activity==1){
        dp[day][activity] = max(arr[day][2] + vacationcost(arr,day+1,2,dp),arr[day][3] + vacationcost(arr,day+1,3,dp));
    }
    else if(activity==2){
        dp[day][activity] = max(arr[day][1] + vacationcost(arr,day+1,1,dp),arr[day][3] + vacationcost(arr,day+1,3,dp));
    }
    else{
    dp[day][activity] =  max(arr[day][1] + vacationcost(arr,day+1,1,dp),arr[day][2] + vacationcost(arr,day+1,2,dp));
    }

    return dp[day][activity];
}

int main(){

int n;
cin>>n;
vector<vector<int>> arr(n+1,vector<int>(4,0));
vector<vector<int>> dp(n+1,vector<int>(4,-1));
for(int i=1;i<=n;i++){
    cin>>arr[i][1]>>arr[i][2]>>arr[i][3];
}

cout<<vacationcost(arr,1,0,dp)<<"\n";


return 0;
}


Measured memory_bytes: 18944
/**
*    created: 11.07.2020 21:03:46
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;




signed main() {

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

    int n; cin >> n;
    int vec[MAX];

    rep2(i,1,101) rep2(j,1,101) rep2(k,1,101) {
        int t = ((i+j)*(i+j) + (k+j)*(k+j) + (k+i)*(k+i))/2;
        if (t <= 10000) vec[t]++;
    }
    rep2(i,1,n+1) cout << vec[i] << endl;
    return 0;
}


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

using namespace std;

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

    vector<int> l(m);
    vector<int> r(m);

    for(int i = 0; i < m; i++) {
        cin >> l.at(i) >> r.at(i);
    }
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());

    int lmax = l[m-1];
    int rmin = r[0];

    if(rmin >= lmax){
        cout << rmin - lmax + 1 << endl;
    }
    else{
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main  {
    public static void main(String[] args)throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(input.readLine());
        int a = Integer.parseInt(tokenizer.nextToken());
        int b = Integer.parseInt(tokenizer.nextToken());
        int c = Integer.parseInt(tokenizer.nextToken());
        if (c >= a &&  c <= b)
            System.out.println("Yes");
        else
            System.out.println("No");
    }

}


Measured memory_bytes: 22356
n, m = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(m)]
ans = -1
if n == 1:
    i = 0
else:
    i = 10**(n-1)
while (ans == -1) & (i < 10**n):
    s = 0
    for j in lis:
        if str(i)[j[0]-1] == str(j[1]):
            s += 1
        else:
            s += 0
    if s == m:
        ans = i
    else:
        i += 1
print(ans)

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

struct Node{
	int parent, left, right;
};

void preorder(Node T[], int root){
	//cout<<" "<<root;
	//if(T[root].left==-1 && T[root].right==-1)
	if(root==-1)
		return ;
	cout<<" "<<root;
	preorder(T, T[root].left);
	preorder(T, T[root].right);
}

void inorder(Node T[], int root){
	//while(T[l].left!=-1)
		//root=T[root].left;
	if(root==-1)
		return ;
	inorder(T, T[root].left);
	cout<<" "<<root;
	inorder(T, T[root].right);
}

void postorder(Node T[], int root){
	if(root==-1)
		return;
	postorder(T, T[root].left);
	postorder(T, T[root].right);
	cout<<" "<<root;
}

int main(){
	int n;
	cin>>n;
	Node T[n];
	for(int i=0; i<n; i++){
		T[i].parent=-1;
		T[i].left=-1;
		T[i].right=-1;
	}
	for(int i=0; i<n; i++){
		int node, l, r;
		cin>>node>>l>>r;
		T[node].left=l;
		T[node].right=r;
		if(l!=-1)
			T[l].parent=node;
		if(r!=-1)
			T[r].parent=node;
	}
	int root;
	for(root=0; root<n; root++)
		if(T[root].parent==-1)
			break;
	cout<<"Preorder"<<endl;
	preorder(T, root);
	cout<<endl<<"Inorder"<<endl;
	inorder(T, root);
	cout<<endl<<"Postorder"<<endl;
	postorder(T, root);
	cout<<endl;
	return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n, k, i, j, *h, *c, r;
  cin >> n >> k;
  h = new int[n];
  c = new int[n];
  for(i = 0; i < n; i++)
  {
    cin >> h[i];
  }
  c[n - 1] = 0;
  for(i = n - 2; i >= 0; i--)
  {
    r = INT_MAX;
    for(j = i + 1; j <= i + k && j < n; j++)
    {
      r = min(r, abs(h[j] - h[i]) + c[j]);
    }
    c[i] = r;
  }
  cout << c[0] << endl;
  return 0;
}

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

//#define Saiyan

using namespace std;

template< class t>
long long int gcd( t g,t h )
{
    return ( h==0 ? g : gcd(h,g%h) );
}

int main()
{
    #ifdef Saiyan
  freopen("inp.txt","r",stdin) ;
  freopen("out.txt","w",stdout) ;
  #endif
  ios_base::sync_with_stdio(false) ; cin.tie(0) ;
  
    long long int i,j,k,ans=0,a[100005],n,l=0,c=0,af[100005]={0},ab[100005]={0},ar[100005]={0};
    
    cin>>n;
    
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    
    if(n==1)
    {
        cout<<"1";
        return 0;
    }
    

    for(i=0;i<n;i++)
    {
        if(a[i]==a[i+1]&&(i<n-1))
        {
            while(a[i]==a[i+1]&&(i<n-1))
            {
               
                i++;
            }
        }
        
        if(a[i]>a[i+1]&&(i<n-1))
        {
            while(a[i]>=a[i+1]&&(i<n-1))
            {
               
                i++;
            }
        }
        else if(a[i]<a[i+1]&&(i<n-1))
        {
            while(a[i]<=a[i+1]&&(i<n-1))
            {
               
                i++;
            }
        }
        ans++;
        //cout<<ans<<" "<<i+1<<endl;
    }
    
    cout<<ans;

	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

void insertionSort(int A[],int N){
  int v,k,i,j;
  for(i=0;i<N;i++){
    v = A[i];
    j = i - 1;
    while(j>=0&&A[j]>v){
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;
    for(k=0;k<N;k++){
      printf("%d",A[k]);
      if(k!=N-1) printf(" ");

    }
    printf("\n");
  }
  
  
}


int main(void){
  int i,v,n;
  int a[100];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  insertionSort(a,n);
  return(0);
}

Measured memory_bytes: 1820
def inpl():
    return list(map(int, input().split()))


N, M = inpl()
X = inpl()

if N >= M:
    print(0)
    exit()

X.sort()
absX = [0] * (M - 1)
for i, xx in enumerate(zip(X, X[1:])):
    absX[i] = xx[1] - xx[0]
absX.sort(reverse=True)
# print(absX)
print(sum(absX[N - 1:]))


Measured memory_bytes: 13960
#include <iostream>
#include <string>
#include <algorithm>
//#include <cassert>
//#include <array>
//#include <queue>
//#include <stack>
//#include <vector>
//#include <map>
//#include <set>
#include <unordered_map>
#include <unordered_set>

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

using namespace std;

string S, T;

void solve() {
	cin >> S >> T;
	unordered_map<char, char> um;
	unordered_set<char> us;


	bool is_possible;
	is_possible = true;
	REP(i, S.size()) {
		if (um.find(S.at(i)) != um.end()) {
			if (um.at(S.at(i)) == T.at(i)) {
				continue;
			}
			else {
				is_possible = false;
				break;
			}
		}
		else {
			if (us.insert(T.at(i)).second) {
				um[S.at(i)] = T.at(i);
			}
			else {
				is_possible = false;
				break;
			}
		}
	}

	string ans;
	if (is_possible) {
		ans = "Yes";
	}
	else {
		ans = "No";
	}
	cout << ans << endl;
	return;
}

int main() {
	solve();
	return 0;
}

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

#define ll long long
#define mii make_pair<int, int>
#define mll make_pair<ll, ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define all(v) (v).begin(), (v).end()

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

    double pi = 3.14159265358979323846;
    int r;
    cin >> r;
    printf("%.4lf", 2 * pi * r);
}

Measured memory_bytes: 3784
n = int(input())
a = list(map(int, input().split()))
dp = [[float("inf")] * n for _ in range(n)]
s = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i - 1]
for i in range(n):
    dp[i][i] = 0

for w in range(1, n):
    for i in range(n - w):
        for j in range(i, i + w):
            dp[i][i + w] = min(dp[i][i + w], dp[i][j] + dp[j + 1][i + w] + s[i + w + 1] - s[i])
print(dp[0][n - 1]) 


Measured memory_bytes: 47252
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>

long table[2020][2020];

int main()
{
    long long L,R;
    for(long i=0; i<=2019; i++){
        for(long j=0; j<=2019;j++){
            table[i][j]=(i*j)%2019;
        }
    }

    std::cin >> L >> R;
    bool flag=0;
    if(L/2019!=R/2019){
        flag=1;
    }
    L=L%2019;
    R=R%2019;
    long temp=std::min(L,R);
    long temp2=std::max(L,R);
    L=temp;
    R=temp2;
    if(flag){
        L=0;
    }
    long result=2020;
    for(long i=L;i<=R; i++){
        for(long j=i+1; j<=R; j++){
            if(table[i][j]<result){
                result=table[i][j];
            }
        }
    }
    std::cout << result << std::endl;
    return 0;
}

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

typedef long long ll;

ll dp[1000][2];

int a[1000];

int main() {
  int n;
  
  cin >> n;
  
  for ( int i = 1 ; i <= n ; i++ )
    cin >> a[i];
  
  
  dp[0][1] = 1;
  dp[0][0] = 0;
  
  for ( int i = 1 ; i <= n ; i++ ) {
    
    for ( int j = a[i]-1 ; j <= a[i]+1 ; j++ ) {
      dp[i][ 1 * ( j % 2 ) ] += dp[i-1][1];
      dp[i][ 0 * ( j % 2 ) ] += dp[i-1][0];
    }
    
  }
  
  
  cout << dp[n][0] << endl;
  
  return 0;
}


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

int main(){

  int a[1111], b[1111], c[1111], d[1111], p[333];
  
  while(cin >> a[0] >> b[0] >> c[0], *a+=*b+*c){
    for(int i=332;i;) p[i--] = 2;
    
    cin >> p[0];
    for(int i=0;i++<*p;) cin >> a[i] >> b[i] >> c[i] >> d[i];
    
    for(int i=0;i++<*p;){
      for(int j=0;j++<*p;){
	if(d[j]) p[a[j]] = p[b[j]] = p[c[j]] = 1;
	else{
	  if(p[a[j]] == 1 && p[b[j]] == 1) p[c[j]] = 0;
	  if(p[a[j]] == 1 && p[c[j]] == 1) p[b[j]] = 0;
	  if(p[b[j]] == 1 && p[c[j]] == 1) p[a[j]] = 0;
	}
      }
    }
    for(int i=0;i<*a;) cout << p[++i] << endl;
  }
  
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
using P = pair<int, int>; 
using ll = long long;

int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if((abs(a - b) <= d && abs(b - c) <= d) || abs(a - c) <= d) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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


typedef long long ll;
typedef vector<int> vec;
//配列の添字ズレに注意
//=に注意

int vector_finder(vector<int> v, int number) {
  auto itr =find(v.begin(), v.end(), number);
  size_t index =distance( v.begin(), itr );
  if(index != v.size()){//発見できたとき
    return 1;}
  else {//発見できなかったとき
    return 0;}
}


int main(){
  int x,n,memo=10000,ans; cin>>x>>n;
  vec p(n);
  rep(i,n) cin>>p[i];
  
  //sort(p.begin(), p.end());
  
  for(int i=-2;i<109;i++){
    if(vector_finder(p,i)==0){
      if(memo>abs(i-x)){memo=abs(i-x);ans=i;}
    }
  }
  

  cout<<ans<<endl;
}

Measured memory_bytes: 3628
min_r = 0
profit = 0

n = int(input())
for i in range(n):
    r = int(input())
    if i == 0:
        min_r = r
    elif i == 1:
        profit = r - min_r
    else:
        profit = max(profit, r - min_r)
    min_r = min(min_r, r)
print(profit)



Measured memory_bytes: 5612
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	ll n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	bool appear=false;
	for(int k=0; k<n; k++){
		if((n-1-k)*c-k*d<=b-a && b-a<=(n-1-k)*d-k*c) appear=true;
	}
	if(appear) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
a, b = map(int, input().split())
a_min = int(a / 0.080 + 0.9)
a_max = int((a + 0.9) / 0.080)
b_min = int(b / 0.100 + 0.9)
b_max = int((b + 0.9) / 0.100)
if a_max < b_min or b_max < a_min:
    ans = -1
elif a_min <= b_min:
    ans = b_min
elif b_min <= a_min:
    ans = a_min
print(ans)

Measured memory_bytes: 3064
x,n = map(int,input().split())
sw = 1
if n == 0:
    sw = 0
    ans = x
else:
    p = list(map(int,input().split()))
    y1 = x
    y2 = x
    ans = 0
    for i in range(n):
        if y1 in p and not(y2 in p):
            ans = y2
            break
        elif y2 in p and not(y1 in p) :
            ans = y1
            break
        elif y1 in p and y2 in p:
            y1 -= 1
            y2 += 1
        else:
            ans = min(y1,y2)
            break
print(ans)

Measured memory_bytes: 9212
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
m,d=MI()
M,D=MI()
if m!=M:
    print(1)
else:
    print(0)
        
        
    
    
        
    
    


Measured memory_bytes: 65560
#include<stdio.h>

int max(int a, int b);

int main(void){

  int a=0, b=0, c=0;
  int x=0, y=0;
  int sum=0, min=0;
  int i=0, k=0;
  
  scanf("%d %d %d %d %d", &a, &b, &c, &x, &y);
  
  if(x>=y){
    for(k=0; k<=x; k++){
      sum=2*c*k+max(x-k, 0)*a+max(y-k, 0)*b;
      if(k==0)
	min=sum;
      if(min>sum)
	min=sum;
    }
  }
  else{
    for(k=0; k<=y; k++){
      sum=2*c*k+max(x-k, 0)*a+max(y-k, 0)*b;
      if(k==0)
	min=sum;
      if(min>sum)
	min=sum;
    }
  }
  printf("%d\n", min);
  
  return 0;
  
}



int max(int a, int b){

  int max=0;
  if(a>=b)
    max=a;
  else
    max=b;

  return max;
}


Measured memory_bytes: 128
//#include<bits/stdc++.h>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
typedef long double ldb;
#define rep(i,a,b) for(i=a;i<b;i++)
#define repu(i,a,b) for(i=a;i<=b;i++)
#define repd(i,a,b) for(i=a;i>=b;i--)
#define repc(i,a,b,c) for(i=a;i<b;i+=c)
#define repcu(i,a,b,c) for(i=a;i<=b;i+=c)
#define repcd(i,a,b,c) for(i=a;i>=b;i-=c)
#define FIN freopen("input.in","r",stdin)
#define FOUT freopen("output.out","w",stdout)
#define CC(a) memset(a,0,sizeof(a))
#define MST(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define VI vector<int>
#define VL vector<long long>
#define VII vector<PII>
#define VLL vector<PLL>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
 
template<typename T>inline void gn(T &x){
	x=0;T f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
template<typename T>inline void gt(T x){
	if(!x)return;
	gt(x/10);putchar(x%10+'0');
}
 
const LL maxn=1e3+10;
LL MOD=1e9+7,inf=0x1f1f1f1f,mod=998244353;
db eps=1e-5;
LL t,n,m,q,ans,cnt[11];

int main()
{
//	ios_base::sync_with_stdio(false);cin.tie(0);
	LL i,j,k,l,ca=0,u,v;
	cin>>n>>m>>q;
	ans=(n+m)*q/2;
	cout<<ans<<endl;
	return 0;
}

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

#define debug(x) cout<<#x<<": "<<x<<endl
#define rep(i,a,b) for(int i=a;i<b;i++)
#define PB push_back
typedef long long ll;

int main(){
	string s;
	cin>>s;
	cin>>s;
	cout<<"A"<<s[0]<<"C"<<endl;



	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <utility> //pair

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

typedef long long ll;

using namespace std;

int main() {
    
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int x,y;
    x=x2-x1;
    y=y2-y1;
    
    int x3,y3,x4,y4;
    x3 = x2-y;
    y3 = y2+x;
    x4 = x3-x;
    y4 = y3-y;
    
    cout << x3 << endl;
    cout << y3 << endl;
    cout << x4 << endl;
    cout << y4 << endl;
    
    return 0;
}


Measured memory_bytes: 256