akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> T;

const ll mod = 1000000007;
const ll INF = 100000010000;

ll N, K;
ll A[100010];
ll kai[100010];

ll ans;

ll gcd(ll x, ll y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2 == 1)
	{
		return x * pow_mod(x, y - 1) % mod;
	}
	else
	{
		ll half = pow_mod(x, y / 2);
		return half * half % mod;
	}
}

ll div_mod(ll x)
{
	return pow_mod(x, mod - 2);
}

void init()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	kai[0] = 1;
	for (int i = 1; i < 100005; i++)
	{
		kai[i] = kai[i - 1] * i % mod;
	}
	sort(A, A + N);
}

void output()
{
	cout << ans << endl;
}



void solve()
{
	ll sum = 0;
	for (int i = K - 1; i < N; i++)
	{
		(sum += kai[i - 1] * div_mod(kai[K - 2] * kai[i - K + 1] % mod) % mod) %= mod;
		(ans += sum * A[i] % mod) %= mod;
	}
	sum = 0;
	for (int i = N - K; i >= 0; i--)
	{
		(sum += kai[N - i - 2] * div_mod(kai[K - 2] * kai[N - K - i] % mod) % mod) %= mod;
		(ans += mod - sum * A[i] % mod) %= mod;
	}

}

int main()
{
	init();

	solve();



	output();
	ll N;
	cin >> N;
}


Measured memory_bytes: 1792
package main

import (
	"fmt"
)

func main() {
	var a, b int
	fmt.Scan(&a, &b)
	if a == 1 {
		a = 14
	}
	if b == 1 {
		b = 14
	}
	if a == b {
		fmt.Println("Draw")
		return
	}
	if a > b {
		fmt.Println("Alice")
		return
	}
	fmt.Println("Bob")
}


Measured memory_bytes: 512
N = int(input())
h = [int(i) for i in input().split()]
m = max(h)
ans = 0
for i in range(1, m+1)[::-1]:
    pre = 0
    for j in range(len(h)):
        
        if h[j] == i:
            if pre != i:
                ans += 1
            pre = h[j]
            h[j] -= 1
        else:
            pre = h[j]
print(ans)


