akhauriyash/Code-Regression huggingface dataset:
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, W, *WV = map(int, read().split())
    weight = WV[::2]
    value = WV[1::2]

    w0 = weight[0]
    items = [[] for _ in range(4)]
    for w, v in zip(weight, value):
        items[w - w0].append(v)

    for i in range(4):
        items[i].sort(reverse=True)

    csums = [0] * 4
    for i in range(4):
        csums[i] = [0]
        csums[i].extend(accumulate(items[i]))

    def rec(i, w, v):
        if i == 4:
            return v
        ans = 0
        w_next = w
        for j in range(len(csums[i])):
            if w_next > W:
                break
            ans = max(ans, rec(i + 1, w_next, v + csums[i][j]))
            w_next += w0 + i

        return ans

    print(rec(0, 0, 0))
    return


if __name__ == '__main__':
    main()


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

int main(){
	int A, B ,C ,K, ans;
	cin >> A >> B >> C >>K;
	
	int xa;
	xa = min(A, K);
	
	int K1 = K - xa;
	int xb = min(K1, B);
	int K2 = K1 - xb;
	int xc = K2;
	
	ans = 1*xa + (-1)*xc;
	cout << ans << endl;
	return 0;
	
}

Measured memory_bytes: 3612
N, W = map(int, input().split())
goods = []
for _ in range(N):
    goods.append(tuple(map(int, input().split())))

