akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N,L;
	cin >> N >> L;

	vector<int> taste(N);
	for ( int i = 0 ; i < N ; i++){
    	taste.at(i) = L + i;
    }
	
	int R = 0;  
  	if( L >= 0 )
      R = 0;
  	else if( taste.at(0)<0 && taste.at(N-1)<= 0 )
      R = N-1;      
    else{  
	for ( int i = 0 ; i < N-1 ; i++){      
    	if(taste.at(i) == 0)
          R = i;
      	if( taste.at(i)<0 && taste.at(i+1)>0 ){
          if( 0 - taste.at(i) >= taste.at(i+1) - 0)
            R = i + 1;
          else
            R = i;
        }
    }
    }

	int sum = 0;
	for ( int i = 0 ; i < N ; i++){
    	sum += taste.at(i);
    }
	cout << sum - taste.at(R) << endl;
}


Measured memory_bytes: 256
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

    def lower_bound(self, x):
        s = 0
        pos = 0
        depth = self.n.bit_length()
        v = 1 << depth
        for i in range(depth, -1, -1):
            k = pos + v
            if k <= self.n and s + self.bit[k] < x:
                    s += self.bit[k]
                    pos += v
            v >>= 1
        return pos

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, q = map(int, input().split())
A = list(map(int, input().split()))
bit = BIT(n)
bit.init(A)
for i in range(q):
    t, a, b = map(int, input().split())
    if t == 0:
        bit.add(a, b)
    else:
        print(bit.sum(a, b))


Measured memory_bytes: 143624
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
  int D,i;
  long N;
  char str[100],*p;
  
  fgets(str,sizeof(str),stdin);
  p=strtok(str," \n");
  D=atoi(p);
  p=strtok(NULL," \n");
  N=atol(p);
  if(N==100){
    N+=1;
  }
  
  for(i=0;i<D;i++){
    N*=100;
  }
  
  printf("%ld\n",N);
  
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;
 
public class Main {
 
	public Main() {
		// TODO 自動生成されたコンストラクター・スタブ
	}
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int answer,index;
		int a,b;
		String s,t;
		
			// 整数の入力
		
		a = sc.nextInt();
		b = sc.nextInt();
		sc.close();
		
		answer=(b-1+a-2)/(a-1);
		System.out.print(answer);

			// 出力
 
	}
}	

Measured memory_bytes: 21332
#include <cstdio>
typedef long long int64;
static const int MAXN = 102;
static const int MAXEXT = 310;
template <typename T> inline void upd_max(T &var, const T val) { if (var < val) var = val; }

int n, cap;
int w[MAXN], v[MAXN];
int f[MAXN][MAXN][MAXEXT] = {{{ 0 }}};

int main()
{
    scanf("%d%d", &n, &cap);
    for (int i = 0; i < n; ++i) scanf("%d%d", &w[i], &v[i]);

    f[0][0][0] = 0;
    f[0][1][0] = v[0];
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= n; ++j)
            for (int k = 0; k < MAXEXT; ++k) {
                upd_max(f[i][j][k], f[i - 1][j][k]);
                if (j - 1 >= 0 && k - (w[i] - w[0]) >= 0)
                    upd_max(f[i][j][k], f[i - 1][j - 1][k - (w[i] - w[0])] + v[i]);
            }
    }

    int ans = 0;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j < MAXEXT; ++j)
            if ((int64)w[0] * i + j <= cap) upd_max(ans, f[n - 1][i][j]);
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 12416
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline().rstrip
show_flg=False
show_flg=True

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
ans=0

s,t=LI()
a=(2*t-s)//3
b=(2*s-t)//3


if (2*t-s)%3!=0 or (2*s-t)%3!=0:
    print(0)
    exit()

cm=Comb(a+b+1+1)
ans=cm.comb(a+b,min(a,b))
print(ans)



Measured memory_bytes: 49516
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <deque>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, k;
int p;

ll dfs(vector<vector<int>>& g, int now, int from) {
  int can_use_color_num;
  if(from == -1) can_use_color_num = k - 1;
  else can_use_color_num = k - 2;

  ll cc = 1;
  if(k < (int)g[now].size()) {
    return 0;
  } else {
    for(auto e: g[now]) {
      if(e == from) continue;
      cc *= can_use_color_num;
      can_use_color_num--;
      cc %= mod;
    }

    for(auto e: g[now]) {
      if(e == from) continue;
      cc *= dfs(g, e, now);
      cc %= mod;
    }
    return cc;
  }
}

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

  cin >> n >> k;

  vector<vector<int>> g(n);
  REP(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  int ma = 0;
  REP(i, n) if(ma < g[i].size()) p = i, ma = g[i].size();

  ll ans = (k * dfs(g, p, -1)) % mod;
  cout << ans << endl;
}