Measured memory_bytes: 3060
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double pi = acos(-1);
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
	for (auto &e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

//↑template↑




int a, b, c, ans, dis[1005][1005];
char area[1005][1005];

int bfs(int n, int m, int o, int p) {
	queue<pair<int, int>>q;
	q.emplace(n, m);
	memset(dis, -1, sizeof(dis));
	dis[n][m] = 0;

	while (!q.empty()) {
		pair<int, int>mon = q.front();
		q.pop();
		if (mon.first == o && mon.second == p) { return dis[mon.first][mon.second]; }

		for (int i = 0; i < 4; ++i) {
			int nn = mon.first + dy[i], mm = mon.second + dx[i];
			if (nn < 0 || mm < 0 || nn >= a || mm >= b || dis[nn][mm] != -1 || area[nn][mm] == 'X') { continue; }
			dis[nn][mm] = dis[mon.first][mon.second] + 1;
			q.emplace(nn, mm);
		}
	}

	return -1;
}

int main() {
	cin >> a >> b >> c;
	vector<pair<int, int>>v(c + 1);
	for (int i = 0; i < a; ++i) {
		for (int j = 0; j < b; ++j) {
			cin >> area[i][j];
			if (area[i][j] == 'S') { v[0] = make_pair(i, j); }
			else if (isdigit(area[i][j])) { v[area[i][j] - '0'] = make_pair(i, j); }
		}
	}

	for (int i = 1; i < c + 1; ++i) {
		ans += bfs(v[i - 1].first, v[i - 1].second, v[i].first, v[i].second);
	}

	cout << ans << endl;
}


Measured memory_bytes: 8024
from heapq import*

class median_tree(object):
    def __init__(self):
        self.lower_than_med=[]
        self.higher_than_med=[]
        self.count=0
        self.low=0
        self.high=0
        self.median=0
    def push(self,x):
        self.count=1-self.count
        if self.count:
            y=heappushpop(self.higher_than_med,x)
            heappush(self.lower_than_med,-y)
            self.low +=-y
            self.high+=x-y
        else:
            y=heappushpop(self.lower_than_med,-x)
            heappush(self.higher_than_med,-y)
            self.low -=x+y
            self.high-=y
        self.median=-self.lower_than_med[0]

from heapq import*
n=int(input())
m=median_tree()

B=0
for i in range(n):
    I=input()
    if I[0]=="1":
        a,b,c=map(int,I.split())
        B+=c
        m.push(b)
    else:
        print(m.median,m.count%2*m.median+B+m.low+m.high)


Measured memory_bytes: 11148
x = int(input())

if 400 <= x < 600:
    print(8)
elif 600 <= x < 800:
    print(7)
elif 800 <= x < 1000:
    print(6)
elif 1000 <= x < 1200:
    print(5)
elif 1200 <= x < 1400:
    print(4)
elif 1400 <= x < 1600:
    print(3)
elif 1600 <= x < 1800:
    print(2)
else:
    print(1)

Measured memory_bytes: 9116
N = int(input())
A = sorted(list(map(int, input().split())))

max_number = max(A) + 1
ng = [False] * max_number
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if not ng[ai]:
        counter += 1
        prev = ai
    for i in range(ai, max_number, ai):
        ng[i] = True
print(counter)

Measured memory_bytes: 32152
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

int main() {

	int sum = 0;
	int small = 114514;

	for (int i = 0; i < 4; i++) {
		int t;
		scanf("%d", &t);
		sum += t;
		small = min(small, t);
	}
	sum -= small;

	int t,u;
	scanf("%d", &t);
	scanf("%d", &u);

	printf("%d\n", sum + max(t, u));

	return 0;
}

Measured memory_bytes: 2756
def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    sumLs = sum(num_list)

    minCount = 10**9

    left = 0
    right = 0

    for i in range(n):
        left += num_list[i]
        right = sumLs - left
        minCount = min(abs(left-right),minCount)

    print(minCount)

if __name__ == '__main__':
    main()

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

int main() {
    int N; cin >> N;
    string S; cin >> S;

    string T = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for(int i=0; i<S.size(); i++){
        for(int j=0; j<T.size(); j++){
            if(S.at(i) == T.at(j)){
                S.at(i) = T.at(j+N);
                break;
            }
        }
    }

    cout << S << endl;
}


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


int main(){
   int n,m;
   cin>>n>>m;
   int p[100000],y[100000];
   vector<int> yd[100001];

   for (int i = 0; i < m; ++i){
      cin>>p[i]>>y[i];
      yd[p[i]].push_back(y[i]);
   }

   for (int i = 0; i < n; ++i){
      sort(yd[i+1].begin(),yd[i+1].end());
   }
   
   for (int i = 0; i < m; ++i){
      cout<<setfill('0')<<setw(6)<<p[i];
      cout<<setw(6)<<lower_bound(yd[p[i]].begin(),yd[p[i]].end(),y[i])-yd[p[i]].begin()+1;
      cout<<endl;
   }

}


Measured memory_bytes: 7808
def ten(arr,R,S,P):
  ans = 0
  num = 0
  length = len(arr)
  for i in range(length):
    if i == 0:
      if arr[i] == "r":
        ans = ans + P
        num = i
      elif arr[i] == "s":
        ans = ans + R
        num = i
      else:
        ans = ans + S
        num = i

    elif i > 0 and arr[i] != arr[i-1]:
      if arr[i] == "r":
        ans = ans + P
        num = i
      elif arr[i] == "s":
        ans = ans + R
        num = i
      else:
        ans = ans + S
        num = i
        
    elif i > 0 and arr[i] == arr[i-1] and int(num+1) != i:
      if arr[i] == "r":
        ans = ans + P
        num = i
      elif arr[i] == "s":
        ans = ans + R
        num = i
      else:
        ans = ans + S
        num = i
    
  return ans

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T = input()

T = list(T)
arr = []

for i in range(K):
  a = T[i::K]
  arr.append(a)

ans = 0

for i in arr:
  ans = ans + ten(i,R,S,P)

print(ans)


Measured memory_bytes: 12836
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Yukicoder solver = new Yukicoder();
        solver.solve(1, in, out);
        out.close();
    }

    static class Yukicoder {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int hitCount, outCount;
            int inning = in.nextInt();
            for (int i = 0; i < inning; i++) {
                int score = 0;
                hitCount = 0;
                outCount = 0;
                while (true) {
                    String setUp = in.next();

                    if (setUp.equals("HIT")) {
                        hitCount++;
                    } else if (setUp.equals("OUT")) {
                        outCount++;
                    }

                    if (setUp.equals("HOMERUN")) {
                        score += hitCount + 1;
                        hitCount = 0;
                    }

                    if (hitCount == 4) {
                        score++;
                        hitCount -= 1;
                    }
                    // out
                    if (outCount == 3) {
                        out.println(score);
                        break;
                    }
                }
            }
        }

    }
}




Measured memory_bytes: 26212
#include <bits/stdc++.h>
using namespace std;
typedef long long               ll;
const int mod = 1e9+7;
#ifndef M_PI
const double M_PI = acos(-1.0);
#endif

int h, w;
vector<string> grid;

int cur[2];

void dfs(int i, int j){
  if(grid[i][j] == '#'){
    ++cur[0];
  } else if(grid[i][j] == '.'){
    ++cur[1];
  } else {
    return;
  }
  char old = grid[i][j];
  grid[i][j] = 'u';
  if(i>0 && old != grid[i-1][j])
    dfs(i-1, j);
  if(i<h-1 && old != grid[i+1][j])
    dfs(i+1, j);
  if(j>0 && old != grid[i][j-1])
    dfs(i, j-1);
  if(j<w-1 && old != grid[i][j+1])
    dfs(i, j+1);
}

int main(){
  cin.sync_with_stdio(false);
  cin>>h>>w;
  grid.resize(h);
  for(int i=0; i<h; ++i){
    cin>>grid[i];
  }
  ll res = 0;
  for(int i=0; i<h; ++i){
    for(int j=0; j<w; ++j){
      cur[0] = cur[1] = 0;
      dfs(i, j);
      res += (ll)cur[0]*cur[1];
    }
  }
  cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 17920
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):
	if t[2*i]<=M:v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Measured memory_bytes: 24932
S = list(input())
T = list(input())

