akhauriyash/Code-Regression huggingface dataset:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

a,b = imn()

if a > 0 and b > 0:
    print('Positive')
elif a < 0 and b < 0:
    print('Positive' if (-a+b+1) % 2 == 0 else 'Negative')
else:
    print('Zero')

Measured memory_bytes: 5300
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int a,b;
    cin >>a>>b;
    cout << (a+b+1)/2 << endl;



}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N; cin>>N;
  vector<vector<pii>> A(N);
  rep(i,1,N){
    int X,Y,Z; cin>>X>>Y>>Z;
    A[X-1].pb(mp(Y-1,Z));
    A[Y-1].pb(mp(X-1,Z));
  }
  queue<pii> Q;
  vector<bool> F(N,1);
  F[0]=0;
  vi ans(N);
  Q.push(mp(0,0));
  while(Q.size()>0){
    int X=Q.front().first,Y=Q.front().second;
    Q.pop();
    rep(i,0,A[X].size()){
      int Z=Y+A[X][i].second,P=A[X][i].first;
      if(F[P]){
        Q.push(mp(P,Z));
        ans[P]=Z%2;
        F[P]=0;
      }
    }
  }
  rep(i,0,N) cout<<ans[i]<<endl;
  }


Measured memory_bytes: 8704
s = list(input())
t = list(input())

len_s = len(s)
len_t = len(t)
count = 0
biggest = 0

for i in range(len_s-len_t+1):
  now = s[i:i+len_t]

  for j in range(len_t):
    if t[j] == now[j]:
      count += 1
      
  if biggest < count:
    biggest = count
    count = 0
  else:
    count = 0
    
print(len_t - biggest)

Measured memory_bytes: 67844
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#include<bitset>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int A,B;
	scan(A);scan(B);
	if(A+B>=10) prin("error");
	else prin(A+B);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

int main(){

    int num;
    int a,b,c,d;

    cin >> num;

    a = num /1000;
    num -= a * 1000;
    b = num / 100;
    num -= b * 100;
    c = num / 10;
    num -= c *10;
    d = num;

    if(a == b || b == c || c == d)cout << "Bad" << endl;
    else cout << "Good" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q, p, kake;
U_MAP mp;

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

  cin >> n >> p >> s;
  if (p == 2 || p == 5) {
    rrrep(i, n - 1, 0) {
      tmp = s[i] - '0';
      if (tmp % p == 0) ans += i + 1;
    }
    Cout(ans);
  } else {
    kake = 1;
    rrrep(i, n - 1, 0) {
      tmp += (s[i] - '0') * kake;
      kake *= 10;
      kake %= p;
      tmp %= p;
      if (tmp != 0) {
        ans += mp[tmp];
        mp[tmp]++;
      } else {
        mp[tmp]++;
        ans += mp[tmp];
      }
      // cout << tmp << "\n";
    }
    Cout(ans);
  }
  return 0;
}