Measured memory_bytes: 13452
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

S = sum(A)
ans = [0] * N
ans[0] = S - sum(A[1::2]) * 2
for i in range(1, N):
    ans[i] = (A[i - 1] - ans[i - 1] // 2) * 2
print(*ans)


Measured memory_bytes: 14408
from collections import deque
N, M = map(int, input().split())
#辺を取り除くことはabのセットとなっている要素から取り除くことと等価。頂点を消すのではない。
ab = [list(map(int, input().split())) for _ in range(M)]
c = 0
for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j][0], ab[j][1]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    Q = deque()
    Q.append(0)
    d = [0] * N
    d[0] = 1
    while Q:
        q = Q.popleft()
        for g in G[q]:
            if d[g] == 0:
                d[g] = 1
                Q.append(g)
    if 0 in d:
        c += 1

print(c)


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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long K = long.Parse(Console.ReadLine());
            long sum = 0;
            for (long i = 1; i <= K; i++)
            {
                for (long j = 1; j <= K; j++)
                {
                    for (long n = 1; n <= K; n++)
                    {
                        long tmp = Gcd(i, j);
                        sum += Gcd(tmp, n);
                    }
                }
            }
            Console.WriteLine(sum);
        }

        //最大公約数
        public static long Lcm(long a, long b)
        {
            return a * b / Gcd(a, b);
        }

　　　　//最小公倍数
        public static long Gcd(long a, long b)
        {
            if (a < b)
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
    }
}


Measured memory_bytes: 27540
#include <cstdlib>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
typedef long long ll;

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

ll solve(const vector<int> &a, int start){
  const int n = a.size();
  ll sum = start;

  ll ret = std::abs(start - a[0]);
  for(int i = 1; i < n; i++){
    ll next;
    if(sum > 0){
      next = - sum - 1;
      if(a[i] < next) next = a[i];
    }else{
      next = - sum + 1;
      if(a[i] > next) next = a[i];
    }
    sum += next;
    ret += std::abs(next - a[i]);
  }

  return ret;
}

int main(){
  const int n = getInt();
  vector<int> a(n);
  REP(i,n) a[i] = getInt();

  ll ans = 1ll << 60;
  if(a[0] == 0) ans = min(ans, solve(a, 1));
  else ans = min(ans, solve(a, a[0]));
  if(a[0] == 0) ans = min(ans, solve(a, -1));
  else if(a[0] > 0) ans = min(ans, solve(a, -1));
  else ans = min(ans, solve(a, 1));
  printf("%lld\n", ans);

  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#define N 25
typedef struct{
    int p,l,r;
    int sib,deg,dep,hei;
}Node;
Node T[N];

int setheight(int);

int main(){
    int n,i;
      int id,left,right;
      scanf("%d",&n);
      for(i=0; i<n; i++) {
          T[i].p = -1;
          T[i].sib = -1;
      }
      for(i=0; i<n; i++){
          scanf("%d",&id);
          scanf("%d%d",&left,&right);
          T[id].l = left;
          T[id].r = right;
          T[left].p = id;
          T[right].p = id;
          T[left].sib = right;
          T[right].sib = left;
      }
      for(id=0; id<n; id++){
          printf("node %d: parent = %d, sibling = %d, ",id,T[id].p,T[id].sib);
          T[id].deg = 0;
          if(T[id].l != -1) T[id].deg++;
          if(T[id].r != -1) T[id].deg++;
          printf("degree = %d, ",T[id].deg);
          T[id].dep = 0;
          i = id;
          while(T[i].p != -1){
              T[id].dep++;
              i = T[i].p;
          }
          printf("depth = %d, ",T[id].dep);
          T[id].hei = 0;
          T[id].hei = setheight(id);
          printf("height = %d, ",T[id].hei);
          if(T[id].p == -1) printf("root\n");
          else if(T[id].deg == 0) printf("leaf\n");
          else printf("internal node\n");          
      }
      return 0;
}

int setheight(int u){
    int h1=0,h2=0;
    if(T[u].l != -1) h1 = setheight(T[u].l) + 1;
    if(T[u].r != -1) h2 = setheight(T[u].r) + 1;
    
    if(h1<h2) return h2;
    else return h1;
}

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

using namespace std;

int N,M;
long int memo;
char spc;
long int memo2;
long int memo3;
long int ans = 0;

int main(){
    priority_queue<long int> pq;

    scanf("%d %d",&N,&M);
    scanf("%c",&spc);

    for(int i=0; i<N; i++){
        scanf("%ld",&memo);
        pq.push(memo);
    }


    for(int i=0; i<M; i++){
        memo2 = pq.top();
        pq.pop();
        memo3 = memo2/2;
        pq.push(memo3);
        
    }
   

    while (!pq.empty()){
        memo2 = pq.top();
        pq.pop();
        ans += memo2;
       
    }
    printf("%ld",ans);

    return 0;
}

Measured memory_bytes: 1400
import math
a,b,x = map(int, input().split())

if x >= (a * a * b) / 2:
	c = 2 * b - (2 * x) / (a * a)
	angle = math.degrees(math.atan(c / a))
else:
	d = 2 * x / (a * b)
	angle = math.degrees(math.atan(b / d))
print(angle)


Measured memory_bytes: 3060
#include <stdio.h>
#include <vector>
#include <array>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>

using std::string;

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}