table = [[0] * (W + 1) for _ in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        addn = table[n][w - goods[n][0]] + goods[n][1] if w - goods[n][0] >= 0 else 0
        table[n + 1][w] = max(table[n][w], addn)
print(table[N][W])


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

int main(void){

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

	int mini;
	int count = 0;
	for (int i = 0; i < n - 1; i++){

		mini = i;
		for (int j = i; j < n; j++){
			if (a[j] < a[mini])
				mini = j;
		}

		if (i != mini){
			swap(a[i], a[mini]);
			count++;
		}
	}

	for (int i = 0; i < n - 1; i++)
		cout << a[i] << ' ';
	cout << a[n - 1] << endl << count << endl;
}

Measured memory_bytes: 1160
import sys
readline = sys.stdin.buffer.readline

n,a,b = map(int,readline().split())
mod = 10**9+7


def pow(n, p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def large_conbination(n,k,mod=10**9+7): #needs pow method. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
        res1%=mod
    res2 = 1
    for i in range(1,k+1):
        res2*= i
        res2%=mod
    return res1*pow(res2,mod-2)%mod

ans = pow(2,n)-1

ans -= large_conbination(n,a)
ans -= large_conbination(n,b)

while ans < 0:
    ans += mod

print(ans)

Measured memory_bytes: 38768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main(){
  ll n, m;
  cin >> n >> m;
  vector<bool> onei(n, false);
  vector<bool> iton(n, false);
  for(ll i=0;i<m;i++){
    ll a, b;
    cin >> a >> b;
    a--, b--;
    if (a == 0){
      onei[b] = true;
    }
    if (b == n-1){
      iton[a] = true;
    }
  }
  for(ll i=1;i<n;i++){
    if (onei[i]){
      if(iton[i]){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 256
def sum_left(n):
    return int(n*(n+1)/2)

def sum_right(n,k):
    return int(n*(n+1)/2 - (n-k)*(n-k+1)/2)

N, K = map(int, input().split())

mod = 10**9+7

cnt = 0
for i in range(K, N+2):
    cnt = (cnt - sum_left(i) +sum_right(N+1, i) + 1) % mod

print(cnt)


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30 - 1)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> A >> S;
    B = (S[0] - '0') * 100 + (S[2] - '0') * 10 + (S[3] - '0');
    dump(B);
    cout << (A * B) / 100L << endl;
}

Measured memory_bytes: 3624
from math import factorial
import collections

N = int(input())
A = input().split()
A = [int(x) for x in A]

L = collections.Counter(A)

c = 0
for i in range(1,N+1):
    n = L[i]
    if n >=2:
        c += factorial(n) // factorial(2) // factorial(n - 2)

for k in range(N):
    c1 = c
    n = L[A[k]]
    if n >= 3:
        c1 -= n-1
    elif n == 2:
        c1 -= factorial(n) // factorial(2) // factorial(n-2)
    print(c1)

Measured memory_bytes: 26772
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
using namespace std;
int main(){
  int a,b,k,i;
  scanf("%d\n%d %d\n",&k,&a,&b);
  for(i=a;i<=b;i++){
    if(i%k==0){
      printf("OK\n");
      return 0;
    }
  }
  printf("NG\n");
  return 0;
}

Measured memory_bytes: 3804
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>

#define AS(a) (sizeof(a)/sizeof(a[0]))
using namespace std;
long long int MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long int ans_1 = 0;
  long long int sum = 0;
  sum = a[0];
  if(a[0] <= 0) {
    ans_1 = -a[0] + 1;
    sum = 1;
  }
  for(int i = 1; i < n; i++) {
    if(sum > 0) {
      sum += a[i];
      if(sum >= 0) {
        ans_1 += sum + 1;
        sum = -1;
      }
    } else {
      sum += a[i];
      if(sum <= 0) {
        ans_1 += -(sum) + 1;
        sum = 1;
      }
    }
  }
  long long int ans_2 = 0;
  sum = 0;
  sum = a[0];
  if(a[0] >= 0) {
    ans_2 = a[0] + 1;
    sum = -1;
  }
  for(int i = 1; i < n; i++) {
    if(sum > 0) {
      sum += a[i];
      if(sum >= 0) {
        ans_2 += sum + 1;
        sum = -1;
      }
    } else {
      sum += a[i];
      if(sum <= 0) {
        ans_2 += -(sum) + 1;
        sum = 1;
      }
    }
  }



  cout << min(ans_1,ans_2) << endl;
}


Measured memory_bytes: 640
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>

#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 12;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    string s;
    cin >> s;
    for(ll i=0;i<s.size();i++)
    {
        if(s[i]=='?')  s[i] = 'D';
    }
    cout<<s;
}

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

Measured memory_bytes: 3736
#include<bits/stdc++.h>
#define fori(j,n) for(ll i=j;i<n;i++)
#define forb(n,j) for(ll i=n-1;i>=0;i--)
#define endl "\n"
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define vec vector<int>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll sgn(ll x){
    if(x>0)
        return 1;
    if(x==0)
        return 0;
    return -1;
}
//const ll N = 2e5 + 5;
int32_t main()
{
    IOS;
    ll n;
    cin>>n;
    cout<<(n+(n*n)+(n*n*n));
    return 0;
}




Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using vi = vector<int>;

#define in(v) v; cin >> v;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rrep(i,n) for(long long i=(n);i>=0;--i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

// ========== debug ==========
template<class T>ostream& operator<<(ostream& os,const vector<T>& vec){os<<"{";for(size_t i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
ostream& operator<<(ostream& os,const vector<char>&v){for(size_t i=0;i<v.size();++i)os<<v[i];return os;}
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>& rhs){os<<"("<<rhs.first<<", "<<rhs.second<<")";return os;}

#ifdef LOCAL
void debug() {cerr << "\n";}
template<class First> void debug(const First& first) {cerr<<first<<"\n";}
template<class First, class... Rest> void debug(const First& first, const Rest&... rest) {cerr<<first<<",";debug(rest...);}
void debug2() {cerr << "\n";}
template<class First> void debug2(const First& first) {cerr<<first<<" ";}
template<class First, class... Rest> void debug2(const First& first, const Rest&... rest) {cerr<<first<<" ";debug2(rest...);}
#else
#define debug(...) 42
#define debug2(...) 42
#endif
// ===========================

int main() {
  int D;
  ins(D);

  vi c(26);
  vector<vi> s(D, vi(26));
  rep(i, 26) cin >> c[i];

  rep(i, D) {
    rep(j, 26)
      cin >> s[i][j];
  }

  rep(i, D) {
    cout << 1 << endl;
  }

  return 0;
}


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


using namespace std;


const int MOD = 1e9 + 7;
const int N = 1e5;
const long long INF = 1e9;


int main() {
  	int n;
  	cin >> n;
  	pair<int, int> a[n];
  	for (int i = 0; i < n; i++) {
    	cin >> a[i].first;
      	a[i].second = i + 1;
    }
  	sort(a, a + n);
  	for (auto x : a)
    	cout << x.second << ' ';  	
}


Measured memory_bytes: 1536
n = int(input())
ab = [list(map(int,input().split())) for i in range(n)]

ab.sort(key= lambda x:x[1],reverse = True)
time = ab[0][1]

for i in range(n):
    if time > ab[i][1]:
        time = ab[i][1]
    time -= ab[i][0]
else:
    if time >= 0:
        ans = "Yes"
    else:
        ans = "No"

print(ans)

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init));

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  ll n;
  cin >> s >>n;
  ll cnt = 0;
  rep(i,n){
    string s2;
    cin >> s2;
    s2 += s2;
    if(s2.find(s) != string::npos) ++cnt;
  }
  cout << cnt << endl;
  return 0;
}

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

int main()
{
    int n, a , b;

    cin>>n>>a>>b;

    int x = b - a;

    if(x == 0) cout<<"Draw"<<endl;
    if(x%2==0) cout<<"Alice"<<endl;
    else cout<<"Borys"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N;

struct matrix {
	long long M[100][100] = {{0}};

	inline matrix operator* (matrix A) {
		int i, j, k;
		matrix B;
		for (i=0; i<N; i++)
			for (j=0; j<N; j++)
				for (k=0; k<N; k++) {
					B.M[i][j] += M[i][k] * A.M[k][j];
					B.M[i][j] %= 1000000007;
				}
		return B;
	}

	inline matrix operator*= (matrix A) {
		*this = *this * A;
		return *this;
	}
};

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

	long long K;
	while (cin >> N >> K) {
		matrix A, B;

		for (int i=0; i<N; i++)
			for (int j=0; j<N; j++)
				cin >> A.M[i][j];

		for (int i=0; i<N; i++)
			B.M[i][i] = 1;

		while (K) {
			if (K&1)
				B *= A;
			K >>= 1;
			A *= A;
		}

		long long sum = 0;

		for (int i=0; i<N; i++)
			for (int j=0; j<N; j++)
				sum += B.M[i][j];
		sum %= 1000000007;

		cout << sum << '\n';
	}
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  set<int> a;
  for(int i=0;i<n;i++){
    int x;
    cin >> x;
    a.insert(x);
  }
  if (n == a.size()) cout << "YES" << endl;
  else cout << "NO" << endl;
  
}