ans_list=[]
for i in range(len(S)-len(T)+1):
    S_temp=S.copy()
    serch_S=S_temp[i:i+len(T)]
    count=0
    for t in range(len(T)):
        if serch_S[t] in [T[t],'?']:
            count+=1
        else:
            break
        
        if count==len(T):
            S_temp[i:i+len(T)]=T

            for s in range(len(S_temp)):
                if S_temp[s]=='?':
                    S_temp[s]='a'
                    
            S_temp_str=''
            for s_t in S_temp:
                S_temp_str+=s_t

            ans_list.append(S_temp_str)

if len(ans_list)>0:
    
    ans_list.sort()
    ans=ans_list[0]
else:
    ans='UNRESTORABLE'
    
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

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

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

int N, M, K, Q, W, H, R, C;
int dp[51000];

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

    cin >> N >> M;
    vector<int> c(M);
    REP(i, M) cin >> c.at(i);

    REP(i, N + 1) dp[i] = INF;
    dp[0] = 0;
    REP(i, N + 1) {
        for (auto v : c) {
            if (i - v >= 0) chmin(dp[i], dp[i - v] + 1);
        }
    }
    cout << dp[N] << endl;

    return 0;
}



Measured memory_bytes: 3284
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int n, k; cin >> n >> k;
    rep(i,n) {int a; cin >> a;}
    int ans = 1;
    n -= k;
    while (n > 0){
        n -= k-1;
        ans++;
    } 
    cout << ans << endl;
}

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

using namespace std;