int main(){

    string word;
    getline(std::cin, word);

    string text, buffer;
    while(true) {
        getline(std::cin, buffer);
        text += buffer;
        if (buffer == string("END_OF_TEXT")) break;
        text += string(" ");
    }

    int count = 0;
    for(auto each: split(text, ' ')) {
        std::transform(each.begin(), each.end(), each.begin(), ::tolower);
        if (word == each) {
            count++;
        } else {
        }
    }
    printf("%d\n", count);
}


Measured memory_bytes: 3340
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int a,b;
    bool flag=false;
    cin>>a>>b;
    cin>>s;
    if(s.length()==a+b+1)
    {
        int i;
        for(i=0;i<s.length();i++)
        {
            if(i!=a&&(s[i]<'0'||s[i]>'9'))
                break;
            if(i==a&&s[i]!='-')
                break;
        }
        if(i==s.length())
            flag=true;
    }
    if(flag)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 256
def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Measured memory_bytes: 6772
#include <iostream>

typedef long long ll;

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

#define debug(x) cout << #x << "=" << x << endl;

using namespace std;

//C. Scc Puzzle

//図形sと図形cの数がそれぞれ与えられる(1≦s,c≦10^12)
//cを2つ組み合わせてsを作ることができる

// "scc"がいくつ作れるかを出力する

int main(void){

  ll s, c;

  cin >> s >> c;

  ll ans = 0;

  if(s*2 <= c){
    ans += s;
    c -= s*2;
  }else{
    ans += c / 2;
    c = 0;
  }

  ans += c / 4;

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int mul2 = 0, mul4 = 0, odd = 0;
    REP(i,N)
    {
        int tmp; cin >> tmp;
        if(tmp % 4 == 0) mul4++;
        else if(tmp % 2 == 0) mul2++;
        else odd++;
    }
    if(N % 2 == 1 && N/2+1 == odd && N/2 == mul4)
    {
        cout << "Yes" << endl;
        return 0;
    }

    if(odd == 0){
        cout << "Yes" << endl;
        return 0;
    }
    else{
        if(odd <= mul4){
            cout << "Yes" << endl;
            return 0;
        }
        else{
            cout << "No" << endl;
            return 0;
        }
    }
    //else{
    //    if(odd - 1 <= mul4){
    //        cout << "Yes" << endl;
    //        return 0;
    //    }
    //    else{
    //        cout << "No" << endl;
    //        return 0;
    //    }
    //}


}

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

using ll = long long;

#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                     \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define check(s) cerr << s << endl

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

ll H, W, K;
vector<vector<char>> C;

void solve() {
  ll cnt_k = 0;  // 全部の黒の数

  rep(i, H) {
    rep(j, W) {
      if (C.at(i).at(j) == '#') {
        cnt_k++;
      }
    }
  }

  ll ans = 0;

  rep(h, 1 << H) {
    rep(w, 1 << W) {
      ll cnt = 0;
      rep(i, H) {
        rep(j, W) {
          if (C.at(i).at(j) == '#' && (h & (1 << i) || w & (1 << j))) {
            cnt++;
          }
        }
      }
      if (cnt_k - cnt == K) ans++;
    }
  }

  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);

  cin >> H >> W >> K;
  C.resize(H);
  rep(i, H) {
    C.at(i).resize(W);
    rep(j, W) { cin >> C.at(i).at(j); }
  }

  solve();

  return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <stdio.h>
#include <string>
using namespace std;
int main()
{
    string str;
    int n = 0;
    int s1[100100] = {};
    int s2[100100] = {};
    int cs1 = 0;
    int cs2 = 0;

    cin >> str;
    n = str.size();

    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            s1[i] = 1;
        }
        else
        {
            s2[i] = 1;
        }
    }

    for (int i = 0; i < n; i++)
    {

        if (s1[i] != str[i] - '0')
        {
            cs1 += 1;
        }
        if (s2[i] != str[i] - '0')
        {
            cs2 += 1;
        }
    }

    cout << min(cs1, cs2) << endl;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define int long long
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; }