Measured memory_bytes: 9600
H,W=[int(x) for x in str(input()).split()]
R=[]
A=[[0 for i in range(W+2)]]
for i in range(H):
  b=str(input())
  c=[0]
  d=[]
  for j in range(W): 
    
    d.append(b[j])
    if b[j]=='.':
      c.append(0)
    else:
      c.append(1)

  c.append(0)
  A.append(c)
  R.append(d)
A.append([0 for i in range(W+2)])

for i in range(0,H):
  for j in range(0+W):
    if R[i][j]=='.':

      R[i][j]=(A[i][j]+A[i][j+1]+A[i][j+2]+A[i+1][j]+A[i+1][j+2]+A[i+2][j]+A[i+2][j+1]+A[i+2][j+2])

for i in R:
  s=''
  for j in range(W):
    s+=str(i[j])
  print(s)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;}


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

int N;
string S;
cin >> N >> S;

i64 ans = 0;

VI R(N, 0), G(N, 0), B(N, 0);
Rrep(i, N-1, 1){
    if (S[i] == 'R') ++R[i];
    else if (S[i] == 'G') ++G[i];
    else if (S[i] == 'B') ++B[i];
    R[i-1] += R[i];
    B[i-1] += B[i];
    G[i-1] += G[i];
}

rep(i, 0, N) rep(j, i+1, N-1) if(S[i] != S[j]){
    set<char> C = {'R', 'G', 'B'};
    C.erase(S[i]);
    C.erase(S[j]);
    char c = *C.begin();
    if (c == 'R') ans += R[j+1];
    else if (c == 'G') ans += G[j+1];
    else if (c == 'B') ans += B[j+1];
    if (2*j -i < N && S[2*j - i] == c) --ans;
}

cout << ans << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
    for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
   }
   sort(vec.begin(), vec.end());

  int flagggg = 0;

  for (int i = 1; i < N; i++) {
    if (vec.at(i-1) == vec.at(i) && flagggg == 0) {
        flagggg++;
        break;
    }
  }

  if (flagggg ==0) {
    cout << "YES" << endl;
  }
  else if (flagggg == 1) {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 1024
n, l = [ int(v) for v in input().split() ]
knot_list = [ int(v) for v in input().split() ]

pos = 0
for i in range(1,n):
    if knot_list[i-1] + knot_list[i] >= l:
        pos = i
        break
if pos == 0:
    print("Impossible")
else:
    print("Possible")
    for i in range(1,pos):
        print(i)
    for i in range(n-1,pos-1,-1):
        print(i)

Measured memory_bytes: 63984
A, B = map(int, input().split())
T = [["#"] * 100 for i in range(100)]
for i in range(50, 100):
    T[i] = ["."] * 100

A -= 1
for i in range(50):
    if A == 0:
        break
    if i % 2 == 0:
        for j in range(100):
            if j % 2 == 0:
                T[i][j] = "."
                A -= 1
                if A == 0:
                    break

B -= 1
for i in range(51, 100):
    if B == 0:
        break
    if i % 2 != 0:
        for j in range(100):
            if j % 2 == 0:
                T[i][j] = "#"
                B -= 1
                if B == 0:
                    break

print(100, 100)
for i in range(100):
    print("".join(T[i]))

Measured memory_bytes: 3188
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define ind(a) scanf("%lf", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//def   puts(a) printf("%s\n", a) 文字はこっち
//your code here!


int main(void){
    ll N, D, X, A[101];
    in(N); in(D); in(X);
    rep(i,N) in(A[i]);
    rep(i,N){
        ll j=0;
        while(1+A[i]*(j++)<=D) X++;
    }
    put(X);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <stack>
#define LL long long
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    int l=b-a;
    cout<<(1LL+l)*l/2-b<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::string S, T;
    std::cin >> S >> T;
    const int M = S.size(), N = T.size();
    std::vector<std::vector<int>> snext(26, std::vector<int>(M, -1));
    for (char c = 'a'; c <= 'z'; c++) {
        int next = M;
        for (int i = M - 1; i >= 0; i--) {
            if (S[i] == c) { next = i; }
            snext[c - 'a'][i] = next;
        }
    }
    std::vector<std::vector<int>> tnext(26, std::vector<int>(N, -1));
    for (char c = 'a'; c <= 'z'; c++) {
        int next = N;
        for (int i = N - 1; i >= 0; i--) {
            if (T[i] == c) { next = i; }
            tnext[c - 'a'][i] = next;
        }
    }

    std::vector<std::vector<int>> memo(M + 2, std::vector<int>(N + 2, -1));
    using P = std::pair<int, int>;
    std::vector<std::vector<P>> Next(M + 2, std::vector<P>(N + 2));
    auto dp = [&, M, N](auto&& self, const int s, const int t) -> int {
        if (s >= M or t >= N) { return 0; }
        if (memo[s][t] != -1) { return memo[s][t]; }
        int ans = 0;
        P next = {-1, -1};
        for (char c = 'a'; c <= 'z'; c++) {
            int ns = snext[c - 'a'][s], nt = tnext[c - 'a'][t];
            const int sub = self(self, ns + 1, nt + 1) + (ns < M and nt < N);
            if (ans < sub) { ans = sub, next = {ns + 1, nt + 1}; }
        }
        return Next[s][t] = next, memo[s][t] = ans;
    };
    const int L = dp(dp, 0, 0);
    int s = 0, t = 0;
    std::string ans;
    for (int i = 0; i < L; i++) {
        const auto next = Next[s][t];
        s = next.first, t = next.second;
        ans.push_back(S[s - 1]);
    }
    std::cout << ans << std::endl;
    return 0;
}


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

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

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const double PI = 3.1415926535;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    vector<int>water, suger;
    for(int i=0; i*100*a<=f; i++){
        for(int j=0; i*a*100+j*b*100<=f; j++){
            if(i==0&&j==0)continue;
            water.push_back(i*a*100+j*b*100);
        }
    }
    for(int i=0; i*c<=f; i++){
        for(int j=0; i*c+j*d<=f; j++){
            suger.push_back(i*c+j*d);
        }
    }
    water.erase(unique(water.begin(),water.end()),water.end());
    suger.erase(unique(suger.begin(),suger.end()),suger.end());
    int n = water.size();
    int m = suger.size();
    double ans = 0;
    int res1 = 100*a, res2 = 0;
    rep(i, 0, n){
        rep(j, 0, m){
            if(water[i]+suger[j]>f)continue;
            double temp = ans;
            if(suger[j]<=water[i]/100*e){
                temp = (double)(100*suger[j])/(suger[j]+water[i]);
                if(temp>ans){
                    res1 = suger[j]+water[i];
                    res2 = suger[j];
                    ans = temp;
                }
            }
        }
    }
    cout << res1 << " " << res2 << endl;
}

Measured memory_bytes: 4164
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int area = x * y;
        int length = ( x + y ) * 2;
        System.out.println( area + " " + length );
    }
}