Measured memory_bytes: 916
#include<iostream>
using namespace std;
int main() {
	int i, j, H, W;
	while (1) {
		cin >> H >> W;

		if (H == 0 && W == 0) { break; }

		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {

				if (i == 0 || j == 0 || i == H-1 || j == W-1) {
					cout << "#";
				}
				else {
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 2984
n,m=map(int,input().split())
a={i+1:list(map(int,input().split())) for i in range(n)}
b=[int(input()) for i in range(m)]
for i in range(n):
    ci=0
    for j in range(m):
        cij=a[i+1][j]*b[j]
        ci+=cij
    print(ci)


Measured memory_bytes: 6020
<?php
fscanf(STDIN, "%d", $N);
$a = explode(" ", trim(fgets(STDIN)));
$b = explode(" ", trim(fgets(STDIN)));

$sav = 0;

$total = array_sum($b) - array_sum($a);

// echo $total . "\n";

// sort($a);
// sort($b);

// echo implode(" ", $a) . "\n";
// echo implode(" ", $b) . "\n";

foreach ($a as $k => $v) {
    if ($a[$k] > $b[$k]) {
        $sav -= abs($a[$k] - $b[$k]);
    } else {
        $sav += floor(abs($a[$k] - $b[$k]) / 2);
    }
}

// echo $sav . "\n";

if ($sav >= 0) {
    echo "Yes" . "\n";
} else {
    echo "No" . "\n";
}

Measured memory_bytes: 6648
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll n,m;
    cin >> n>> m;
    vector<ll>a(m);
    ll total = 0;
    REP(i,m){
        cin >> a[i];
        total += a[i];
    }
    cout << max(n-total,-1ll) << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <numeric>
#include <set>
#include <iomanip>
#include <functional>
#define FOR(i, a, n) for (long long i = (a); i < (n); i++)
#define REP(i, n) for(long long i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
using namespace std;

typedef long long ll;

long long myGcd(long long a, long long b)
{
	if (a % b == 0)return b;
	return myGcd(b, a % b);
}

int myGcd(int a, int b)
{
	if (a % b == 0)return b;
	return myGcd(b, a % b);
}

long long myLcm(long long a, long long b)
{
	return a * b / myGcd(a, b);
}

int myLcm(int a, int b)
{
	return a * b / myGcd(a, b);
}


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

	int K;
	string S;

	cin >> K >> S;

	if (S.length() > K)
	{
		string tmp = S.substr(0, K);
		cout << tmp << "..." << endl;
	}
	else
	{
		cout << S << endl;
	}

	return 0;
}

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		for k, sw in enumerate(v):
			st = set()
			for i in range(n):
				if l[i] == 1:
					st.add(i + 1)
			# print(st)
			if len(sw.intersection(st)) % 2 == p[k]:
				c += 1
		# print("c: {}".format(c))
		if c == m:
			count += 1
		# print(l)
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()


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

int main() {
  int a,b,c,x,sum=0;
  cin>>a>>b>>c>>x;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      for(int k=0;k<=c;k++){
        if(500*i+100*j+50*k==x){
          sum++;
        }
      }
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  string S;
  int K;
  cin >> N >> S >> K;
  for (int i = 0; i < N; i++){
    if (S[i] != S[K - 1]){
      cout << '*';
    } else {
      cout << S[i];
    }
  }
}

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

#define pb push_back
#define se second
#define fi first

using namespace std;

long long n, a[(int)1e5 + 7][3], d[(int)1e5 + 7][3];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    d[1][1] = a[1][1];
    d[1][2] = a[1][2];
    d[1][3] = a[1][3];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= 3; j++)
            for(int h = 1; h <= 3; h++)
                if(h != j)
                    d[i][j] = max(d[i][j], d[i - 1][h] + a[i][j]);
    cout << max(d[n][1], max(d[n][2], d[n][3]));
}


Measured memory_bytes: 4992
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#define MOD (1e9+7)

using namespace std;

string S;

void solve(){
  /*
  dp[何番目の文字まで確認したか][状態]
  状態 0: ABCのうち何も決めていない
  状態 1: Aの位置のみ確定済み
  状態 2: ABの位置のみ確定済み
  状態 3: ABCの位置確定済み
  */
  vector<vector<long>> dp = vector<vector<long>>(S.size()+1,vector<long>(4,0));
  dp[0][0] = 1;
  for(int i = 0; i < S.size(); i++){
    switch (S[i]) {
      case 'A':
        dp[i+1][0] = dp[i][0] ;
        dp[i+1][1] = dp[i][1] + dp[i][0] ;
        dp[i+1][2] = dp[i][2] ;
        dp[i+1][3] = dp[i][3] ;
        break;
      case 'B':
        dp[i+1][0] = dp[i][0] ;
        dp[i+1][1] = dp[i][1] ;
        dp[i+1][2] = dp[i][2] + dp[i][1] ;
        dp[i+1][3] = dp[i][3] ;
        break;
      case 'C':
        dp[i+1][0] = dp[i][0] ;
        dp[i+1][1] = dp[i][1] ;
        dp[i+1][2] = dp[i][2] ;
        dp[i+1][3] = dp[i][3] + dp[i][2] ;
        break;
      case '?':
        dp[i+1][0] = dp[i][0] * 3;
        dp[i+1][1] = 3 * dp[i][1] + dp[i][0] ;
        dp[i+1][2] = 3 * dp[i][2] + dp[i][1] ;
        dp[i+1][3] = 3 * dp[i][3] + dp[i][2] ;
        break;
    }
    for(int j = 0; j < 4; j++) dp[i+1][j] = dp[i+1][j] % (int)MOD ;

  }
  cout << dp[S.size()][3] << endl;
}
int main(){
  cin >> S;
  solve();
  return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main() {
    int n;
    cin >> n;
    unordered_map<string,int> mp;
    rep(i,n){
        string s;
        cin >> s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    ll ans = 0;
    for(auto&p : mp){
        int s = p.second;
        ans += (ll) s*(s-1)/2;
    }
    cout<<ans<<endl;
}

 

Measured memory_bytes: 10660
import sys

input = sys.stdin.readline
N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
g = [[] for _ in range(N)]
for a, b, w in uvw:
    g[a-1].append((b-1, w))
    g[b - 1].append((a - 1, w))

children = [[] for _ in range(N)]
colors = [None]*N
q = [(0, None, 0)]  # nodeid, parent, color
while len(q) > 0:
    v, p, c = q.pop()
    colors[v] = c
    for u, w in g[v]:
        if u != p:
            c_ = (c+(w%2))%2
            q.append((u, v, c_))
            children[v].append(u)
for c in colors:
    print(c)


Measured memory_bytes: 111712
#include <bits/stdc++.h>
using namespace std;
int A,B,ans;
int dp[2][123456];
int main(){
    cin>>A>>B;
    B/=100;
    fill(dp[0],dp[0]+123456,1e9);
    fill(dp[1],dp[1]+123456,1e9);
    dp[0][0]=0;
    for(int i=1;i<=A;i++){
        int x,y;
        cin>>x>>y;
        y/=100;
        for(int j=0;j<123456;j++){
            for(int k=0;k<x;k++){
                int sum = j+k*i;
                if(sum<123456){
                    dp[1][sum]=min(dp[1][sum],dp[0][sum]);
                    dp[1][sum]=min(dp[1][sum],dp[0][j] + k);
                }
            }
        }
        for(int j=0;j<123456;j++){
            int sum = j+x*i+y;
            if(sum<123456){
                dp[1][sum]=min(dp[1][sum],dp[0][sum]);
                dp[1][sum]=min(dp[1][sum],dp[0][j] + x);
            }
        }
        swap(dp[0],dp[1]);
    }
    cout<<*min_element(dp[0]+B,dp[0]+123456)<<'\n';
    return 0;
}

Measured memory_bytes: 1152
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using E = System.Linq.Enumerable;
using System.IO.Pipes;
using System.Threading;

class Program
{
    static char[] abc = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
    static long mod = 1000000007;
    static void Main(string[] args)
    {
        //var N = long.Parse(Console.ReadLine());
        var NK = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        var N = NK[0];
        var K = NK[1];
        var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        long ans1 = 0;
        long ans2 = 0;
        for (int i = 0; i < N; i++)
        {
            var tentou = 0;
            var all = 0;
            for (int j = 0; j < N; j++)
            {
                if(A[j] < A[i])
                {
                    if(i < j)
                    {
                        tentou++;
                    }
                    all++;
                }
            }
            ans1 += tentou;
            ans2 += all;
        }
        ans1 *= K;
        ans1 %= mod;
        ans2 *= (K * (K - 1) / 2)%mod;
        ans2 %= mod;
        Console.WriteLine((ans1 + ans2)%mod);

    }

}

Measured memory_bytes: 28412
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll LINF = ll(1e18);

ll func(ll num){
  num++;
  ll div=1LL;
  ll ret=0LL;
  for(int i=0;i<40;i++){
    ll cnt=0;
    div *= 2;
  	cnt += (num/div)*(div/2);
    cnt += max(0LL, (num%div)-(div/2));
    if(cnt%2!=0LL){
      ret += div/2;
    }
  }
  return ret;
}

int main(){
  ll a, b;cin>>a>>b;
  cout<<(func(b)^func(a-1))<<endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<vector<ll>> adj(n, vector<ll>(n));
    vector<vector<ll>> mat(n, vector<ll>(n, -1));
    rep(i, n) rep(j, n) cin >> adj[i][j];

    bool shortest = true;
    rep(k, n) rep(i, n) rep(j, n) {
        if(adj[i][j] > adj[i][k] + adj[k][j]){
            shortest = false;
            break;
        }
        else if(k!=i && k!=j&&adj[i][j] == adj[i][k] + adj[k][j]){
            mat[i][j] = k;
        }
    }
    if(!shortest){
        puts("-1");
        return 0;
    }
    ll dist = 0;
    rep(i,n) rep(j,n){
        if (mat[i][j] != -1) continue;
        dist += adj[i][j];
    }
    cout << dist / 2 << endl;
}

Measured memory_bytes: 1664
#include <iostream>

using namespace std;

int main (){
    int a, b, i;
    for(i=0; i<3000; i++){
    cin>>a>>b;
    if(a==0&&b==0){
    return 0;
    }
    else if(b>=a){
    cout<<a<<" "<<b<<endl;
    }
    else{
    cout<<b<<" "<<a<<endl;
    }
    }
    cout<<endl;
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int dp[111][21];

signed main(){
    int N;
    cin>>N;
    int a;cin>>a;
    dp[0][a]=1;
    for(int i=1;i+1<N;i++){
        cin>>a;
        for(int j=0;j<=20;j++){
            if(j+a<=20)dp[i][j+a]+=dp[i-1][j];
            if(j-a>=0)dp[i][j-a]+=dp[i-1][j];
        }
    }
    cin>>a;
    cout<<dp[N-2][a]<<endl;
    return 0;
}

Measured memory_bytes: 1172
#include <stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[N][N];
int color[N],d[N],f[N],tt;

//递归函数实现DFS
void dfs_visit(int u){
    int v;
    color[u]=GRAY;
    d[u]=++tt;//最初访问
    for(v=0;v<n;v++){
        if( M[u][v]==0)continue;
        if( color[v]==WHITE){
            dfs_visit(v);
        }
    }
    color[u]=BLACK;
    f[u]=++tt;//访问结束
    
}

void dfs(){
    int u;
    //初始化
    for(u=0;u<n;u++){
        color[u]=WHITE;
    }
    tt=0;
    
    for(u=0;u<n;u++){
        if( color[u]==WHITE)dfs_visit(u);
    }
    for(u=0;u<n;u++){
        printf("%d %d %d\n",u+1,d[u],f[u]);
    }
}

int main(int argc, const char * argv[]) {
//    printf("A");
    int u,v,k,i,j;
    
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            M[i][j]=0;
        }
    }
    for(i=0;i<n;i++){
        scanf("%d %d",&u,&k);
        u--;
        for(j=0;j<k;j++){
            scanf("%d",&v);
            v--;
            M[u][v]=1;
        }
    }
    dfs();
    return 0;
}



Measured memory_bytes: 2108
N, K = map(int, input().split())
p = list(map(int, input().split()))

A = [p[0]]
for i in range(N-1):
	A.append(A[i] + p[i+1])

res = 0
for i in range(N - K):
	res = max(A[i + K] - A[i], res)

if N == K:
	res = A[N-1]

print( (res + K) / 2)

Measured memory_bytes: 76040
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int a;
  cin >> a;

  cout << a + a * a + a * a * a << endl;
}


Measured memory_bytes: 3564
#include <iostream>
#include <algorithm>
#include <sstream>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

string itos (int n )
{
	stringstream ss;
	ss << n;

	return ss.str();
}

void x2n (string & s, int n )
{
	string cn = itos (n );
	while (s.find ('X' ) != string::npos ){
		s = s.replace(s.find('X'), 1, cn );
	} // end while
}

string longlongadd (string str1, string str2 )
{
	string res = "";
	
	reverse (str1.begin(), str1.end() );
	reverse (str2.begin(), str2.end() );
	int len1 = str1.length();
	int len2 = str2.length();

	while (len1 != len2 ){
		if (len1 < len2 ){
			str1 += '0';
			len1 = str1.length();
		}else if (len1 > len2 ){
			str2 += '0';
			len2 = str2.length();
		} // end if
	} // end while

	bool carry = false;
	for (int i = 0; i < len1; i++ ){
		int num1 = str1[i] - '0';
		int num2 = str2[i] - '0';
		int sum = num1 + num2;

		sum += (carry ? 1 : 0 );

		if (sum < 10 ){
			res += sum + '0';
			if (carry){
				carry = false;
			} // end if
		}else{
			sum %= 10;
			res += sum + '0';
			carry = true;
		} // end if
	} // end for

	if (carry){
		res += '1';
	} // end if

	reverse (res.begin(), res.end());

	return res;
}

int main()
{
	string str = "";
	while (cin >> str ){
		string a = str.substr (0, str.find('+') );
		string b = str.substr (str.find ('+' )+1, str.find ('=' ) - str.find('+') - 1);
		string c = str.substr (str.find ('=')+1 );
		bool found = false;
		for (int i = 0; i < 10;  i++ ){
			string ca = a, cb = b, cc = c;
			x2n (ca, i ), x2n(cb, i ), x2n (cc, i );
			string add = longlongadd (ca, cb );
			if (add == cc ){
				cout << i << endl;
				found = true;
			} // end if
		} // end for
		if (!found ){
			cout << "NA" << endl;
		} // end if		
	} // end loop
		
	return 0;
}

Measured memory_bytes: 0
#E_Multiplication4
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 1000000007
#ソート
arr = []
j = 0
i = 0
seki = 1
gyaku = 1
minuscount = 0
minusposition = 0

def modpow(a,n,mod):
    res = 1
    while n > 0 :
        if n & 1 :
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
def modinv(a,mod):
    return modpow(a, mod - 2, mod)
 
arr = sorted(A,reverse = True)
if arr[(N -1)] > 0 :
    for i in range(K):
        seki = seki * arr[i] % MOD
else:
    if arr[0] < 0 :
        for j in range(K):
            if K % 2 == 1:
                seki = seki * arr[j] % MOD
            else:
                seki = seki * arr[N-j-1] % MOD
    else:
        while (i + j) < K:
            if (i + j + 1) < K :
                if arr[i] * arr[i+1] > (arr[(N - j -1)] * arr[(N - j -2)]):
                    seki = seki * arr[i] % MOD
                    i += 1
                else:
                    minuscount += 2
                    minusposition = N - j -2
                    seki = (seki * arr[(N - j -1)] % MOD) * arr[(N - j -2)] % MOD
                    j += 2
            else:
                if abs(arr[i]) > abs( arr[(N - j -1)]) :
                    seki = seki * arr[i] % MOD
                    i += 1
                else:               
                    minuscount += 1
                    minusposition = N - j -1
                    seki = seki * arr[(N - j -1)] % MOD
                    j += 1
if (minuscount % 2) != 0:
    if minusposition != (i - 1):
        gyaku = modinv(arr[minusposition],MOD)
        seki  = seki * gyaku % MOD
        seki  = seki * arr[i] % MOD
print(seki)


Measured memory_bytes: 31808
/*************************************************************************
>>> Author: WindCry1
>>> Mail: lanceyu120@gmail.com
>>> Website: https://windcry1.com
>>> Date: 12/30/2019 11:03:37 PM
*************************************************************************/
//#pragma GCC optimize(3)
//#pragma GCC diagnostic error "-std=c++11"
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <stack>
#include <bitset>
#include <iomanip>
#include <list>
#include <sstream>
#include <fstream>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define endl '\n'
#define ll long long
#define ull unsigned long long
#ifdef WindCry1
#define DEBUG(x) cout<<#x<<" : "<<x<<endl;
#endif
#define lowbit(x) x&(-x)
#define ls u<<1
#define rs u<<1|1
using namespace std;
template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;}
template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;}
template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);}
template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);}
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifdef WindCry1
	freopen("C:\\Users\\LENOVO\\Desktop\\in.txt","r",stdin);