int N,a[3010];

int dp[3010][3010];
const int INF=1e18;

int rec(int i,int j)
{
    if(i==j) return 0;
    if(dp[i][j]>=0) return dp[i][j];
    
    if(N%2==(j-i)%2){
        int res=-INF;
        chmax(res,a[i]+rec(i+1,j));
        chmax(res,a[j-1]+rec(i,j-1));
        return dp[i][j]=res;
    }else{
        int res=INF;
        chmin(res,rec(i+1,j));
        chmin(res,rec(i,j-1));
        return dp[i][j]=res;
    }
}

signed main()
{
    cin>>N; 
    for(int i=0;i<N;i++){
        cin>>a[i];
    }

    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            dp[i][j]=-INF;
        }
    }
    cout<<2*rec(0,N)-accumulate(a,a+N,0LL)<<endl;
}


Measured memory_bytes: 71040
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#include<set>
using namespace std;

int n,a,b,c,t;
vector<int>TOP;
int dp[110][110];
//dp[i][j] == max(dp[i-1][j],dp[i-1][j-1]+TOP[i]

/*
int solve(int now){
	if(0 == n)return 0;
	if ((solve(now+1))/(top*b)  >  solve(now+1)+(TOP[now]/ ( (top+1)*b ))) {
		return solve(now+1);
	}
	if ((solve(now+1))/(top*b)  <  solve(now+1)+(TOP[now]/ ( (top+1)*b ))) {
		return solve(now+1)+TOP[now];
		top++;

	}
}
*/

int main(){

	cin >> n >> a >> b >> c;
	t = c/a;
	for(int i=0; i<n; i++){
		int d;
		cin >> d;
		TOP.push_back(d);
	}

	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			if(j != 0){
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+TOP[i-1]);
			}
		}
	}

	for(int i=1; i<=n; i++){
		for(int j=0;j<=n; j++){
			t = max(t,(dp[i][j]+c)/(b*j+a));
		}
	}

	cout << t << endl;
	return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0;i < n;++i)
#define REPR(i, n) for (int i = n;i >= 0;--i)
#define FOR(i, m, n) for (int i = m;i < n;++i)
#define FORR(i, m, n) for (int i = m;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define FI first
#define SE second
#define PB(a) push_back(a)
#define DEBUG(x) cerr << __LINE__ << ":" << #x << ": " << x << "\n";
#define SZ(x) ((int)(x).size())
#define SO(x) sizeof((x)) / sizeof((x)[0])
//#define int long long
using namespace std;
using lint = long long;
struct Fast{Fast(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};} fast;
const int INF = INT_MAX;
const lint LINF = LLONG_MAX;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
inline void co(int a[], int n) {REP(i, n) cout << a[i] << " "; cout << "\n";}
//if (IO > 1e5){lint a;	scanf(%lld, &a);	printf("%lld\n", a);}

signed main(){
	int n,m;
	cin >> n >> m;
	
	int b,ans = 1;
	for (int a = 1; a*a <= m; a++){
		if (m%a != 0) continue;
		b = m/a;
		if ((long)a*n <= m) ans = max(ans,a);
		if ((long)b*n <= m) ans = max(ans,b);
	}
	
	cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define f first
#define s second


//var 
LL n, L[105];

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

	cin >> n;
	for(int i = 1; i<=n; i++)
		cin >> L[i];

	sort(L+1, L+n+1);
	LL ans = 0;
	for(int i = 1; i<=n; i++){
		for(int j = i+1; j<=n; j++){
			for(int k = j+1; k<=n; k++){
				if(L[i] == L[j] || L[i] == L[k] || L[j] == L[k]) continue;
				if((L[i] + L[j]) > (L[k])){
					//bcout << i << " " << j << " " << k << endl;
 					ans++;
				}
			}
		}
	}

	cout << ans << endl;

	cout.flush();
	return 0;
}

Measured memory_bytes: 3656
x,y = gets.split.map(&:to_i)
if x>3 && y>3
    puts 0
else
    ans = 0
    ans += 300000 if x==1
    ans += 200000 if x==2
    ans += 100000 if x==3
    ans += 300000 if y==1
    ans += 200000 if y==2
    ans += 100000 if y==3
    ans += 400000 if x==1 && y==1
    puts ans
end

Measured memory_bytes: 1788
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N = int(input())
    H = int(input())
    W = int(input())

    print((N - H + 1) * (N - W + 1))


if __name__ == '__main__':
    main()


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