int main()
{
     int A,B,C;
     cin>>A>>B>>C;
    if(A>=1&&A<10&&B>=1&&B<10&&C>=1&&C<10){
     if((A==B&&A!=C&&B!=C)||(B==C&&B!=A&&C!=A)||(A==C&&A!=B&&C!=B)){
         cout<<"Yes";
     }
     else{
         cout<<"No";
     }
    }
   return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

bool cmp(char a,char b)
{
	return a>b;
}
int main()
{
	string s,t;
	
	cin>>s;
	cin>>t;
	
	sort(s.begin(),s.end());
	sort(t.begin(),t.end(),cmp);
	
	if(s<t)
		cout<<"Yes"<<endl;
	else 
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
def solve():
    N = int(input())
    A1 = list(map(int, input().split()))
    A2 = list(map(int, input().split()))

    mx = 0
    for i in range(N):
        tmp = sum(A1[:i+1]) + sum(A2[i:])
        mx = max(tmp, mx)
    
    print(mx)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 38512
from itertools import product

N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    l = list(map(int, input().split()))
    C.append(l[0])
    A.append(l[1:]) # コストと勉強分を分けて管理
# L = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for bit in product((0, 1), repeat=N):
    cost = 0
    study = [0] * M
    for i in range(N):
        if bit[i]:
            for m in range(M):
                study[m] += A[i][m]
            cost += C[i]

    if min(study) >= X: # 最小値が基準より大きければよい
        ans = min(ans, cost)

if ans == 10**9:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9160
using System;
using System.Collections.Generic;
namespace tst
{
    class Program
    {
        public static long min = Int64.MaxValue;
        public static long[] Kumi = new long[2];
        public static List<long> Prime(long x, List<long>L)
        {//素因数分解
            long i = 2;
            long tmp = x;
            while (i * i <= x)
            {
                if (tmp % i == 0)
                {
                    tmp /= i;
                    L.Add(i);
                }
                else
                {
                    i++;
                }
            }
            if (tmp != 1) L.Add(tmp);
            return L;
        }
        public static void Comb(long x, long y, List<long>L, int index)
        {//一番和の小さくなる組を見つける
            if (L.Count == index)
            {
                if (Math.Abs(x - y) < min)
                {
                    min = Math.Abs(x - y);
                    Kumi[0] = x;
                    Kumi[1] = y;
                }
                return ;
            }
            else
            {
                Comb(x * L[index], y, L, index + 1);
                Comb(x , y * L[index], L, index + 1);
            }
        }
        public static void Main()
        {
            long n = long.Parse(Console.ReadLine());
            List<long> L = new List<long>();
            L = Prime(n, L);
            if (L.Count == 1)
            {//素数だったら素因数に１を追加
                L.Insert(0,1);
            }
            //要素がすべて同じ数だったら特別な処理
            bool flag = true;
            long chk = L[0];
            for(int i=0; i<L.Count; i++)
            {
                if (chk != L[i]) flag = false;
            }
            if (!flag)
            {
                Comb(1, 1, L, 0);
            }
            else
            {
                if (L.Count % 2 == 0)
                {
                    Kumi[0] = (long)Math.Pow(L[0],  L.Count / 2);
                    Kumi[1] = Kumi[0];
                }
                else
                {
                    double val = L.Count / 2;
                    Kumi[0] = (long)Math.Pow(L[0],(int)Math.Floor(val));
                    Kumi[1] = Kumi[0]*L[0];
                }
            }
            Console.WriteLine(Kumi[0] + Kumi[1] - 2);
        }
    }
}

Measured memory_bytes: 11220
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


# FIXME: More smarter.
def calc_benefit(my_schedule, others_schedule, benefit_table, answer):
    score = 0

    if sum(my_schedule) == 0:
        return benefit_total

    for index, other_schedule in enumerate(others_schedule):
        count = 0

        for mine, other in zip(my_schedule, other_schedule):
            if mine == other == 1:
                count += 1
        score += benefit_table[index][count]
    return max(score, benefit_total)


# FIXME: More smarter.
def dfs(my_schedule, others_schedule, benefit_table, benefit_total, pos):
    if pos == 10:
        return calc_benefit(my_schedule, others_schedule, benefit_table, benefit_total)

    my_schedule[pos] = 0
    foo = dfs(my_schedule, others_schedule, benefit_table, benefit_total, pos + 1)
    my_schedule[pos] = 1
    bar = dfs(my_schedule, others_schedule, benefit_table, benefit_total, pos + 1)
    return max(foo, bar)


if __name__ == '__main__':
    shop_count = int(input())
    others_schedule = [list(map(int, input().split())) for _ in range(shop_count)]
    benefit_table = [list(map(int, input().split())) for _ in range(shop_count)]

    benefit_total = -1000000000
    my_schedule = [None] * (10)

    # See: https://www.youtube.com/watch?v=GWhYUxeDe70
    benefit_total = dfs(my_schedule, others_schedule, benefit_table, benefit_total, 0)
    print(benefit_total)


Measured memory_bytes: 3064
N, M = map(int, input().split())
pS = []
pS_dict = {i:[] for i in range(10**5)}
shutugen = set()
for i in range(M):
    tmp = input().split()
    if tmp[1] == "AC":
        pS_dict[int(tmp[0])].append(1)
    else:
        pS_dict[int(tmp[0])].append(0)
    shutugen.add(int(tmp[0]))
    
seitou = 0
penaru = 0
for i in shutugen:
    seitou_i = 0
    penaru_i = 0
    set_i = pS_dict[i]
    for s in set_i:
        if s == 0:
            penaru_i += 1
        else:
            seitou_i += 1
            break
    if seitou_i == 0:
        continue
    else:
        seitou += seitou_i
        penaru += penaru_i
print(seitou, penaru) 

Measured memory_bytes: 31976
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
map<string, int> mp;
P parse(int n, string s, int st) {
  int res = 0, tmp = 0, mul = 0;
  string now = "";
  for(int i=st;i<n;++i) {
    if(s[i] == '(') {
      P p = parse(n, s, i+1);
      if(p == make_pair(-1, -1)) {
        return {-1, -1};
      }
      tmp += p.first;
      i = p.second;
    } else if(s[i] == ')') {
      return {res, i};
    } else if('0' <= s[i] && s[i] <= '9') {
      mul = mul * 10 + (s[i] - '0');
      if(i == n-1 || s[i+1] < '0' || '9' < s[i+1]) {
        res += tmp * mul;
        tmp = 0;
        mul = 0;
      }
    } else {
      now.push_back(s[i]);
      if(!('a' <= s[i+1] && s[i+1] <= 'z')) {
        if(mp.find(now) == mp.end()) {
          return {-1, -1};
        } else {
          if(i == n-1 || s[i+1] < '0' || '9' < s[i+1]) res += mp[now];
          else tmp += mp[now];
          now = "";
        }
      }
    }
  }
  return {res, n};
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  while(1) {
    string s; cin >> s;
    if(s == "END_OF_FIRST_PART") break;
    int tmp; cin >> tmp;
    mp[s] = tmp;
  }
  while(1) {
    string s; cin >> s;
    if(s == "0") break;
    P p = parse((int)(s.size()), s, 0);
    cout << (p == make_pair(-1, -1) ? "UNKNOWN" : to_string(p.first)) << endl;
  }
}



Measured memory_bytes: 3236
import math
import decimal

list1 = input().split()
N = decimal.Decimal(list1[0])
M = decimal.Decimal(list1[1])
a = N*M

val_pi_d = decimal.Decimal(a)
val_floor_d = val_pi_d.quantize(decimal.Decimal('0'), rounding=decimal.ROUND_FLOOR)
print(int(val_floor_d))

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

using namespace std;

int main(){
  int n; cin >>n;
  int a,cnt=0;
  for(int i=0;i<n;++i) {
    cin >>a;
    if(a%2==0) cnt++;
  }
  cout<<cnt<<endl;
  
  return 0;
} 



Measured memory_bytes: 3092
from collections import deque
import numpy as np
H,W = map(int,input().split())
Maze=[list(input()) for i in range(H)]
ans=0
for hi in range(0,H):
    for wi in range(0,W):
        if Maze[hi][wi]=="#":
            continue
        maze1=[[0]*W for _ in range(H)]
        stack=deque([[hi,wi]])
        while stack:
            h,w=stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h,new_w=h+i,w+j
                if new_h <0 or new_w <0 or new_h >=H or new_w >=W:
                    continue
                elif Maze[new_h][new_w]!="#" and maze1[new_h][new_w]==0:
                    maze1[new_h][new_w]=maze1[h][w]+1
                    stack.append([new_h,new_w])
        
        maze1[hi][wi]=0
        ans=max(ans,np.max(maze1))
print(ans)

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

vector <int> to[200005];
vector <int> ans;

void dfs(int v,int p=-1){
  for(int u : to[v]){
    if(u==p) continue;

    ans[u] += ans[v];
    dfs(u,v);
  }
}


int main(){
  int n,q,i;
  cin >> n >> q;

  for(i=0;i<n-1;++i){
    int a,b;
    cin >> a >> b;
    --a;
    --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  ans.resize(n);
  for(i=0;i<q;i++){
    int p,x;
    cin >> p >> x;
    --p;
    ans[p] += x;
  }

  dfs(0);

  for(i=0;i<n;i++){
    cout << ans[i] << " ";
  }
  cout << "\n";

  return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

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

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

int main() {
	llong n, l;
	cin >> n >> l;
	llong sum = (n+1)*n/2 + n*l - n;

	llong mini = inf;
	for (int i = 0; i < n; ++i)
		if (abs(mini) > abs(i+l))
			mini = i+l;

	cout << sum - mini << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vec vector<ll>
#define vvec vector<vec>
#define f(i,o,n) for(auto i=o;i!=n;i++)
#define pb push_back
#define mk make_pair
#define all(x) (x.begin(), x.end())

int main()
{
    ll n,k;
    cin>>n>>k;
    vec a(n);
    f(i,0,n)
        cin>>a[i];
    // cout<<n<<k<<endl;
    if(n<=1)
        cout<<"0"<<endl;
    else if(n==2)
        cout<<(abs(a[1]-a[0]))<<endl;
    else
    {
        vec dp;
        dp.resize(n,1e10);
        dp[0] = 0;
        // dp[2] = min(dp[1]+abs(a[2]-a[1]), abs(a[2]-a[0]));
        f(i,1,n)
        {
            // cout<<i<<endl;
            f(j,1,k+1)
            {  
                if((i-j) >=0)
                    dp[i] = min(dp[i], abs(a[i]-a[i-j])+dp[i-j]);
                else
                    break;
            }
        }
        cout<<dp[n-1]<<endl;
    }
    
}

Measured memory_bytes: 4808
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());
        System.out.println(factorial(n));
    }
    
    private static long factorial(long n) {
        final long MOD = (long) (Math.pow(10, 9) + 7);
        long ans = 1;
        long temp = n;
        while (temp > 1) {
            ans = temp * ans % MOD;
            temp--;
        }
        return ans;
    }
}

Measured memory_bytes: 21716
#include <algorithm>  //min, max, sort, unique, fill
#include <iostream>
#include <numeric>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>  //pair, swap,
#include <vector>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using VI = vector<ll>;
using VB = vector<bool>;
using VP = vector<P>;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) for (ll i = 0; i < (n); i++)

static const ll kIntMax = numeric_limits<ll>::infinity();
static const double kFloatMax = numeric_limits<double>::infinity();

vector<ll> vi;

int main() {
  ll a, b, c;
  cin >> a >> b >> c;
  cout << ((a + b >= c) ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
parseInt(x::SubString{String})=parse(Int,x)
function f(A::Array{Int},B::Array{Int},T::Int)
	N=length(A)
	for i=1:N
		@inbounds if A[i]>=2T
			@inbounds A[i]-=2T
		end
		@inbounds if B[i]>=2T
			@inbounds B[i]-=2T
		end
	end
	sort!(A)
	sort!(B)
	cnt=0
	i1=i2=i3=i4=1
	for a=reverse(A)
		@inbounds while i1<=N&&B[i1]<T-a
			i1+=1
		end
		@inbounds while i2<=N&&B[i2]<2T-a
			i2+=1
		end
		@inbounds while i3<=N&&B[i3]<3T-a
			i3+=1
		end
		@inbounds while i4<=N&&B[i4]<4T-a
			i4+=1
		end
		cnt+=i4-i3+i2-i1
	end
	cnt&1
end
function main()
	N=parse(Int,readline())
	A=map(parseInt,split(readline()))
	B=map(parseInt,split(readline()))
	ans=0
	for k=28:-1:0
		ans+=f(A,B,1<<k)*(1<<k)
	end
	println(ans)
end
main()


Measured memory_bytes: 162684
N,M = list(map(int, input().split()))
S = list(map(int, input().split())) #N
T = list(map(int, input().split())) #M

MOD = 10**9+7

dp = [[0]*M for _ in range(N)]
# dp[n][m] Sのn文字目，Tのm文字目までの場合の数

dp[0][0] = 1 + int(S[0] == T[0])

for i in range(1,N):
  dp[i][0] = dp[i-1][0] + int(S[i]==T[0])
  
for j in range(1,M):
  dp[0][j] = dp[0][j-1] + int(T[j]==S[0])
  
for n in range(1,N):
  for m in range(1,M):
    dp[n][m] = (dp[n-1][m] + dp[n][m-1] - dp[n-1][m-1] + dp[n-1][m-1]*int(S[n]==T[m]))%MOD
    

#print(dp)
print(dp[N-1][M-1])

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

int main(){
    int a, b;
    cin >> a >> b;

    cout << std::fixed << std::setprecision(5) << a/b <<  " " << a%b << " " << (double)a/(double)b << endl;
    return 0;
}


Measured memory_bytes: 3288
use std::io;

fn read_line()-> String {
    let mut s = String::new();
    let _ = io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn to2 (s: &Vec<i32>,mut c:i32) -> i32 {
	if s.iter().filter(|i|*i % 2 != 0).count() > 0 {
		c
	}else{
		let s = s.iter().map(|i|i/2).collect::<Vec<i32>>();
		c+=1;
		to2(&s,c)
	}
}

fn main() {
	let _ = read_line();
	let s = read_line().split_whitespace().map(|e|e.parse().unwrap())
	.collect::<Vec<i32>>();
	println!("{:?}",to2(&s,0));
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(){
  int i,j,f=0,c=0,w,h,d[110][110]={0};
  for(i=0;i<110*110;i++)d[i/110][i%110]=2;
  scanf("%d %d",&h,&w);
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++)scanf("%d",&d[i][j]);
  }
  while(f-2){
    f=f==0?1:2;//printf("%d\n",f);
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	if(d[i-1][j]-2||d[i][j-1]-2&&d[i][j+1]-2)continue;
	if(d[i][j]==1||d[i][j]==0&&f==2){
	  if(f-2)c++;
	  f=0;
	  d[i][j]=2;
	  if(d[i][j-1]-2)d[i][j-1]^=1;
	  if(d[i+1][j]-2)d[i+1][j]^=1;
	  if(d[i][j+1]-2)d[i][j+1]^=1;
	}
      }
    }
  }
  printf("%d\n",c);
  return 0;
}
 

Measured memory_bytes: 656
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

struct Z_algorithm
{
	vector< int > prefix;

	void build(const string &s)
	{
		prefix.assign(s.size(), 0);
		for (int i = 1, j = 0; i < s.size(); i++) {
			if (i + prefix[i - j] < j + prefix[j]) {
				prefix[i] = prefix[i - j];
			}
			else {
				int k = max(0, j + prefix[j] - i);
				while (i + k < s.size() && s[k] == s[i + k]) ++k;
				prefix[i] = k;
				j = i;
			}
		}
		prefix[0] = (int)s.size();
	}

	int operator[](const int k) const
	{
		return (prefix[k]);
	}

	size_t size()
	{
		return(prefix.size());
	}
};


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

	cin >> N;
	string s;
	cin >> s;
	string t;
	int ans = 0;
	for (int i = N - 1; i >= 0; i--) {
		t = s[i] + t;
		Z_algorithm z;
		z.build(t);
		for (int j = 1; j < z.prefix.size(); j++) {
			if (j >= z.prefix[j])ans = max(ans, z.prefix[j]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#Z-Algorithm
#文字列が与えられた時、各 i について「S と S[i:] の最長共通接頭辞の長さ」を記録した配列 A を O(len(S)) で構築するアルゴリズム
#s : 文字列
#あとで要復習！
def z_algorithm(s):
    N = len(s)
    z_alg = [0]*N
    z_alg[0] = N
    i = 1
    j = 0
    
    while i < N:
        while i+j < N and s[j] == s[i+j]: # 伸ばせるだけ伸ばす
            j += 1
        z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k+z_alg[k] < j: # 今までで求められている場所ならば計算を省略
            z_alg[i+k] = z_alg[k]
            k += 1
        i += k
        j -= k
    return z_alg

n = int(input())
S = input()
max_ = 0
for i in range(n):
    k = S[i:len(S)]
    li = z_algorithm(k)
    for j in range(len(li)):
        if li[j] < j+1:
            max_ = max(max_, li[j])
print(max_)

Measured memory_bytes: 49244
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    double t,x;
    cin>>t>>x;
    printf("%.3f",t/x);


    return 0;
}


Measured memory_bytes: 636
#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
const Int Inf = 1e17;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define Pr(t) priority_queue<t>
#define gPr(t) priority_queue<t,vector<t>,greater<t>>
#define V(t) vector<t>
#define rep(i,n) for(int(i)=0; i<n; i++)
#define rer(i,l,r) for(int i=l; i<=r; i++)
#define gnr(i,l,r) for(int i=r; i>=l; i--)
#define eb emplace_back
#define pri1(a) cout<<(a)<<'\n'
#define pri2(a,n) {rep(pri2i,n-1)cout<<a[pri2i]<<' '; cout<<a[n-1]<<'\n';}
#define prip(p) cout<<p.fi<<' '<<p.se<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }

  bool same(int x, int y){
    return find(x) == find(y);
  }
};

Int n,m,_,x,y,q;
string s,sb;
bool ok;
char ch;

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

  cin>>n>>m; UnionFind a(2*n);
  rep(i,m){
    cin>>x>>y;
    a.unite(--x,--y+n); a.unite(x+n,y);
  }
  if(a.same(0,n))pri1(n*(n-1)/2-m);
  else{
    rep(i,n)q+=a.same(0,i);
    pri1(q*(n-q)-m);
  }
}

Measured memory_bytes: 1024
H, W = map(int, input().split())

s = [input() for i in range(H)]

for y in range(H):
  for x in range(W):
    if x-1 < 0 or y-1 < 0 or x+1 > W-1 or y+1 > H-1:
      continue
    if s[y][x] == '#' and s[y+1][x] != '#' and s[y-1][x] != '#' and s[y][x+1] != '#' and s[y][x-1] != '#':
      print("No")
      exit()
      
print("Yes")


Measured memory_bytes: 3064
int dif(int a, int b){return a<b?b-a:a-b;}
char *s[]={"No","Yes"};
int a, b, c, d;
char f;
int main(){
  scanf("%d%d%d%d", &a, &b, &c, &d);
  f = dif(a,c)<=d || (dif(a,b)<=d && dif(c,b)<=d);
  puts(s[f]);
}


Measured memory_bytes: 128
# coding: utf-8
import math

while True:
    n = int(input())
    
    if n == 0:
        break

    m = 0 # ?????????
    m2 = 0 # 2???????????????
    
    s = map(int,input().split())

    for i in s:
        m += i
        m2 += i ** 2

    m /= n
    m2 /= n

    sd = math.sqrt(m2 - m**2)

    print("{:.8f}".format(sd))

Measured memory_bytes: 7716
package main

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

func main() {
	A := nextInt()
	B := nextInt()
	C := nextInt()
	cnt := B / A
	if cnt < C {
		fmt.Println(cnt)
	} else {
		fmt.Println(C)
	}
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextFloat() float64 {
	sc.Scan()
	f64, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}

	return f64
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

// ---------- Util.


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl '\n'
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vpi vector<pi>
 
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int MX = 3e5 + 5;
const ld PI = 4 * atan((ld)1);

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	int a[n];
	long double pr=1;
	for(int i=0;i<n;i++){
		cin>>a[i];
		pr*=a[i];
	}
	long double sum=0;
	for(int i=0;i<n;i++)
		sum+=pr/a[i];
	cout<<pr/sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline int read() {
    register int x = 0, f = 1;
    register char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return x * f;
}
const int N = 4e5 + 5;
int n, m, now, v[N], a[N], nex[N], pre[N], head[N];
void add(int x, int y) {
    nex[++now] = head[x];
    head[x] = now, v[now] = y;
}
queue<int> que;
int main(){
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        add(x, y), add(y, x);
    }
    que.push(1), a[1] = 1;
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (int i = head[x]; i; i = nex[i])
            if (!a[v[i]]) {
                a[v[i]] = 1, que.push(v[i]);
                pre[v[i]] = x;
            }
    }
    for (int i = 1; i <= n; i++)
        if (!a[i]) {
            puts("No");
            return 0;
        }
    puts("Yes");
    for (int i = 2; i <= n; i++)
        printf("%d\n", pre[i]);
    return 0;
}