#endif
	int n,k,s;cin>>n>>k>>s;
	for(int i=1;i<=k;i++) cout<<s<<" ";
	for(int i=k+1;i<=n;i++){
		if(s==1000000000){
			cout<<1<<" ";
		}
		else cout<<s+1<<" ";
	}
	return 0;
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string n;
  cin >> n;
  
  if (n.back() == '3') cout << "bon\n";
  else if (n.back() == '0' || n.back() == '1' || n.back() == '6' || n.back() == '8') cout << "pon\n";
  else cout << "hon\n";
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        while (n-- > 0) {
            int num = sc.nextInt();
            
            if (num % 2 != 0) continue;
            
            if (num % 3 != 0 && num % 5 != 0) {
                System.out.println("DENIED");
                return;
            }
        }
        System.out.println("APPROVED");
    }
}


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

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

    if(a%2 == 0 || b%2 == 0 || c%2 == 0){
        cout << 0 << endl;
    }else{
        cout << min(a*b, min(b*c, c*a)) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(void){
  string s;
  cin >> s;
  if(s[0]=='R' && s[1] == 'R' && s[1] == 'R' && s[2] == 'R'){
    cout << 3 << endl;
  }else if(s[0]=='R' && s[1] == 'R' || s[1] == 'R' && s[2] == 'R' ){
    cout << 2 << endl;
  }else if(s[0]=='R' || s[1] == 'R' ||  s[2] == 'R'){
    cout << 1 << endl;

  }else{
    cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <stdio.h>
using namespace std;

int A[25], n;

bool Solve(int i, int m) 
{
    if (m == 0) return true;
    if (i == n) return false;
    int res = Solve(i+1, m) || Solve(i+1, m-A[i]);
    return res;
}

int main() {
    int q, t;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    } 
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &t);
        if (Solve(0, t)) printf("yes\n");
        else printf("no\n");
    }
}