Measured memory_bytes: 26264
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x, y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x, y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=1e9+7;
const ll maxn=1e5+10;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
ll random(ll mn, ll mx){
	return (rand() % (mx - mn + 1)) + mn; 
}
vector<ll> adj[maxn];
vector<ll> deg(maxn, 0);
vector<ll> ans(maxn);

void solve(){
	
	ll k,n;
	cin>>k>>n;
	ll a[n+1];
	for (int i=1;i<=n;i++) cin>>a[i];
	
	
	
	ll ans=a[n]-a[1];
	for (int i=1;i<n;i++){
		ans=min(ans, (k-(a[i+1]-a[i])));
	}
	cout<<ans<<endl;
	
	return ;
	
}

int main(){ 
    
    #ifndef ONLINE_JUDGE
  	//	freopen("input.txt", "r", stdin);
    #endif
    srand(time(0)); 
    
    ios::sync_with_stdio(0);
    cin.tie(0);

	//T{ solve(); }
	solve();
	
	
	
	return 0;
}

Measured memory_bytes: 5760
package main

import (
	"fmt"
)

func main() {
	var s string
	_, _ = fmt.Scanf("%s", &s)

	fmt.Println(answer166A(s))
}

func answer166A(s string) string {
	if s == "ABC" {
		return "ARC"
	} else {
		return "ABC"
	}
}


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

using namespace std;