Measured memory_bytes: 8100
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

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

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

# 1個の変える先は他のやつの最大公約数にすればいいので、
# N-1個の最大公約数の最大値を求める
lefts = list(itertools.accumulate(A, gcd))
rights = list(itertools.accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, rights[1])
    elif i == N - 1:
        ans = max(ans, lefts[-2])
    else:
        ans = max(ans, gcd(lefts[i - 1], rights[i + 1]))
print(ans)


Measured memory_bytes: 22468
# include <bits/stdc++.h>
# define rep(i, n) for (ll i = 0; i < (n); i++)
# define reps(i, n) for (ll i = 1; i <= (n); i++)
# define foreps(i, m, n) for (ll i = (m); i < (n); i++)
# define len(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const long long mod = 1e9 + 7;
const long long inf = 1e18;

int main() {
    ll N; cin >> N;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A[i] >> B[i];

    vector<ll> C(N + 1, 0);
    for (ll i = N - 1; i >= 0; i--) {
        A[i] += C[i + 1];
        ll modd = A[i] % B[i];
        ll need = 0;
        if (modd != 0) need = B[i] - modd;
        C[i] = C[i + 1] + need;
    }
    cout << C[0] << endl;
}

Measured memory_bytes: 5592
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int c(int a){return a/100*60+a%100;}
int K[4000];
int main(){
  int n,s,g;
  while(cin>>n>>s>>g,n){
    memset(K,0,sizeof(K));
    s=c(s);
    g=c(g);
    r(i,n){
      int t;
      cin>>t;
      while(t--){
        int a,b;
        cin>>a>>b;
        a=c(a);
        b=c(b);
        K[a]++;
        K[b]--;
      }
    }
    int ans=0;
    int sum=0;
    int ch=0;
    for(int i=s;i<g;i++){
      sum+=K[i];
      if(sum!=n)ans++;
      else ans=0;
      ch=max(ch,ans);
    }
    cout<<ch<<endl;
  }
}