Measured memory_bytes: 3128
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	string s, t;
	cin>>s>>t;
	int a, b;
	cin>>a>>b;
	string u;
	cin>>u;
	if(s==u) a--;
	else b--;
	cout<<a<<" "<<b<<endl;
	return 0;
}

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

using namespace std;

int main()
{
    int n;
    int tmp;
    vector<int> l;
    
    cin >> n;
    for (int i=0; i<n; ++i)
    {
        cin >> tmp;
        l.push_back(tmp);
    }

    sort(l.begin(), l.end());  

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

    //cout << sum << ' ' << l[n-1];

    const string res = (sum > l[n-1]) ? "Yes" : "No";
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x,y;
  cin >> x >> y;
  if (y%2==1){
  cout << "No" << endl;
  }
  else if(2*x <= y && y <= 4*x) {
  cout << "Yes" << endl;
  }
  else {
  cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in ab(in a){
  return a<0?-a:a;
}
in sm=0;
map<pair<in,in>, in> dcd;
map<in,set<in> > ups,dns;
map<in,VI> upv,dnv;
in d;
VI x,y;
VI cr;
queue<in> q;
void aad(in rx, in ry){
  in id=dcd[MP(rx,ry)];
  if(!cr[id]){
    cr[id]=1;
    q.push(id);
  }
}
void prk(map<in,set<in> >& cs, map<in,VI>& cv, in vl, in mn, in mx, bool tup){
  if(!(cs.count(vl)))
    return;
  set<in>& ss=cs[vl];
  auto it=ss.lower_bound(mn);
  auto it2=it;
  in rx,ry;
  while(it!=ss.end() && *it<=mx){
    rx=*it;
    if(tup)
      ry=rx-vl;
    else
      ry=vl-rx;
    aad(rx,ry);
    it2=it;
    ++it;
    ss.erase(it2);
  }
  VI& vv=cv[vl];
  in tl=lower_bound(all(vv),mn)-vv.begin();
  in tr=upper_bound(all(vv),mx)-vv.begin();
  sm+=tr-tl;
}
void proc(in a){
  in cx=x[a];
  in cy=y[a];
  prk(ups,upv,cx-cy-d,cx-d,cx-1,1);
  prk(ups,upv,cx-cy+d,cx+1,cx+d,1);
  prk(dns,dnv,cx+cy-d,cx-d+1,cx,0);
  prk(dns,dnv,cx+cy+d,cx,cx+d-1,0);
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,a,b;
  cin>>n>>a>>b;
  --a;
  --b;
  x=y=cr=VI(n);
  cr[a]=cr[b]=1;
  forn(i,n){
    cin>>x[i]>>y[i];
    ups[x[i]-y[i]].insert(x[i]);
    dns[x[i]+y[i]].insert(x[i]);
    dcd[MP(x[i],y[i])]=i;
  }
  fors(i,ups){
    fors(j,i->second)
      upv[i->first].PB(*j);
  }
  fors(i,dns){
    fors(j,i->second)
      dnv[i->first].PB(*j);
  }
  d=ab(x[a]-x[b])+ab(y[a]-y[b]);
  q.push(a);
  q.push(b);
  while(!q.empty()){
    a=q.front();
    q.pop();
    proc(a);
  }
  cout<<(sm/2)<<endl;
  return 0;
}


Measured memory_bytes: 53504
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <numeric>
int main() {

	int m, n; std::cin >> m >> n;
	std::vector<int> price(m); for (auto& p : price) std::cin >> p;
	std::sort(price.begin(), price.end()); std::reverse(price.begin(), price.end());
	for (auto i = 1; i < m; ++i) price[i] += price[i - 1];
	std::vector<int> min_price(m + 1, INT_MAX); min_price[0] = 0;
	for (auto i = 0; i < n; ++i) {
		int c, e; std::cin >> c >> e;
		for (int j = m; j >= 0; --j) {
			if (j + c > m) {
				if (min_price[j] != INT_MAX && min_price[m] > min_price[j] + e) min_price[m] = min_price[j] + e;
			}else if (min_price[j] != INT_MAX && min_price[j + c] > min_price[j] + e) {
				min_price[j + c] = min_price[j] + e;
			}
		}
	}
	auto max = 0;
	for (auto i = 1; i <= m; ++i) {
		if (price[i - 1] - min_price[i] > max) max = price[i - 1] - min_price[i];
	}
	std::cout << max << std::endl;
}



Measured memory_bytes: 3248
using System;
using static System.Console;
using System.Collections.Generic;
using System.Collections;

namespace Grobal
{
	class Program
	{
		static void Main(string[] args)
		{
			int a, b, c;
			string[] str = ReadLine().Split(' ');
			a = int.Parse(str[0]);
			b = int.Parse(str[1]);
			c = int.Parse(str[2]);
			if (b - a == c - b) WriteLine("YES");
			else WriteLine("NO");
		}
    }
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

int maxi(int x, int y)
{
	return (x >= y ? x : y);
}

int main(void)
{
	int a, b, c;
	int n;
	int d[100];
	int sum;
	int res;
	int i;
	
	scanf("%d %d %d %d", &n, &a, &b, &c);
	for (i = 0; i < n; i++){
		scanf("%d", &d[i]);
	}
	
	qsort(d, n, sizeof(int), cmp);
	
	res = c / a;
	sum = c;
	for (i = 0; i < n; i++){
		sum += d[i];
		res = maxi(res, sum / (a + (i + 1) * b));
	}
	
	printf("%d\n", res);
	
	return (0);
}

Measured memory_bytes: 600
#include <iostream>

using namespace std;

int main(){

    int H, N;
    cin>>H>>N;
    int sum1 = 0;

    int arr[N];
    int i;

    for(i=0; i<N; i++){
        cin>>arr[i];
    }

    for(i=0; i<N; i++){
        sum1 += arr[i];
    }

    int sum2 = 0;
    sum2 = H - sum1;

    if(sum2 <= 0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }






}


Measured memory_bytes: 640
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  ll n,m;
  cin>>n>>m;
  
  vector<int> A;
  for(int i=1;i*i<=m;i++){
    if(m%i==0){
      A.push_back(i);
      if(i*i!=m) A.push_back(m/i);
    }
  }
  sort(ALL(A));
  
  for(int i=0;i<A.size();i++){
    if(A[i]>=n){
      cout<<m/A[i]<<endl;
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 3592
while True:
    H, W = map(int, input().split())
    if W == 0 and H == 0:
        break
    else:
        for i in range(H):
            x = ''
            if i % 2 == 0:
                for i in range(W):
                    if len(x) < W:
                        x += '#'
                    if len(x) < W:
                        x += '.'
                print(x)
            else:
                for i in range(W):
                    if len(x) < W:
                        x += '.'
                    if len(x) < W:
                        x += '#'
                print(x)
        print()

Measured memory_bytes: 7696
/**
 * Created by hiramekun at 20:53 on 2019-11-23.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

void solve() {
    ll x, y;
    cin >> x >> y;

    ll ans = 0;
    if (x == 1) ans += 300000;
    else if (x == 2) ans += 200000;
    else if (x == 3) ans += 100000;

    if (y == 1) ans += 300000;
    else if (y == 2) ans += 200000;
    else if (y == 3) ans += 100000;
    
    if (x == 1 && y == 1) ans += 400000;
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair < int,int> pii;
typedef pair < double,double> pt;

const int N = 1e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

vector < int > cur;
vector < int > all;
vector < int > v[N];

int a[N],n,bio[N],m;

void dfs(int x,int lst){
    cur.push_back(a[x]);bio[x] = 1;
    for(int i = 0;i<v[x].size();i++){
        if(v[x][i] != lst)
            dfs(v[x][i], x);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%d",a+i);
    }
    for(int i = 0;i<m;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ll sol = 0;
    int grup = 0;
    for(int i = 0;i<n;i++){
        if(bio[i]) continue;
        cur.clear();
        grup++;
        dfs(i, i);
        sort(cur.begin(),cur.end());
        sol += (ll)cur[0];
        for(int j = 1;j<cur.size();j++)
            all.push_back(cur[j]);
    }
    if(grup == 1){
        printf("0\n");
        return 0;
    }
    if(all.size() < grup-2){
        printf("Impossible\n");
        return 0;
    }
    sort(all.begin(),all.end());
    for(int i = 0;i<grup-2;i++)
        sol += (ll)all[i];
    printf("%lld\n",sol);
}


Measured memory_bytes: 7676
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    K = int(input())

    queue = deque()

    for i in range(1,10):
        queue.append(i)

    for i in range(K):
        x = queue.popleft()
        d = x % 10
        temp = 10 * x + d
        if d != 0:
            queue.append(temp - 1)
        queue.append(temp)
        if d != 9:
            queue.append(temp + 1)

    print(x)



main()


Measured memory_bytes: 11884
#include <iostream>
#include <cstdio>

using namespace std;

int solve0(int money, int year){
    int fee;
    double rate;
    cin >> rate >> fee;
    int savings = 0;

    while(year--){
        savings += int(rate*money);
        money -= fee;
    }
    return money+savings;
}

int solve1(int money, int year){
    int fee;
    double rate;
    cin >> rate >> fee;

    while(year--){
        money += money*rate;
        money -= fee;
    }
    return money;
}

int main(){
    int m;
    cin >> m;
    while(m--){
        int money,year,n;
        cin >> money >> year >> n;
        int ans = 0;
        while(n--){
            int type;
            cin >> type;
            if(type==0){
                ans = max(solve0(money, year), ans);
            }else if(type==1){
                ans = max(solve1(money, year), ans);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1240
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	string s, t, u;

	cin >> s >> t >> u;

	transform(s.begin(), s.end(), s.begin(), ::toupper);
	transform(t.begin(), t.end(), t.begin(), ::toupper);
	transform(u.begin(), u.end(), u.begin(), ::toupper);

	cout << s[0] << t[0] << u[0] << endl;

	return 0;
}

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

int main() {
    ll N, mcnt = 0, zf=0;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) {
        cin >> A[i];
        if(A[i] < 0) mcnt++;
        if(A[i] == 0) zf = 1;
    }

    ll sum = 0;
    if(!(mcnt%2) || zf) {
        rep(i, N) {
            if(A[i] < 0) A[i] *= -1;
            sum += A[i];
        }
    } else if(mcnt == N)
        {
            ll maxi = 0;
            rep(i, N) if(A[maxi] < A[i]) maxi = i;
            rep(i, N) {
                if(i != maxi) sum += A[i] * (-1);
                else sum += A[i];
            }
        } else{
        ll midi, madi, resi;
        rep(i, N) if(A[i] < 0) {midi = i; break;}
        rep(i, N) if(A[i] > 0) {madi = i; break;}
        rep(i, N) {
            if(A[i] < 0 && abs(A[i]) < abs(A[midi])) midi = i;
            if(A[i] > 0 && A[i] < A[madi]) madi = i;
        }
        if(abs(A[midi]) > A[madi])  resi = madi;
        else resi = midi;
        rep(i, N) if(A[i] < 0) A[i] *= -1;
        rep(i, N) {
            if(i == resi) sum += A[i] * (-1);
            else sum += A[i];
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
str = input().split()
n = int(str[0])
m = int(str[1])
arr = input().split()
cnt = 0
sum = 0
for i in range(n):
    sum+=int(arr[i])

for i in range(n):
    if int(arr[i]) >= (sum)/(4*m):
        cnt+=1
if cnt >= m:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int h[n+1];
    for(int i =1;i<n+1;i++)
        cin>>h[i];
    vector <int> mp[n+1];
    while(m--){
        int a,b;
        cin>>a>>b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    int cnt =0;
    for(int i=1; i<n+1;i++){
        if(mp[i].size()==0)
            cnt++;
        else{
            int flag =1;
            for(int j =0; j<mp[i].size();j++){
                if(h[mp[i][j]]>=h[i]){
                    flag =0;
                    break;
                }
            }
            if(flag==1)
                cnt++;
        }
    }
    cout<<cnt<<endl;
}


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

int main(void){
    int A, B, K;
    cin >> A >> B >> K;
    int i{min(A, B)};
    while(i>0){
        if(A%i==0 and B%i==0)
            --K;
        if(K==0){
            cout << i << endl;
            return(0);
        }
        --i;
    }
}


Measured memory_bytes: 256
h, w = map(int, input().split())
g = []
for i in range(h):
    g += list(map(int, input().split()))
res = []
for j in range(h):
    for i in range(w):
        for k in [(1,0),(0,1)]:
            if i+k[0]>=0 and i+k[0]<w and j+k[1]>=0 and j+k[1]<h:
                idx_cur = j * w + i
                idx_nex = (j+k[1]) * w + i+k[0]
                if g[idx_cur] % 2 != 0:
                    g[idx_cur] -= 1
                    g[idx_nex] += 1
                    res.append([j+1,i+1,j+k[1]+1,i+k[0]+1])
print(len(res))
for i in res:
    print(*i)

Measured memory_bytes: 96052
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(1000000)


def input():
    return stdin.readline().strip()


def main():
    N, Q = map(int, input().split())
    g = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    points = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        points[p] += x

    scores = [0] * N

    def dfs(g, v, v_prev):
        scores[v] = points[v]
        if v_prev >= 0:
            scores[v] += scores[v_prev]

        for w in g[v]:
            if w == v_prev:
                continue
            dfs(g, w, v)

    dfs(g, 0, -1)

    print(*scores)

    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 274404
import bisect
n,m = map(int,input().split())
d = {}
for i in range(1,n+1):
    d[i] = []
c = []
l = []
for _ in range(m):
    x,y = map(int,input().split())
    c.append([x,y])
    l.append([x,y])
c = sorted(c)
for i in range(len(c)):
    d[c[i][0]].append(c[i][1])
for i in range(len(l)):
    p = '0'*(6-len(str(l[i][0])))+str(l[i][0])
    o = bisect.bisect_left(d[l[i][0]],l[i][1])
    q = '0'*(6-len(str(o+1)))+str(o+1)
    print(p+q)


Measured memory_bytes: 51584
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

double t1, t2;

int main(void)
{
	cin >> t1 >> t2;
	while (t1 > t2) {
		t2 += 360.;
	}
	if (t2 - t1 < 180) {
		double ans = (t1 + t2) / 2;
		while (ans > 360.)ans -= 360.;
		cout << ans << endl;
	}
	else {
		double ans = (t1 + t2) / 2 + 180.;
		while (ans > 360.)ans -= 360.;
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3280
using System;

class Program
{
    static void Main()
    {
        string[] s1 = Console.ReadLine().Split(' ');
        long a = long.Parse(s1[0]);
        long b = long.Parse(s1[1]);

        long c = Gcd(a, b);
               
        Console.WriteLine(a * b / c);
    }

    private 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: 13140
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,x,y;cin>>a>>b>>c>>x>>y;
  int ans=a*x+b*y;
  for(int i=0;i<=max(x,y);i++)ans=min(ans,max(0,x-i)*a+max(0,y-i)*b+2*i*c);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>

using namespace std;

int main()
{
  int n;
  int m;
  int i;
  int j;
  
  int a[100][100]={0};
  int b[100]={0};
  int c[100]={0};
  
  cin >> n >> m;
  
/*  int a[n][m]={0};
  int b[m]={0};
  int c[n]={0};
  */
  for(i=0;i<n;i++)
  {
    for(j=0;j<m;j++)
    {
      cin >> a[i][j];
    }
  }
  
  for(i=0;i<m;i++)
  {
  cin >> b[i];
  }
  
  for(i=0;i<n;i++)
  {
    for(j=0;j<m;j++)
    {
      c[i]+=a[i][j]*b[j];
    }
  }
  
  for(i=0;i<n;i++)
  {
  cout << c[i] <<"\n";
  }
}

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

typedef long long ll;

int main()
{
   ll x,y;
   cin>>x>>y;
   int ans=1;
   for(ll i=1;;i++){
      ll val=x*pow(1LL*2,i);
      if(val>y)break;
      ans++;
   }
   cout<<ans;

}


Measured memory_bytes: 512