int main()
{
    set<char> s;
    s.insert('A');
    s.insert('C');
    s.insert('T');
    s.insert('G');
    string ss;
    cin>>ss;
    int ans=0, cur=0;
    for(int i=0; i<ss.size(); i++){
        if(s.count(ss[i])) cur++;
        else cur=0;
        ans = max(ans, cur);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define cri const int
#define ll long long
using namespace std;
vector<int>to[52];
int is[52];
ll w[52],v[52],dp[125010];
void dfs(cri x){
	w[x]=1;
	for(int y:to[x]) dfs(y),w[x]+=w[y],v[x]+=v[y];
}
inline int as(cri x,cri y){
	return w[x]*v[y]>w[y]*v[x];
}
int main(){
	int n,X,d,sum=0;
	cin>>n>>X>>d>>v[1];is[1]=1;
	for(int i=2,x;i<=n;i++){
		cin>>v[i]>>x;is[i]=i;
		to[x].push_back(i);
	}
	dfs(1);
	sort(is+1,is+n+1,as);
	memset(dp,0x3f,sizeof dp);dp[0]=0;
	cri mn=min(d,n);
	for(int i=1;i<=n;i++){
		int lst=mn;
		for(int j=1;j<=lst;j<<=1){
			sum+=j*w[i];
			for(int k=sum;k>=j*w[i];k--) dp[k]=min(dp[k],dp[k-j*w[i]]+j*v[i]);
			lst-=j;
		}
		if(lst){
			cri j=lst;
			sum+=j*w[i];
			for(int k=sum;k>=j*w[i];k--) dp[k]=min(dp[k],dp[k-j*w[i]]+j*v[i]);
		}
	}//cout<<1<<endl;
	ll ans=0;
	for(int s=0;s<=sum;s++) if(dp[s]<=X){
		int lst=X-dp[s];ll tmp=s;
		//cout<<s<<" "<<lst<<" "<<tmp<<endl;
		for(int i=1;i<=n;i++){
			cri x=is[i],num=x==1?lst/v[x]:min((ll)d-mn,lst/v[x]);
			tmp+=num*w[x];lst-=num*v[x];
		}
		//cout<<tmp<<endl;
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4160
#include <iostream>

using namespace std;
#define pi 3.14159265

int main()
{
	long long ans = 0, i = 0, j = 0, k = 0, l = 0;
	long long X, Y;
	cin >> X >> Y;

	while (X*2 <= Y) {
		ans++;
		X = X*2;
	}

	cout << ++ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int h,w;
string g[25];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int dfs(int x, int y){
  g[y][x]='#';
  int ans=0;
  for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(0<=nx && nx<w && 0<=ny && ny < h && g[ny][nx]!='#'){
      ans+=dfs(nx,ny);
    }
  }
  return ans+1;
}

int main(void){

  while(cin >> w >> h, h|w){
    for(int i=0;i<h;i++)cin >> g[i];
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(g[i][j]=='@')cout << dfs(j,i) << endl;
      }
    }
  }
  
  return 0;
}

Measured memory_bytes: 3184
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}
ll uni[100001];
ll root(ll u){
    if(uni[u]<0)return u;
    return uni[u]=root(uni[u]);
}
void connect(int a,int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(uni[a]>uni[b]){
        a^=b;
        b^=a;
        a^=b;
    }
    uni[a]+=uni[b];
    uni[b]=a;
    return;
}
ll size(ll u){
    return -uni[root(u)];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(uni,-1,sizeof(uni));
    ll n,m,ans;
    stack<ll> s; 
    cin>>n>>m;
    ans=n*(n-1)/2;
    ll a[m],b[m];
    for(int i=m-1;i>=0;i--){
        cin>>a[i]>>b[i];
    }
    s.push(ans);
    for(int i=0;i<m-1;i++){
        if(root(a[i])==root(b[i])){
            s.push(ans);
        }
        else{
            ans-=size(a[i])*size(b[i]);
            connect(a[i],b[i]);
            s.push(ans);
        }
    }
    while(!s.empty()){
        cout << s.top()<<endl;
        s.pop();
    }
    return 0;
}





Measured memory_bytes: 4252
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,n) for(lli i=0;i<n;i++)
#define repb(i,n) for(lli i=n-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define bg() begin()
#define en() end()
#define ft first
#define sc second
#define vect_lli_it vector<lli>::iterator
#define set_lli_it set<lli>::iterator
#define inf 1e18
#define all(X) X.begin(),X.end()
#define iterate(X) for(it=X.begin();it!=X.end();it++)
lli combi(lli n,lli k)
{
    lli ans=1;
    k=k>n-k?n-k:k;
    lli j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli findlcm(vector <lli> arr, lli n)
{
    lli ans = arr[0];
    for (lli i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));

    return ans;
}
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n,m;
    cin>>n>>m;
    lli x;
    vector <lli> hei;
    rep(i,n){
    	cin>>x;
    	hei.pb(x);
	}
	lli max_hei[n+1];
	rep(i,n+1)
	max_hei[i]=0;
	lli y;
	rep(i,m){
		cin>>x>>y;
		max_hei[x]=max(max_hei[x],hei[y-1]);
		max_hei[y]=max(max_hei[y],hei[x-1]);
	}
	lli cnt=0;
	for(lli i=1;i<=n;i++){
		if(hei[i-1]>max_hei[i])
		cnt++;
	}
	cout<<cnt;
    return 0;
}


Measured memory_bytes: 5132
using System;

class MainClass
{
    public static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var d = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        Array.Sort(d);

        var x = d[d.Length - 1];
        var p = x / 2.0;
        var i = binsearch(d, p, 0, d.Length - 1);

        if (i == d.Length - 1)
        {
            Console.WriteLine($"{x} {d[i - 1]}");
        }
        else if (i == 0)
        {
            Console.WriteLine($"{x} {d[i]}");
        }
        else if (Math.Abs(d[i] - p) < Math.Abs(d[i - 1] - p))
        {
            Console.WriteLine($"{x} {d[i]}");
        }
        else
        {
            Console.WriteLine($"{x} {d[i - 1]}");
        }
    }

    static int binsearch(int[] d, double x, int l, int r)
    {
        if (l == r) return l;

        var m = (l + r) / 2;
        if (x < d[m])
        {
            return binsearch(d, x, l, m);
        }
        else
        {
            return binsearch(d, x, m + 1, r);
        }
    }
}


Measured memory_bytes: 21600
N, M = map(int, input().split())
ab=[]
for _ in range(N):
    ab.append(list(map(int, input().split())))
ab.sort()