Measured memory_bytes: 3004
<?php
//Request Question
function getq($get_word=null){
	if($get_word===null){
		return str_replace("\n","",fgets(STDIN));
	}else if($get_word===1){
		return explode(" ",str_replace("\n","",fgets(STDIN)));
	}
}

/*		START		*/
$temp = getq(1);
$A=$temp[0];
$B=$temp[1];
$C=$temp[2];
$X=$temp[3];
$Y=$temp[4];
$total=0;
$l=min($X,$Y);
$t_a=array();
//とりあえずmin埋め
if($C*2<$A+$B){
	for ($i=0; $i <$l; $i++) { 
		$total+=$C*2;
		$X-=1;
		$Y-=1;
	}
}
while(0<$X){
	$X-=1;
	$total+=$A;
}
while(0<$Y){
	$Y-=1;
	$total+=$B;
}
array_push($t_a,$total);

$A=$temp[0];
$B=$temp[1];
$C=$temp[2];
$X=$temp[3];
$Y=$temp[4];
$total=0;
$l=min($X,$Y);
//A+B ture
array_push($t_a,($A*$X+$B*$Y));
array_push($t_a,($C*2*max($X,$Y)));
echo min($t_a)."\n";
?>

Measured memory_bytes: 4604
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

// typedef
typedef long long ll;