vector<int> record;
vector<int> dist;
vector<int> deg;
vector<vector<int>> edges;
int idx;

void dfs(int v, int p, int dep){
    dist.push_back(dep);
    int r = record[idx];
    if(0 <= p){
        r--;
        edges.push_back({p});
        deg[p]--;
        edges[p].push_back(v);
    }else{
        edges.push_back({});
    }
    deg.push_back(r);
    
    while(deg[v]){
        idx++;
        if(record[idx]<0){
            for(int i=0; i<dist.size(); i++){
                if(dist[i] == dist[v] + record[idx] && 0 < deg[i]){
                    edges[i].push_back(v);
                    edges[v].push_back(i);
                    deg[i]--;
                    deg[v]--;
                }
            }
        }else{
            dfs(deg.size(), v, dep+1);
        }
    }
}

void solve(){
    idx = 0;
    dfs(0, -1, 0);
    for(int i=0; i<edges.size(); i++){
        auto edge = edges[i];
        sort(edge.begin(), edge.end());
        cout << i+1;
        for(auto v: edge)
            cout << " " << v+1;
        cout << endl;
    }
}

int main(){
    int N; cin >> N;
    int cnt = 1;
    while (N--) {
        record.clear();
        dist.clear();
        deg.clear();
        edges.clear();
        
        int r;
        while(cin >> r, r)
            record.push_back(r);
        //cout << "Case:" << cnt << endl;
        solve();
        cnt++;
    }
    
    return 0;
}

Measured memory_bytes: 3004
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, b, a) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

int main() {
  int n, d;
  cin >> n >> d;
  int ans = 0;
  FI(i,1,n) {
    FI(j,20,d) {
      int x = j / 10;
      int y = j % 10;
      if (y >= 2 && x * y == i) ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
group1 = ['1', '3', '5', '7', '8', '10', '12']
group2 = ['4', '6', '9', '11']
group3 = ['2']

x, y = input().split()
if x in group1 and y in group1:
    print('Yes')
elif x in group2 and y in group2:
    print('Yes')
else:
    print('No')

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

int main(){
  int ans=0;
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  vector<int> c(n-1);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  for(int i=0;i<n;i++){
    cin >> b.at(i);
    ans += b.at(i);
  }
 
  for(int i=0;i<n-1;i++){
    cin >> c.at(i);
  }
  for(int i=0;i<n-1;i++){
    if(a.at(i)+1==a.at(i+1)){
      ans += c.at(a.at(i)-1);
    }}
  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    b=LI()
    ans=[]
    for _ in range(N):
        for i in range(len(b)-1,-1,-1):
            if b[i]==i+1:
                ans.append(b[i])
                b.pop(i)
                break
            
    if len(ans)==N:
        for i in range(N):
            print(ans[-1-i])
    else:
        print(-1)
        

main()


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

using namespace std;

using ll = long long;
using ii = pair<int,int>;

#define ff first
#define ss second

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	char a,b;
	cin >> a >> b;
	string s1(a-'0',b),s2(b-'0',a);
	cout << (s1 <= s2 ? s1 : s2) << '\n';
	return 0;
}

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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int main(){
	int n;cin >> n;
	vector<ll> L(n+1);
	vector<ll> R(n+1);
	
	REP(i,n)cin >> L[i] >> R[i];
	
	sort(ALL(R));
	sort(ALL(L),greater<ll>());
	
	DBG(SHOW1d(R,R.size()););
	DBG(SHOW1d(L,L.size()););
	
	ll ans = 0;
	ll tmp = 0;
	REP(i,n+1){
		tmp += 2 *(L[i] - R[i]);
		ans = max(ans,tmp);
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
import std.stdio, std.conv, std.string;

void main(){
	auto ip = readln.split.to!(int[]), x = ip[0], y = ip[1];
	const gr = [0, 1, 2, 1, 3, 1, 3, 1, 1, 3, 1, 3, 1];
	if(gr[x] == gr[y]){
		writeln("Yes");
	} else {
		writeln("No");
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
typedef vector<vector<char> > vvc;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
template<class T> using vv=vector<vector< T > >;
typedef deque<int> di;
typedef deque<deque<int> > ddi;
typedef deque<bool> db;
typedef deque<deque<bool> > ddb;

// cout pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    s << p.first << " " << p.second << "\n";
    return s;
}

// cout vector<pair>
template<typename T1, typename T2> ostream& operator<<(ostream& s, const vector<pair<T1, T2> >& vp) {
    int len = vp.size();
    for (int i = 0; i < len; ++i) {
        s << vp[i];
    }
    s << "\n";
    return s;
}

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    return s;
}

// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
    int len = v.size();
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len - 1) s << "\t";
    }
    return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) {
        s << vv[i] << "\n";
    }
    return s;
}

// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
    int len = vv.size();
    for (int i = 0; i < len; ++i) {
        s << vv[i] << "\n";
    }
    return s;
}

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
        printf("0\n");
        return 0;
    }
    vll ar = {a, b, c};
    sort(all(ar));
    printf("%lld\n", ar[0]*ar[1]);

    return 0;
}