y=d=0
for i in ab:
    y+=i[0]*i[1]
    d+=i[1]
    if(d>=M):
        print(y-(d-M)*i[0])
        exit()


Measured memory_bytes: 27760
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }


ll dp[100010];
const ll MOD = pow(10,9) + 7;

int main() {
  int N,M;
  scanf("%d%d", &N,&M);
  int a[M+1];
  for (int i = 0; i < M; ++i) {
    scanf("%d", &a[i]);
  }
  a[M] = 0;
 

  int ref = 0;

  dp[0] = 1;
  if(a[0]!=1) dp[1] = 1;
  else ++ref;

  FOR(i,2,N){
    if(a[ref]==i) {
      ++ref;
      continue;
    }

    dp[i] = (dp[i-2] + dp[i-1])%MOD;
  }

  cout << dp[N] << endl;


}



Measured memory_bytes: 1280
#include "bits/stdc++.h"

using namespace std;

static const int MAX = 100;
int n, A[2][MAX], sum[2][MAX];

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

    sum[0][0] = A[0][0];
    sum[1][n - 1] = A[1][n - 1];

    for (int i = 1; i < n; ++i) {
        sum[0][i] = sum[0][i - 1] + A[0][i];
        sum[1][n - i - 1] = sum[1][n - i] + A[1][n - i - 1];
    }

    int candy = 0;
    for (int i = 0; i < n; ++i) {
        int v = sum[0][i] + sum[1][i];
        candy = max(candy, v);
    }

    cout << candy << endl;

    return 0;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int X = int.Parse(input[0]);
            int Y = int.Parse(input[1]);
            Console.WriteLine(X + Y / 2);
        }
    }
}


Measured memory_bytes: 13140
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
    int key;
    Node *next,*prev; //ポインタ　要素をNodeとする．
};

Node *nil;

Node* listSearch(int key){ //要素を探索する．
    Node *cur = nil->next; //番兵の次の要素 現在位置の要素のポインタをcur 
    while(cur != nil && cur->key != key){ //->　…アロー演算子，a->bの時，aの構造体の中のフィールドbを指す．
        cur = cur->next; //curが番兵nilに戻ってしまうか，keyを発見すると探索は終了する
    }
    return cur; 
}

void init(){ //リストの初期化
    nil = (Node *)malloc(sizeof(Node)); //mallocは指定したサイズだけメモリを動的に確保する関数
    nil->next = nil; //ポインタ変数からメンバにアクセスするアロー演算子 ->
    nil->prev = nil;
}

void printList(){
    Node *cur = nil->next;
    int isf = 0;
    while(1){
        if(cur == nil) break;
        if(isf++ > 0)printf(" ");
        printf("%d", cur->key); 
        cur = cur->next;
    }
    printf("\n");
}