// container util
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(c) int((c).size())
#define EACH(i,c) for(auto (i)=(c).begin(); (i)!=(c).end(); ++(i))
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))

// repetition
#define FOR(i,m,n) for(ll (i) = ((ll) m); (i) < ((ll) n); ++(i))
#define RFOR(i,m,n) for(ll (i) = ((ll) (m)-1); (i) >= ((ll) n); --(i))
#define REP(i,n) FOR(i,0,n)

// i/o
#define TFOUT(b,t,f) cout << ((b)? (t) : (f)) << endl

// constant
const double    EPS     = 1e-10;
const int       INFTY   = (1<<21);
const ll        MOD     = (ll) 1e9+7;

// clear memory
#define CLR(a) memset((a),0,sizeof(a))

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << " " << __FILE__ << endl

int solve(int n, int m, int s) {
    int N = n*n;
    int M = m - N;
    int S = s - N*(N+1)/2;
    vector<int> dp(N*(S+1), 0);
    REP(i, N) {
        REP(j, S+1) {
            if (i == 0) {
                dp[i*(S+1)+j] = (j <= M? 1 : 0);
                continue;
            }
            int val = dp[(i-1)*(S+1)+j];
            if (j-i-1 >= 0)   val += dp[i*(S+1)+j-i-1];
            if (j-i-1-M >= 0) val -= dp[(i-1)*(S+1)+j-i-1-M];
            dp[i*(S+1)+j] = val % 100000;
        }
    }
    return *(dp.end() - 1);
}