Measured memory_bytes: 888
using System;
using System.Linq;
using System.Collections.Generic;
class c
{
    static void Main()
    {
        var nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var x = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        x = x.OrderBy(f => f).ToArray();
        var len = new List<int>();
        for (int i = 0; i < x.Length - 1; i++)
        {
            len.Add(x[i + 1] - x[i]);
        }
        len = len.OrderByDescending(f => f).ToList();
        long ans = len.Sum();
        for (int i = 0; i < nm[0] - 1; i++)
        {
            if (i == len.Count()) break;
            ans -= len[i];
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 24288
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;

int N;
int W[100];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> W[i];

	int s = 0;
	for (int i = 0; i < N; i++)
		s += W[i];

	int m = 1000000;
	int ss = 0;
	for (int i = 0; i < N; i++)
	{
		ss += W[i];
		int a = ss;
		int b = s - ss;
		m = min(m, abs(a-b));
	}

	cout << m << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
// #include <functional>

using namespace std;

void solve()
{
    // 入力の処理
    long long A, B;
    cin >> A >> B;

    long long x = A * B;
    long long temp;
    if (A < B)
    {
        temp = A;
        A = B;
        B = temp;
    }

    long long r = A % B;
    while (r != 0)
    {
        A = B;
        B = r;
        r = A % B;
    }

    cout << x / B << endl;

    return;
}

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


Measured memory_bytes: 256
import java.util.*;
class Main{
    public static void main(String[] args){
	Scanner stdIn = new Scanner(System.in);
        int A = stdIn.nextInt();
	int B = stdIn.nextInt();
	int k =A+A-1;
	if(A==B){
	    k=A+B;
	}
	if(A<B){
	    k=B+B-1;
	}
	System.out.println(k);
    }
}


Measured memory_bytes: 21844
n = int(input())
c = input()
cl = list(c)
wi = 0
wnum=0
ri = n-1
rnum=0
br=0
bw=0
res1 = n
break1 = 0
for i in range(n):
    while(cl[wi] == "R" and bw==0):
        wi+=1
        if(wi >= n-1):
            bw=1
            break
    if(cl[wi] == "W"):
        wnum+=1
    while(cl[ri] == "W" and br==0):
        ri-=1
        if(ri <= 0):
            br=1
            break
    if(cl[ri] == "R"):
        rnum+=1
    if(ri < wi and break1 == 0):
        res1 = i
        break1 = 1
    wi+=1
    if(wi >= n-1):
        wi=0
        bw=1
    ri-=1
    if(ri <= 0):
        ri=n-1
        br=1

    if(br*bw==1):
        break
print(min(res1, rnum, wnum))

Measured memory_bytes: 77976
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

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

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  long a, count = 0;
  for(int i = 0; i < N; i++){
    cin >> a;
    if(a % 2 == 1)count++;
  }
  cout << (count % 2 == 0?"YES":"NO") << endl;
  return 0;
}

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

using Bool = bool;
using Int = long long int;
using String = std::string;
template <class... Ts>
using Tuple = std::tuple<Ts...>;
template <class T>
using Vector = std::vector<T>;
template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T>
using Set = std::set<T>;
template <class T, class U>
using Map = std::map<T, U>;

template <class Cost = Int>
struct Edge {
    Int src, dst;
    Cost cost;
    Edge(Int src = -1, Int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};
template <class Cost = Int>
using Graph = Vector<Vector<Edge<Cost>>>;

constexpr Int INF = std::numeric_limits<Int>::max() / 3;

Bool solve() {
    Int m, l, cap;
    std::cin >> m >> l >> cap;
    if (m == 0) return false;
    cap *= 10;

    String ss, gs;
    std::cin >> ss >> gs;

    Int n;
    Graph<Int> graph;

    Map<String, Int> rev;

    {
        Vector<String> strs;
        Vector<Tuple<String, String, Int>> edges(m);
        for (auto& e : edges) {
            String us, vs;
            Int d;
            std::cin >> us >> vs >> d;
            e = std::make_tuple(us, vs, d);
            strs.push_back(us), strs.push_back(vs);
        }

        std::sort(strs.begin(), strs.end());
        strs.erase(std::unique(strs.begin(), strs.end()), strs.end());
        n = strs.size();
        for (Int i = 0; i < n; ++i) rev[strs[i]] = i;

        graph.resize(n);
        for (auto& e : edges) {
            String us, vs;
            Int d;
            std::tie(us, vs, d) = e;
            Int u = rev[us], v = rev[vs];

            graph[u].emplace_back(u, v, d);
            graph[v].emplace_back(v, u, d);
        }
    }

    Int s = rev[ss], g = rev[gs];

    Set<Int> tanks;
    for (Int i = 0; i < l; ++i) {
        String vs;
        std::cin >> vs;
        tanks.insert(rev[vs]);
    }

    Vector<Vector<Int>> dist(n, Vector<Int>((cap + 1), INF));
    dist[s][cap] = 0;
    MinHeap<Tuple<Int, Int, Int>> heap;
    heap.emplace(0, s, cap);

    while (!heap.empty()) {
        Int d, v, c;
        std::tie(d, v, c) = heap.top();
        heap.pop();
        if (dist[v][c] < d) continue;

        for (auto e : graph[v]) {
            if (e.cost > c ||
                dist[e.dst][c - e.cost] <= dist[e.src][c] + e.cost) continue;
            dist[e.dst][c - e.cost] = dist[e.src][c] + e.cost;
            heap.emplace(dist[e.dst][c - e.cost], e.dst, c - e.cost);
        }

        if (tanks.count(v) && dist[v][cap] > dist[v][c]) {
            dist[v][cap] = dist[v][c];
            heap.emplace(dist[v][cap], v, cap);
        }
    }

    Int ans = *std::min_element(dist[g].begin(), dist[g].end());

    std::cout << (ans < INF ? ans : -1) << std::endl;
    return true;
}

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



Measured memory_bytes: 99844
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
 
int main() {
    int a,b;
    cin >> a >> b;
    for(int i = 1; i<=1000; i++) {
        int tmp1 = i * 0.08;
        int tmp2 = i * 0.10;
        if(tmp1 == a && tmp2 == b) {
            cout << i << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
}

Measured memory_bytes: 256
# coding: utf-8
N,K=map(int,input().split())
MOD=10**9+7

fac=[None for i in range(5000)]
finv=[None for i in range(5000)]
inv=[None for i in range(5000)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(5000)

for i in range(1,K+1):
    print(COM(N-K+1,i)*COM(K-1,i-1)% MOD)

#print(COM(0,0))


Measured memory_bytes: 3948
using System;

namespace ABC053_B_A_to_Z_String
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			string s = Console.ReadLine();

			int startIndex = s.Length;
			int endIndex = s.Length;
			for (int i = 0; i < s.Length; i++)
			{
				//始点は必ず一番最初でないとNGだが、終点は一番最後でなくてはならないため更新OK
				if (s.Substring(i, 1) == "A" && startIndex == s.Length)
					startIndex = i;

				if (s.Substring(i, 1) == "Z")
					endIndex = i + 1; //iのみだと、Zの手前で止まってしまうため1小さくなる
			}

			int resultStrLength = endIndex - startIndex;
			Console.WriteLine(resultStrLength);
		}
	}
}

Measured memory_bytes: 17200
#include <cstdio>
#include <cmath>
#include <climits>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <fstream>
#include <functional>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <iomanip>
#define memtst(x) (sizeof(x) / 1024. / 1024.)
#define mem0(x) memset((x), 0, (sizeof x))
#define meminf(x) memset((x), INF, (sizeof x))
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define pf(x) push_front(x)
#define pq std::priority_queue
#define iter iterator
#define mp(x, y) std::make_pair((x), (y))
#define fst first
#define sec second
#define lc(x) ((x) * 2)
#define rc(x) ((x) * 2 + 1) 
#define md(x, y) (((x) + (y)) / 2)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair <int, int> pii;
const double PI = acos(-1);
const double EPS = 1e-6;
const ll MOD = 1e8 + 7;
const ll INF = 0x3F3F3F3F;
template <typename T>
inline T Abs(T x)
{
    return x < 0 ? x * -1 : x;
}
template <typename T>
inline T Max(T x, T y, T z)
{
    return std::max(std::max(x, y), z);
}
template <typename T>
inline T Min(T x, T y, T z)
{
    return std::min(std::min(x, y), z);
}
template <typename T>
inline T Ckmax(T &x, T y)
{
    return x = std::max(x, y);
}
template <typename T>
inline T Ckmin(T &x, T y)
{
    return x = std::min(x, y);
}
template <typename T>
inline T Sqr(T x)
{
    return x * x;
}
template <typename T>
T Pow(T x, T y, T z)
{
    T r = 1;
    while (y > 0)
    {
        if (y % 2 > 0)
            (r *= x) %= z;
        (x *= x) %= z;
        y /= 2;
    }
    return r % z;
}
template <typename T>
inline T gcd(T x, T y)
{
    return y > 0 ? gcd(y, x % y) : x;
}
template <typename T>
inline T lcm(T x, T y)
{
    return x / gcd(x, y) * y;
}
inline void cinspu(void)
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
}
inline ll read(void)
{
    char x;
    while (x = getchar(), x != '-' && !isdigit(x))
        ;
    char flg = x == '-';
    ll num = (flg ? getchar() : x) - '0';
    while (isdigit(x = getchar()))
        ((num *= 10) += x - '0') %= MOD;
    return flg ? -num : num;
}
const int N = 1e5 + 10;
int a[N], b[N];
int f[N], s[N];
ll ans[N];
inline int find(int x)
{
	return x == f[x] ? x : f[x] = find(f[x]);
}
int main()
{
	cinspu();
	int n, m;
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		f[i] = i;
		s[i] = 1;
	}
	for (int i = 1; i <= m; ++i)
		std::cin >> a[i] >> b[i];
	ans[m] = (n - 1ll) * n / 2;
	for (int i = m; i; --i)
	{
		int x = find(a[i]), y = find(b[i]);
		ll fk = 0;
		if (x != y)
		{
			fk += s[x] * s[y];
			s[x] += s[y];
			f[y] = x;
		}
		ans[i - 1] = ans[i] - fk;
	}
	for (int i = 1; i <= m; ++i)
		std::cout << ans[i] << std::endl;
	return 0;
}

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

using namespace std;

long long D[302][301], H[302];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> H[i];
    }
    H[n+1] = 0;
    for (int i = 0; i <= k; i++)
    {
        D[0][i] = 0;
    }
    for (int i = 1; i <= n+1; i++)
    {
        D[i][0] = D[i-1][0] + max(0ll, H[i]-H[i-1]);
        for (int y = 1; y <= k; y++)
        {
            D[i][y] = D[i-1][y] + max(0ll, H[i]-H[i-1]);
            for (int u = 1; u <= y; u++)
            {
                if (i-u >= 0)
                {
                    D[i][y] = min(D[i][y], D[i-u-1][y-u] + max(0ll, H[i]-H[i-u-1]));
                }
            }
        }
    }
    cout << D[n+1][k];
    return 0;
}