void deleteNode(Node *t){
    if(t==nil)return; //tが番兵なら処理しない
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst(){
    deleteNode(nil->next);
}

void deleteLast(){
    deleteNode(nil->prev);
}

void deletekey(int key){ //検索した要素(Node)を削除
    deleteNode(listSearch(key));//keyと同じものを探し，削除する
}

void insert(int key){
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;//番兵の直後に要素を追加
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

int main(){
    int key,n,i;
    int size = 0;
    char com[20];
    int np = 0,nd = 0;
    scanf("%d", &n);
    init();
    for(i=0;i<n;i++){
        scanf("%s%d",com,&key); //cinよりscanfの方が早い．
        if(com[0] == 'i'){
            insert(key);np++;size++;
        }else if(com[0] == 'd'){
            if(strlen(com) > 6){
                if(com[6] == 'F') deleteFirst();
                else if(com[6] == 'L')deleteLast();
            }else{
                deletekey(key);
                nd++;
            }
            size--;
        }
    }
    printList();

    return 0;
}


Measured memory_bytes: 33872
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <cmath>
#define MAX 1000000007LL
using namespace std;

typedef long long ll;

ll fact(int n) {
  ll x = 1;
  for(int i = 1; i <= n; i++) {
    x *= i;
    x %= MAX;
  }
  return x;
}

int main() {
  int n, m; cin >> n >> m;
  if(n < m) {
    int t = n;
    n = m;
    m = t;
  }
  if(n - m >= 2) {
    puts("0");
    return 0;
  }
  if(n - m == 1) {
    cout << fact(n) * fact(m) % MAX << endl;
    return 0;
  }
  cout << 2 * fact(n) * fact(m) % MAX << endl;
}


Measured memory_bytes: 256
object MainKt {
  @JvmStatic fun main(args:Array<String>) {
    val (X,A,B)=readLine()!!.split(" ").map(String::toInt)

    println(if(B-A>X) {
      "dangerous"
    } else {
      if(B-A<=0) {
        "delicious"
      } else {
        "safe"
      }
    })
  }
}


Measured memory_bytes: 38020
#include<iostream>

using namespace std;

int main(){
	char a,b;
	cin >> a >> b;
	if(a == 'H')
		cout << b << endl;
	else{
		if(b == 'H')
			cout << 'D' << endl;
		else
			cout << 'H' << endl;
	}
	return 0;
}



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

int main() {
    int n, D[100];
    cin >> n;
    for (int i = 0 ; i < n; i++) cin >> D[i];
    
    for (int i = n-1; i >=0; i--){
        if (i != 0){
        cout << D[i] << " ";
        }
        else cout << D[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int a,b,c,d,e,k;
 	cin >> a>>b>>c>>d>>e>>k;
 	if(e-a>k){
 		cout << ":(" << endl;
 	}else{
 		cout << "Yay!"  << endl;
 	}
 }

Measured memory_bytes: 764
from collections import deque

def solve(n, ABC, q, k, XY):
    graph = [[] for _ in range(n)]
    for a, b, c in ABC:
        graph[a - 1].append((b - 1, c))
        graph[b - 1].append((a - 1, c))

    q = deque(maxlen=n)
    q.append((k - 1, 0))
    used = {k - 1}
    l = [0] * n
    while len(q) > 0:
        node, length = q.popleft()
        l[node] = length
        for next, next_length in graph[node]:
            if next in used:
                continue
            q.append((next, length + next_length))
            used.add(next)

    return [l[x - 1] + l[y - 1] for x, y in XY]

_n = int(input())
_ABC = [list(map(int, input().split())) for _ in range(_n - 1)]
_q, _k = map(int, input().split())
_XY = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_n, _ABC, _q, _k, _XY), sep='\n')

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

using namespace std;
const int maxn=1e5+100;
int a[maxn];
int main()
{
    int n;

    cin>>n;
    int i,x;
    for (i=1;i<=n;i++){
      scanf("%d",&a[i]);
    }
    int ans=0,k=0;
    for (i=1;i<=n;i++){
		if (a[i]==i) k++;
		else {
		  if (k==0) continue;
		  if (k&1) ans+=k/2+1;
		  else ans+=k/2;
		  k=0;
		}
    }
           if (k&1) ans+=k/2+1;
		  else ans+=k/2;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
// Ref : https://book.mynavi.jp/ec/products/detail/id=35408

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

class Node {
public:
	int location;
	int p, l, r;
	Node() {}
};

class Point {
public:
	int id, x, y;
	Point() {}
	Point(int id, int x, int y) : id(id), x(x), y(y) {}
	bool operator < (const Point &p) const {
		return id < p.id;
	}

	void print() {
		printf("%d\n", id);
	}
};

static const int MAX = 1000000;
static const int NIL = -1;

int N, np;
Point P[MAX];
Node T[MAX];

bool lessX(const Point &p1, const Point &p2) { return p1.x < p2.x; }
bool lessY(const Point &p1, const Point &p2) { return p1.y < p2.y; }

int makeKDTree(int l, int r, int depth) {
	if (!(l < r)) return NIL;
	int mid = (l + r) / 2;
	int t = np++;
	if ((depth % 2) == 0) {
		sort(P + l, P + r, lessX);
	}
	else {
		sort(P + l, P + r, lessY);
	}
	T[t].location = mid;
	T[t].l = makeKDTree(l, mid, depth + 1);
	T[t].r = makeKDTree(mid + 1, r, depth + 1);

	return t;
}

void find(int v, int sx, int tx, int sy, int ty, int depth, vector<Point> &ans) {
	int x = P[T[v].location].x;
	int y = P[T[v].location].y;

	if (sx <= x && x <= tx && sy <= y && y <= ty) {
		ans.push_back(P[T[v].location]);
	}

	if ((depth % 2) == 0) {
		if (T[v].l != NIL) {
			if (sx <= x) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
		}
		if (T[v].r != NIL) {
			if (x <= tx) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
		}
	}
	else {
		if (T[v].l != NIL) {
			if (sy <= y) find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
		}
		if (T[v].r != NIL) {
			if (y <= ty) find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
		}
	}
}

int main() {
	int x, y;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &x, &y);
		P[i] = Point(i, x, y);
		T[i].p = T[i].l = T[i].r = NIL;
	}

	np = 0;
	int root = makeKDTree(0, N, 0);

	int q;
	scanf("%d", &q);
	int sx, tx, sy, ty;
	vector<Point> ans;
	for (int i = 0; i < q; i++) {
		scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
		ans.clear();
		find(root, sx, tx, sy, ty, 0, ans);
		sort(ans.begin(), ans.end());
		for (unsigned int j = 0; j < ans.size(); j++) {
			ans[j].print();
		}
		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 15848
N = int(input())
ans = ''
N1 = N
i = 1
if N == 0:
    print('0')
else:
    while N1 != 0:
        if N1 % 2 == 0:
            ans = '0'+ans
            N1 =int(N1/2)
        else:
            ans = '1'+ans
            N1 = int((N1-i)/2)
        i *= -1
    print(ans)

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

int main(void)
{
	int n, m, p[10000];
	while (cin >> n >> m)
	{
		if (n == 0 && m == 0) break;
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> p[i];
			sum += p[i];
		}
		sort(p, p + n);
		for (int i = n - m; i >= 0; i -= m) sum -= p[i];
		cout << sum << endl;
	}
}

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

int main()
{
	int s;
	scanf("%d", &s);
	//入力完了
	int a[1000000];
	int b[300] = {};
	int answer;

	for (int i = 0; i < 1000000; i++)
	{
		if (i == 0) a[i] = s;
		else if (a[i - 1] % 2 == 0) a[i] = a[i - 1] / 2;
		else a[i] = 3 * a[i - 1] + 1;

		b[a[i]]++;
		if (b[a[i]] == 2)
		{
			answer = i + 1;
			break;
		}
	}

	printf("%d", answer);
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int a[200000];

int main() {
    int n, x = -1, i;
    long long ans = 0;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (i = n - 1; i >= 0; i--) {
        if (a[i] > i) {
            ans = -1;
            break;
        }
        
        if (x > i && a[x] - a[i] > x - i) {
            ans = -1;
            break;
        }
        
        if (x > i && a[x] - a[i] == x - i) continue;
        
        ans += a[i];
        x = i;
    }
    
    printf("%lld\n", ans);
    
    return 0;
}


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

void out(vector<int> v, int n) {
  for (int i = 0; i < n; i++) {
    if (i == n - 1)
      cout << v[i] << endl;
    else
      cout << v[i] << ' ';
  }
}

void insertionSort(vector<int> A, int n) {
  int v, j;
  for (int i = 1; i < n; i++) {
    v = A[i];
    j = i - 1;
    while (0 <= j && v < A[j]) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    out(A, n);
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  out(v, n);
  insertionSort(v, n);
}



Measured memory_bytes: 3168
package main

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

func main() {
	n := readI()
	a := make(map[int]int)
	for i := 0; i < n-1; i++ {
		a[readI()]++
	}
	for i := 1; i <= n; i++ {
		fmt.Println(a[i])
	}
}

/*-----------Utils-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	if len(os.Args) >= 2 {
		if os.Args[1] == "debug" {
			debug()
		}
	}
	const maxBuf = 200100
	var buf []byte = make([]byte, maxBuf)
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBuf)
}

func debug() {
	testFile, err := os.Open("./test/sample-3.in")
	if err != nil {
		fmt.Fprintln(os.Stderr, "Error : There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

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

func readSs(a int) []string {
	b := make([]string, a)
	for i := 0; i < a; i++ {
		b[i] = readS()
	}
	return b
}

func readI() int {
	sc.Scan()
	r, _ := strconv.Atoi(sc.Text())
	return r
}

func readIs(a int) []int {
	b := make([]int, a)
	for i := 0; i < a; i++ {
		b[i] = readI()
	}
	return b
}

func readF() float64 {
	sc.Scan()
	r, _ := strconv.ParseFloat(sc.Text(), 64)
	return r
}

func readFs(a int) []float64 {
	b := make([]float64, a)
	for i := 0; i < a; i++ {
		b[i] = readF()
	}
	return b
}


Measured memory_bytes: 13336
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

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

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 10000+5;
const int D = 100+5;

int n;
int d;
string s;
bool vis[N][D][2][2];
int memo[N][D][2][2];

int DP(int pos, int res, bool menor, bool valid){
	if(pos == n){
		return res == 0 and valid;
	}
	if(vis[pos][res][menor][valid]) return memo[pos][res][menor][valid];
	int ans = 0;
	if(menor){
		for(int i=0; i<10; i++){
			bool nxt_valid = valid || (i > 0);
			ans = add(ans,DP(pos+1,add(res,i,d),true,nxt_valid));
		}
	}
	else{
		for(int i=0; i<=s[pos]-'0'; i++){
			bool nxt_valid = valid || (i > 0);
			ans = add(ans,DP(pos+1,add(res,i,d),i < s[pos]-'0',nxt_valid));
		}
	}
	vis[pos][res][menor][valid] = true;
	return memo[pos][res][menor][valid] = ans;
}

int main(){
	cin >> s >> d;
	n = s.size();
	printf("%d\n",DP(0,0,0,0));
	return 0;
}


Measured memory_bytes: 21760
fn main() {
    let n: usize = read_line_as_value();
    let b_in: Vec<usize> = read_line_as_vector();

    let mut prev = b_in[n-2];
    let mut ans = 0;
    for i in (0..n-1).rev() {
        ans += std::cmp::min(b_in[i], prev);
        prev = b_in[i];
    }
    ans += prev;
    println!("{}", ans);
}

fn read_line_as_value<T: std::str::FromStr>() -> T {
    let mut input = String::new();
    let res = std::io::stdin().read_line(&mut input);
    if let Err(error) = res {
        panic!("io error at stdin.read_line: {}", error);
    };
    match input.trim().parse() {
        Ok(val) => val,
        _ => panic!("error while parsing input: {}", input)
    }
}

fn read_line_as_vector<T: std::str::FromStr>() -> Vec<T> {
    let mut input = String::new();
    let res = std::io::stdin().read_line(&mut input);
    if let Err(error) = res {
        panic!("io error at stdin.read_line: {}", error);
    };
    match input.trim().split_whitespace().map(|x| x.parse()).collect::<Result<Vec<T>, _>>() {
        Ok(vec) => vec,
        _ => panic!("error while parsing input: {}", input)
    }
}

Measured memory_bytes: 2076