int main() {
    while (true) {
        int n, m, s; cin >> n >> m >> s;
        if (n == 0 && m == 0 && s == 0) break;
        cout << solve(n, m, s) << endl;
    }
    return 0;
}
/*
Bingo
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537

本問題では, Sを互いに異なるN=n^2個の1以上M以下の数に分割できれば良い.

「互いに異なる」の部分: 後から1からNを足す.
M-N(N-1)をN個に分割する分割の仕方を考えてからソートしてそれぞれ1からNを足せば良い.

「M以下の部分」: 分割数を少し変えてQ(n, k)を数nを0以上M以下のk個の自然数の和として表す組み合わせ
とする.この時
Q(n, k) = Q(n, k-1) + (Q(n-k, k) - Q(n-k-m, k))
Q(n, k-1): k個の自然数のいずれかに0を含むものは,
k-1個の自然数によってnが表せた後, そこに0をくわえている場合だと考えることができる.
Q(n-k, k) - Q(n-k-M, k): k個の自然数のいずれにも0を含まないものは,
n-kをk個の0以上の数の和で表した後に, k個の数字全てに一斉に1をくわえることで
全て作ることができる. ただし, Mを1つ以上含むものは, 一斉に1をくわえると,
M+1ができてしまってM以下という制約に合わなくなるので除かなくてはいけない.
Mを1つ以上含むものの組み合わせの総数を考える.この組み合わせは
(0個以上Mを含んで)n-k-Mを0以上M以下のk-1個の自然数に分割する組み合わせに, 1つMをくわえたもの
となる.この組み合わせの総数はQ(N-k-M, k-1)そのものである.

本問題では後から最大でNを加えることにして「互いに異なる」を実現するから,
M以下ではなくてM-N以下dで考えておく必要がある.
*/



Measured memory_bytes: 3376
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Measured memory_bytes: 68232
/*
 * Author : Sadi
 * Mon 06/07/2020
 * 14:32:03.56
 */
#include <iostream>
#include <cstdio>
#include <climits>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE

    string s;
    cin >> s;
    set<char> st;
    for(int i = 0; i < (int) s.size(); ++i) {
    	st.insert(s[i]);	
    }
    if(st.size() == 2) {
    	cout << "Yes" << endl;
    }
    else {
    	cout << "No" << endl;
    }
    return 0;
}


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

int main() {
	int h, w;
	bool flag;
	while(h+w){
		flag = true;
		cin >> h >> w;
		for(int i=0; i < h; i++){
			for(int j =0; j < w; j++){
				if(flag)cout << "#";
				else cout << ".";
				flag = !flag;
			}
			cout << endl;
			if(w%2-1)flag = !flag;
		}
		if(h+w)cout<<endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#include <cmath>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
int main(){
    char a[100000];

    ss(a);
    int lena = len(a);
    if(lena == 2){
        puts(a);

    }else if(lena == 3){
        char temp =a[0];
        a[0] = a[2];
        a[ 2] = temp;
        puts(a);
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int con = scan.nextInt();
		int[] num = new int[con];
		for(int i = 0; i < con; i++){
			num[i] = scan.nextInt();
		}
		Sort s = new Sort(num);
		s.printSort();
		s.insertionSort();
	}

}

class Sort{
	private int[] sorted;
	
	Sort(int[] sorted){
		this.sorted = new int[sorted.length];
		for(int i = 0; i < sorted.length; i++){
			this.sorted[i] = sorted[i];
		}
	}
	
	public void insertionSort(){
		int v, j;
		for(int i = 1; i < this.sorted.length; i++){
			v = this.sorted[i];
			j = i - 1;
			while(j >= 0 && this.sorted[j] > v){
				this.sorted[j + 1] = this.sorted[j];
				j--;
			}
			this.sorted[j + 1] = v;
			printSort();
		}
	}
	
	public void printSort(){
		for(int i  = 0; i < this.sorted.length - 1; i++){
			System.out.print(this.sorted[i] + " ");
		}
		System.out.println(this.sorted[this.sorted.length - 1]);
	}
}



Measured memory_bytes: 32148