Measured memory_bytes: 896
object Main extends App {
  import scala.util.control.Breaks._
  val Array(d, g) = io.StdIn.readLine().split(' ').map(_.toInt)
  val (p, c) = Array.fill(d){
    val Array(pi, ci) = io.StdIn.readLine().split(' ').map(_.toInt)
    (pi, ci)
  }.unzip
  var min = p.sum
  for (b <- 0 until 1 << d) {
    val indices = for (i <- 0 to d; if (b >> i & 1) == 1) yield i
    var sum = 0
    val count = Array.fill(d)(0)
    indices.foreach {i =>
      sum += 100 * (i+1) * p(i) + c(i)
      count(i) = p(i)
    }
    breakable {
      for (i <- d-1 to 0 by -1)
        while (count(i) < p(i)) {
          if (sum >= g) break
          sum += 100 * (i+1)
          count(i) += 1
          if (count(i) == p(i)) sum += c(i)
        }
    }
    if (count.sum < min) min = count.sum
  }
  println(min)
}

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

using namespace std;

int main()
{
    int n,  a[100001];
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    bool b[100001] = {};
    b[1] = true;
    int c = a[1], cnt = 0;
    while (!b[c]) {
        b[c] = true;
        cnt++;
        if (c == 2) {
            cout << cnt << endl;
            return 0;
        }
        c = a[c];
    }
    
    cout << -1 << endl;
    
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll
#define INF 1e16
#define mod 1000000007
int main(){
    ll n,m;
    cin>>n>>m;
    string a="";
    string b="";
    rep(i,n) a+=to_string(m);
    rep(i,m) b+=to_string(n);
    if(a<b) cout<<a<<endl;
    else cout<<b<<endl;
return 0;}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
int a[N];
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    cin >> a[i];
  }
  int ans = a[n-1];
  for (int i = n-1; i >= 1; i--) {
    if (i > 1) ans += min(a[i], a[i-1]);
    else ans += a[i];
  }
  cout << ans;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mo = 10**9+7

def main():
	n = II()
	d=defaultdict(lambda: -1)
	ans = 0
	for i in range(n):
		s = IS()
		if d[s]==-1:
			d[s]=1
			ans+=1
	print(ans)



if __name__ == '__main__':
	main()

Measured memory_bytes: 35724