akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Mod:
    def __init__(self, m):
        self.m = m
    
    def add(self, a, b):
        return (a + b ) % self.m

    def sub(self, a, b):
        return (a - b) % self.m
    
    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    def pow(self, x, y):
        if y == 0: 
            return 1
        elif y == 1: 
            return x % self.m
        elif y % 2 == 0: 
            return self.pow(x, y//2)**2 % self.m
        else: 
            return self.pow(x, y//2)**2 * x % self.m


@mt
def slv(N):
    if N==3:
        return 61

    m = Mod(10**9+7)
    dp = {}
    iv = (
        'agc',
        'acg',
        'gac',
        'aggc'
        'acgc',
        'atgc',
        'agac',
        'aggc',
        'agtc',
    )
    for s in product('agct', repeat=4):
        s = ''.join(s)
        if not any(map(lambda x: x in s, iv)):
            dp[s] = 1

    for _ in range(N-4):
        dp_ = Counter()
        for k, v in dp.items():
            for c in 'agct':
                s = k + c
                s = s[1:]
                if s in dp:
                    dp_[s] = m.add(v, dp_[s])
        dp = dp_
    
    return reduce(m.add, dp.values())


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6464
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin >> N;
  vector<int> H(N);
  int answer = 0;
  int counter = 0;
  for (int i = 0; i < N; i++)
    cin >> H.at(i);//入力完了
  for (int i = 0; i < N; i++){
    if (i == N - 1)
      break;
    if (H.at(i) >= H.at(i + 1))
    counter++;
      else{
        if(answer <= counter)
          answer = counter;
          counter = 0;
    }
    
  }
  if (answer <= counter)
    answer = counter;
    
  cout << answer << endl;
}

Measured memory_bytes: 640
H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

from collections import defaultdict

dt = defaultdict(int)
for x in range(D + 1, H * W + 1):
    y = x - D
    p1 = pos[x]
    p2 = pos[y]
    dt[x] = dt[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

for l, r in LR:
    print(dt[r] - dt[l])


Measured memory_bytes: 55180
#include<stdio.h>

int main() {
  int a, b;
  char op;

  while(1) {
    scanf("%d %c %d", &a, &op, &b);

    if (op == '+') {
      printf("%d\n", a + b);
    } else if (op == '-') {
      printf("%d\n", a - b);
    } else if (op == '*') {
      printf("%d\n", a * b);
    } else if (op == '/') {
      printf("%d\n", a / b);
    } else {
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 2036
N,L=map(int,input().split())
A=list(map(int,input().split()))
x=-1
for i in range(N-1):
    if A[i]+A[i+1]>=L:
        x=i
        break
if x==-1:
    print('Impossible')
else:
    print('Possible')
    r=list(range(1,x+1))+list(range(N-1,x+1,-1))+[x+1,]
    print(*r,sep='\n')

Measured memory_bytes: 14264
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include <iomanip>
#include<queue>
#include<algorithm>
#include <functional>
#include<vector>
#include <math.h>
#include <numeric>
#include <stack>
using namespace std;


int main() {
	int v[3];
	cin >> v[0] >> v[1] >> v[2];
	sort(v, v+3);
	cout << v[0] + v[1] << endl;


}

Measured memory_bytes: 256
loop do
  m = gets.to_i
  break if m.zero?
  m.times.map do
    id, *ss = gets.split.map(&:to_i)
    s, i = 0, 0
    10.times do |j|
      if ss[i] == 10
        s += ss[i] + ss[i+1] + ss[i+2]
        i += 1
      elsif ss[i] + ss[i+1] == 10
        s += ss[i] + ss[i+1] + ss[i+2]
        i += 2
      else
        s += ss[i] + ss[i+1]
        i += 2
      end
    end
    [-s, id]
  end.sort!.each {|s, id| puts "#{id.to_i} #{-s}" }
end

Measured memory_bytes: 8868
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=100000000000000000;

ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}

int main(){
    ll n;cin>>n;
    string s[n];
    ll c[5]={};
    for(ll i=0;i<n;i++){
        cin>>s[i];
        if(s[i][0]=='M'){
            c[0]++;
        }else if(s[i][0]=='A'){
            c[1]++;
        }else if(s[i][0]=='R'){
            c[2]++;
        }else if(s[i][0]=='C'){
            c[3]++;
        }else if(s[i][0]=='H'){
            c[4]++;
        }
    }
    ll ans=0;
    for(ll i=0;i<=2;i++){
        for(ll j=i+1;j<=3;j++){
            for(ll k=j+1;k<=4;k++){
                ans+=c[i]*c[j]*c[k];
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 6144
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    if(n & 1){
    	ll mid = n / 2;
    	for(int i=0;i<m;i++){
    		cout << mid - i << " " << mid + 1 + i << endl;
    	}
    }else{
    	if(n == 4){
    		cout << 1 << " " << 2 << endl;
    	}else{
    		vector<pair<ll, ll> > v;
    		ll k = n / 2;
    		ll mid = k / 2;
    		for(int i=0;mid - i >= 1 ;i++){
    			v.push_back({mid - i, mid + 1 + i});
    	    }
    	    k++;
    	    mid = ( n + k ) / 2;
    	    for(ll i = 1; mid + i <= n; i++){
    	    	v.push_back({mid - i, mid + i});
    	    }
    	    for(int i=0;i<m;i++){
    	    	cout << v[i].first << " " << v[i].second << endl;
    	    }
    	}
    }
    return 0;
}


Measured memory_bytes: 5252
import java.io.*;
import java.util.Arrays;
class Main{
    public static void main(String[] args) throws IOException {
        int i;
        int[] n = new int[990];
        String[] str = new String[990];
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        for(;;){
            str = in.readLine().split(" ");
            for(i=0;i<3;i++){
                n[i]=Integer.parseInt(str[i]);
            }
            if(n[0]==n[1] && n[0]==-1)   break;
            if((n[0]==-1) || (n[1]==-1)) 
                System.out.println("F");
            else if(n[0]+n[1]<30)        
                System.out.println("F");
            else if((30<=n[0]+n[1] && n[0]+n[1]<50) && n[2]<50)  
                System.out.println("D");
            else if((30<=n[0]+n[1] && n[0]+n[1]<50) && n[2]>=50) 
                System.out.println("C");
            else if((50<=n[0]+n[1] && n[0]+n[1]<65))     
                System.out.println("C");
            else if((65<=n[0]+n[1]) && (n[0]+n[1]<80))   
                System.out.println("B");
            else if(80<=n[0]+n[1])   
                System.out.println("A");  
        }          
        System.out.flush();
    }
}

Measured memory_bytes: 24216
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<ll, int> mp;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(8, 0);
	int cnt = 0;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		int c = 0;
		for (int j = 0; j < 8; j++) {
			if (c <= a[i] && a[i] < (c + 400)) b[j]++;
			c += 400;
		}
		if (3200 <= a[i]) cnt++;
	}
	if (cnt == n) {
		cout << 1 << " " << cnt << endl;
		return 0;
	}
	int ans = 0;
	for (int i = 0; i < 8; i++) {
		if (b[i] > 0) ans++;
	}
	cout << ans << " " << ans + cnt << endl;
	return 0;
}

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

long long f(long long n, long long x) {
    if(n < 0) {
        return 0;
    } else {
        return n / x + 1;
    }
}

int main() {
    long long a, b, x;
    cin >> a >> b >> x;
    cout << f(b, x) - f(a-1, x) << endl;
    return 0;
}

Measured memory_bytes: 256
import bisect

def line_input(f, type):
    return f(map(type, input().split(" ")))

a,b,c,d,e,f = line_input(tuple, int)

max_dens = 0
ans_w = 0
ans_s = 0

wl = set()
for adx in range(0, f // (a*100) + 1):
    for bdx in range(0, f // (b*100) + 1):
        if adx == 0 & bdx == 0:
            continue

        wl.add(a * adx + b * bdx)

sl = set()
for cdx in range(0, f // c + 1):
    for ddx in range(0, f // d + 1):
        sl.add(c * cdx + d * ddx)

for w in wl:
    if w > f:
        continue

    for s in sl:
        cap = f - w * 100
        C = w * 100 + s

        dens = s / C
        if (C <= f) & (s <= e * w) & (max_dens <= dens):
            max_dens = dens
            ans_w = C
            ans_s = s

print(ans_w, ans_s)

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

int main(void) {
	long long int n; cin >> n;
	int i;

	for (i = 1;; i++) {
		if (i*i > n) { break; }
	}

	cout << (i - 1)*(i - 1) << endl;

	return 0;
}



Measured memory_bytes: 256
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N = in.nextInt
  val As = Array.fill(N)(in.nextInt)

  val map = (0 until N)
    .map(i => i - As(i))
    .filter(_ > 0)
    .groupBy(identity)
    .view.mapValues(_.size.toLong).toMap
    .withDefaultValue(0L)

  println((0 until N).map(i => map(i + As(i))).sum)
}

Measured memory_bytes: 141600
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------

int n, a, x,y,z;
double dp[301][301][301];

double dfs(int o, int tw, int th){
    if(dp[o][tw][th]) return dp[o][tw][th];
    double sm = o+tw+th;
    double ret = n / sm;
    if (o) ret += dfs(o-1,tw,th) * (o/sm);
    if (tw) ret += dfs(o+1,tw-1,th) * (tw/sm);
    if (th) ret += dfs(o,tw+1,th-1) * (th/sm);

    dp[o][tw][th] = ret;
    return ret;
}

signed main(){
    I(n);
    REP(i,n){
        I(a);
        if(a == 1) x++;
        if(a == 2) y++;
        if(a == 3) z++;
    }
    dp[1][0][0] = n;
    printf("%.13f\n",dfs(x,y,z));
}

Measured memory_bytes: 213248
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#define MY_DEBUG(s)      s
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#define MY_DEBUG(s)      
#endif

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define EPS (1e-7)
#define IINF ((int)1e9)


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

	ll n;
	cin >> n;
	ll res = 0;
	for (ll k = 1; k <= n; k++)
	{
		for (ll j = k; j <= n; j += k)
		{
			res += j;
		}
	}
	cout << res << "\n";
	return 0;
}
MY_NAMESPACE_

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

int main() {
  int n;
  ll ans = 0;
  cin >> n;
  vector<int>a(n);
  rep(i,0,n) cin >> a[i];
  rep(i,0,n-1){
    ans += a[i]/2;
    a[i] %= 2;
    if(a[i+1] > 0){
      ans += a[i];
      a[i+1] -= a[i];
    }
  }
  ans += a[n-1]/2;
  cout << ans << endl;
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("black");}else{puts("white");}
#define MAX_N 200005

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

    int a[n];
    rep(i,n)cin >> a[i];

    cout << min_element(a, a+n) - a + 1 << endl;
    
    return 0;
}
 
 



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

int main(){
    string W;
    cin >> W;
    sort(begin(W), end(W));
    char a = W[0];
    bool beautiful = true;
    if(W.size()%2 == 0){
        for(int i = 1; i < W.size(); i++){
            if(a != W[i] && i%2 == 1){
                beautiful = false;
                break;
            } else if(a != W[i]){
                a = W[i];
            }
        }
        if(beautiful) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    // 文字列が偶数じゃない時点で美しくない。
    else cout << "No" << endl;
}

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

int main(){
    string s;
    cin >> s;
    rp(i,s.size())
    s.at(i)='x';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> init(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

int n, m;
vector<int> a;

ll lcm(int a, int b){
    return (ll)a*b/__gcd(a, b);
}

int numTwos(int a){
    int ans = 0;
    while(a%2==0){
        a /= 2;
        ++ans;
    }
    return ans;
}

void solve(){
    cin >> n >> m;
    a = vector<int>(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        a[i] /= 2;
    }

    ll lowest = a[0];
    int twos = numTwos(a[0]);
    for(int i = 1; i < n; ++i){
        lowest = lcm(lowest, a[i]);
        if(lowest > m || numTwos(a[i]) != twos){
            cout << "0\n";
            return;
        }
    }

    ll ans = 1 + (m - lowest)/(2LL*lowest);
    cout << ans << '\n';
}

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

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

#include <boost/range/adaptors.hpp>
#include <boost/range/combine.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n;
    cin >> n;

    for (auto i : irange(0L, n)) {
        cout << "ACL";
    }
    cout << endl;
}

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

#define ll long long int
#define pb emplace_back
#define mod 1000000007
#define inf 1e16

double dp[301][301][301];

double solve(ll one, ll two, ll three, ll n){
    // cout<<one<<" "<<two<<" "<<three<<endl;
    if(one<0 || two<0 || three<0){
        return 0;
    }
    if(dp[one][two][three]!=-1){
        return dp[one][two][three];
    }
    if(one+two+three==0){
        return 0;
    }
    double p1 = double(one)/n;
    double p2 = double(two)/n;
    double p3 = double(three)/n;
    double p0 = double(n-one-two-three)/n;
    return dp[one][two][three] = (1 + p1*solve(one-1, two, three, n) + p2*solve(one+1, two-1, three, n) + p3*solve(one, two+1, three-1, n))/(1-p0);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cout<<fixed<<setprecision(9);
    
    ll n;
    cin>>n;
    ll one = 0, two = 0, three = 0;
    for(ll i=0; i<n; i++){
        ll ai;
        cin>>ai;
        one+=(ai==1);
        two+=(ai==2);
        three+=(ai==3);
    }
    for(ll i=0; i<301; i++){
        for(ll j=0; j<301; j++){
            for(ll k=0; k<301; k++){
                dp[i][j][k] = -1;
            }
        }
    }
    cout<<solve(one, two, three, n)<<"\n";
}

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

int main(){
    int N;
    cin>>N;
    int a[N];
    int ans=0;
    rep(i,N)cin>>a[i];
    rep(i,N){
        if((i+1)%2==1&&a[i]%2==1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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

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

  int ans = 0;

  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }

  cout << ans << "\n";
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 21:01:13 2019

@author: Wataru
"""

x=input()
if x=='A':
    print('T')
elif x=='T':
    print('A')
elif x=='C':
    print('G')
elif x=='G':
    print('C')
    

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

Measured memory_bytes: 96248
import sys
from collections import deque


fin = sys.stdin.readline
H, W = [int(elem) for elem in fin().split()]
A_list = [fin().rstrip("\n") for _ in range(H)]
assert len(A_list[0]) == W

visited = [[False] * W for _ in range(H)]
que = deque((i, j, 0) for i in range(H) for j in range(W) if A_list[i][j] == "#")
max_dist = 0
while que:
    i, j, dist = que.popleft()
    for next_i, next_j in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if not (0 <= next_i < H and 0 <= next_j < W):
            continue
        elif visited[next_i][next_j]:
            continue
        elif A_list[next_i][next_j] == "#":
            continue
        else:
            que.append((next_i, next_j, dist + 1))
            visited[next_i][next_j] = True
            max_dist = max(max_dist, dist + 1)
print(max_dist)


Measured memory_bytes: 135644
void solve();

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

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
using namespace std;

int M, D;

void solve() {
	cin >> M >> D;
	int counter = 0;
	for (int d = 10; d <= D; d++) {
		int d1 = d % 10;
		int d10 = (d - d1) / 10;
		if (d1 < 2 || d10 < 2)continue;
		if (d1 * d10 <= M)counter++;
	}
	cout << counter << endl;
	return;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll dp[105][100005];
ll fun(ll wt[],ll v[],ll n,ll w)
{
    if(dp[n][w]!=-1)
    return dp[n][w];
    if(n==0 || w==0)
    return dp[n][w]=0;
    if(wt[n-1]>w)
    return dp[n][w]=fun(wt,v,n-1,w);
    return dp[n][w]=max(fun(wt,v,n-1,w),(v[n-1]+fun(wt,v,n-1,w-wt[n-1])));
}
int main()
{
    ll t,n,w;
        cin>>n;
        cin>>w;
        ll wt[n],v[n];
        for(int i=0;i<n;i++)
        cin>>wt[i]>>v[i];
        for(int i=0;i<105;i++)
        {
            for(int j=0;j<100005;j++)
            dp[i][j]=-1;
        }
        cout<<fun(wt,v,n,w)<<endl;
    return 0;
}


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

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 5e5 + 13;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int a[N];

int main(){
    #ifdef KAZAKH
        freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll s = 0;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        s += a[i];
    }
    ll mn = INF;
    ll p = 0;
    for (int i = 1; i <= n; i++){
        p += a[i];
        s -= a[i];
        mn = min(abs(p-s), mn);
    }
    cout << mn;
    return 0;
}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;

bool IsPrime(ll num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
    ll N; cin >> N;

    ll cnt = 0;
    ll result = 1000000000007; // 10^12+7
    double sqrtNum = sqrt(N);

    if(IsPrime(N) == true) {
        result = N - 1;
    } else {
        for(int i = 2; i <= sqrtNum; ++i) {
            if(N % i == 0) {
                cnt = (N / i) + i - 2;
                if(result > cnt) {
                    result = cnt;
                }
            }
        }
    }

    cout << result << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

void FastIO ()
{
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
}

inline void solve ()
{
  int n, m;
  cin >> n >> m;
  
  int cnt = 0, s = 0;
  
  vector<int> v(n);
  for(int& x: v) { cin >> x; s += x; }
  
  for(int x: v) cnt += (double) x >= (double) s / (double) (4.0 * m);
  
  if(cnt >= m) cout << "Yes";
  else cout << "No";
}

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

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

int main(){
  
  int A,B,C; cin >> A >> B >> C;
  
  if(A == B){
    cout << C << endl;
  }
  
  else if(B == C){
    cout << A << endl;
  }
  
  else{
    cout << B << endl;
  }
  
  
  return 0;
}
  
  

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

class Dice {
public:
	int f[6];
	Dice() {}//これなぞ下の関数を使えるようにするため？←初期化っぽい？
	void roll_z() { roll(1, 2, 4, 3); }
	void roll_y() { roll(0, 2, 5, 3); }
	void roll_x() { roll(0, 1, 5, 4); }
	
	void roll(int i, int j, int k, int l) {
		int t = f[i]; f[i] = f[j]; f[j] = f[k]; f[k] = f[l]; f[l] = t;
	}
};


int getRight(Dice c1, int f1, int f2) {
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 4; j++) {
			if (c1.f[0] == f1&&c1.f[1] == f2)return c1.f[2];
			c1.roll_z();
		}
		if (i % 2 == 0) c1.roll_y();
		else  c1.roll_x();
	}
	return -1;
}


int main()
{
	Dice c;
	int f1, f2;

	for (int i = 0; i < 6; i++) cin >> c.f[i];
	int q; cin >> q;
	
	for (int i = 0; i < q; i++) {
		cin >> f1 >> f2;
		cout << getRight(c, f1, f2) << endl;
	}
    return 0;
}




Measured memory_bytes: 3080
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;


int main()
{


        int N=0;
        cin >> N;


        int* num = new int[2*N];
        for(int i=0;i<2*N;i++)
        {
                string data;
                cin >> data;
                num[i]=atoi(data.c_str());
        }
        sort(num,num+2*N);
        int sum=0;
        for(int i=0;i<2*N;i+=2)
                sum+=num[i];

        cout<<sum<<endl;
        return 0;



}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair
 
using namespace std;
 
const LL MOD=1e9+7;

LL a,b,c;

int main()
{
	cin>>a>>b>>c;
	if(c-a-b<0)
	{
		puts("No");
		return 0;
	}
	if(4LL*a*b<(c-a-b)*(c-a-b)) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 256
s = input()
t = input()

s_c = []
t_c = []
for i in range(len(s)):
    s_c.append(s[i])
    t_c.append(t[i])
    
from collections import Counter
s_c = Counter(s_c)
t_c = Counter(t_c)
s_keys, s_values = zip(*s_c.most_common())
t_keys, t_values = zip(*t_c.most_common())

if s_values == t_values:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 68412
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
double dp[200][100];//動的計画法
int main(){
    long long a,b,cnt,tmp;
    while(cin>>a>>b,a){
        cnt=0;
        if(a<b){
            tmp=b;
            b=a;
            a=tmp;
        }
        while(b){
            a%=b;
            tmp=b;
            b=a;
            a=tmp;
            cnt++;
        }
        cout<<a<<" "<<cnt<<endl;
    }
}


Measured memory_bytes: 3016
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int n;
ll d[202020];
vector<pair<int,int>> v;
ll s;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		while (v.size() && v.back().first > x) v.pop_back();
		if (v.size()) {
			d[i] += (ll)x*(i-v.back().second);
			d[i] += d[v.back().second];
		} else {
			d[i] += (ll)x*i;
		}
		s += d[i];
		v.push_back({x,i});
	}
	cout << s << "\n";
}


Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  int ans = max(c - (a - b), 0);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    int TESTS=1;
    // cin>>TESTS;
    while(TESTS--)
    {   
        int n;
        cin>>n;
        int a[n];
        rep(i,0,n) cin>>a[i];
        int ans=1;
        int cur=1;
        int curval = a[0];
        rep(i,1,n){
        	if(a[i]<=curval){
        		cur++;
        		curval = a[i];
        	}
        	else{
        		curval = a[i];
        		cur = 1;
        	}
        	ans = max(ans,cur);
        }
        cout<<ans-1;
    }   
}     

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

ll gcd(ll a, ll b){
    if(b == 0) return a;
    if(a < b){
        ll tmp = b;
        b = a;
        a = tmp;
    }

    while(b != 0){
        ll tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

int main(){
    ll n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    ll l = n/gcd(n, m)*m, ln = l/n, lm = l/m;
    ll p = 0, q = 0, sp = 0, st = 0;
    for(ll i = 0; i < l; i += min(ln, lm)){
        if(st == sp && i == st){
            if(s[p] != t[q]){
                cout << "-1" << endl;
                return 0;
            }
        }
        if(i >= sp) sp = ++p*ln;
        if(i >= st) st = ++q*lm;
    }    
    cout << l << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4765
const int mod = 1000000007;

struct mint {
    ll x;

    mint(ll x = 0) : x(x % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

struct combination {
    vector<mint> fact, ifact;

    combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
} comb(100005);

mint f(int n, int k) {
    if (n < 0) return 0;
    // nPk = nCk * k!
    mint res = comb(n, k);
    res *= comb.fact[k];
    return res;
}

int k;
mint ans;
vector<int> to[100005];

void dfs(int v, int p = -1) {
    for (int u : to[v]) {
        if (u == p) continue;
        dfs(u, v);
    }
    int nk = (p == -1) ? k : k - 2;
    int c = (p == -1) ? to[v].size() + 1 : to[v].size() - 1;
    ans *= f(nk, c);
}

int main() {
    int n;
    cin >> n >> k;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ans = 1;
    dfs(0);
    cout << ans.x << endl;
    return 0;
}


Measured memory_bytes: 10752
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ull unsigned long long 
#define int long long 
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define MAX 1e18
#define PI 3.14159265
const int mod = 1e9 + 7;

int power(int x, int y) 
{ 
   int res = 1;      
  
   
    while (y > 0) 
    { 
       
        if (y & 1) 
            res = (long long)(res*x); 
  
 
        y = y>>1; 
 
        if (x<=100000000)
        x = (long long)(x*x);
 
        //cout<<x<<'\n'; 
    } 
    return res; 
} 

void solve()
{
    int n;
    cin>>n;

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

    }

    unordered_map<int,int>m;
    int sum=0;
    for(int i=0;i<n;i++){
        m[a[i]]++;
        sum+=a[i];
    }

   
   
    int q;
    cin>>q;

    for(int i=0;i<q;i++){
        int b,c;
        cin>>b>>c;
        sum+=(-b*m[b]  +  c*m[b]);
        cout<<sum<<endl;
        m[c]+=m[b];
        m[b]=0;


    }
    return;
}

    

    

    


int32_t main()
{
    IOS;
    solve();
    return 0;
}

Measured memory_bytes: 7876
#include<iostream> 
long long a,b,x;
long long s,e;
int main(){
    std::cin>>a>>b>>x;
    if(a%x==0)s=a/x;
    else s=a/x+1;
    e=b/x;
    std::cout<<e-s+1;
	return 0;
}

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

int n;
vector<int> g[222];
int c[222];

vector<int> a;
int max_depth = 0;
void depth(int x) {
  vector<int> d(200, 0);
  queue<int> q;
  q.push(x);
  d[x] = 1;
  while (q.size()) {
    int a = q.front();
    q.pop();
    max_depth = max(max_depth, d[a]);
    for (int b : g[a]) if (!d[b]) {
      d[b] = d[a] + 1;
      q.push(b);
    }
  }
}

int solve() {
  max_depth = 0;
  for (int x : a) {
    depth(x);
  }
  return max_depth;
}

void dfs(int x, int t) {
  c[x] = t;
  a.push_back(x);
  for (int y : g[x]) {
    if(c[y] == 0) {
      dfs(y, 3 - t);
    } else if (c[y] == c[x]) {
      cout << -1 << endl;
      exit(0);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < n; ++j) {
      if (s[j] == '1') {
        g[i].push_back(j);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (c[i] == 0) {
      dfs(i, 1);
      ans += solve();
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 512
#include<iostream>
#include<sstream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cfloat>
#include<functional>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<bitset>
#include<list>
#include<numeric>
#include<complex>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<long long, long long> ll_ll;
typedef pair<double, double> d_d;
typedef vector<int> Vint;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define rep2d(i, j, n) for(i = 0;i < n;++i)for(j = i + 1;j < n;++j)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << x << "\n"
#define pri2(x, y) cout << x << " " << y << "\n"
#define pri3(x, y, z) cout << x << " " << y << " " << z << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << x << "\n"
#define debug2(x, y) cout << " --- " << x << " " << y << "\n"
#define debug3(x, y, z) cout << " --- " << x << " " << y << " " << z << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

struct edge{
  int to, cap, inv;
};

vector<edge> G[100];
bool vsted[100];
int inf = 123456; //???????°´??????

int dfs(int v, int e, int now, int t, int w){
  if(now == t)return w;
  vsted[now] = true;
  for(int i = 0;i < G[now].size();++i){
    edge tmp = G[now][i];
    if(!vsted[tmp.to] && tmp.cap > 0){
      int d = dfs(v, e, tmp.to, t, min(w, tmp.cap));
      if(d > 0){
        G[now][i].cap -= d;
        G[tmp.to][tmp.inv].cap += d;
        return d;
      }
    }
  }
  return 0;
}

ll edmondskarp(int v, int e, int s, int t){
  ll res = 0;
  for(;;){
    for(int i = 0;i < v;++i)vsted[i] = false;
    int x = dfs(v, e, s, t, inf);
    if(x == 0)return res;
    res += x;
  }
  return res;
}

signed main(void){
  int i, j, k;

  int2(v, e);
  rep(i, e){
    int3(x, y, z);
    G[x].pb((edge){y, z, G[y].size()});
    G[y].pb((edge){x, 0, G[x].size() - 1});
  }

  cout << edmondskarp(v, e, 0, v - 1) << endl;

  return 0;
}

Measured memory_bytes: 1276
city_num, like_num = map(int, input().split())
arrival = list(map(int, input().split()))
for _ in range(city_num):
    arrival[_] -= 1

am = 0
a2m = 0
l_lis = [0, arrival[0]]  # l_lis[0]は0回

am = arrival[am]
a2m = arrival[arrival[a2m]]

while(am != a2m):
    am = arrival[am]
    a2m = arrival[arrival[a2m]]
    l_lis.append(am)

# city_lが循環開始
l = 0
x = am
y = 0
while(x != y):
    x = arrival[x]
    y = arrival[y]
    l += 1
# print(l)


r = 1
am = x
a2m = x
r_lis = []  # r_lis[0]は循環開始の次
am = arrival[am]
a2m = arrival[arrival[a2m]]
while(am != a2m):
    r_lis.append(am)
    am = arrival[am]
    a2m = arrival[arrival[a2m]]
    r += 1
    # print(am+1, a2m+1, r)

# print(r)

times = 0
if(l > like_num):
    times = like_num
else:
    times = l + (like_num - l) % r
ans = 0
for _ in range(times):
    ans = arrival[ans]

print(ans+1)


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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

s = 0
for k in d:
    s += d[k] * (d[k] - 1) // 2

for i in range(N):
    t = d[A[i]]
    print(s - t * (t - 1) // 2 + (t - 1) * (t - 2) // 2)

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

int main(){
    int A,B; cin >> A >> B;
    int left,right;
    left=ceil(A/0.08); right=floor((A+1)/0.08);
    int ans=-1;
    for(int i=left; i<right; i++){
        if(floor(i*0.1)==B){
            ans=i;
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dl double long
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rrep(i, m, n) for(ll i = (ll)(m); i > (ll)(n); --i)
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;

int main(void){
    int n, k;
    cin >> n >> k;
    bool A[100];
    rep(i, 0, n)A[i] = false;
    rep(i, 0, k){
        int d;
        cin >> d;
        rep(j, 0, d){
            int a;
            cin >> a;
            if(A[a-1] == false) A[a-1] = true;
        }
    }
    int count = 0;
    rep(i, 0, n){
        if(A[i] == false)count++;
    }
    cout << count << endl;
    return 0;
}

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

#define max(a,b) ((a) > (b) ? (a) : (b))

using namespace std;

string add(string lhs, string rhs) {
    int length = max(lhs.size(), rhs.size());
    int carry = 0;
    int sum_col;  // sum of two digits in the same column
    string result;

    // pad the shorter string with zeros
    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    // build result string from right to left
    for (int i = length-1; i >= 0; i--) {
      sum_col = (lhs[i]-'0') + (rhs[i]-'0') + carry;
      carry = sum_col/10;
      result.insert(0,to_string(sum_col % 10));
    }
    
    if (carry)
      result.insert(0,to_string(carry));
    
    // remove leading zeros
    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string subtract(string lhs, string rhs) {
    int length = max(lhs.size(), rhs.size());
    int diff;
    string result;

    while (lhs.size() < length) 
      lhs.insert(0,"0");
            
    while (rhs.size() < length) 
      rhs.insert(0,"0");

    for (int i = length-1; i >= 0; i--) {
        diff = (lhs[i]-'0') - (rhs[i]-'0');
        if (diff >= 0)
            result.insert(0, to_string(diff));
        else {

            // borrow from the previous column
            int j = i - 1;
            while (j >= 0) {
                lhs[j] = ((lhs[j]-'0') - 1) % 10 + '0';
                if (lhs[j] != '9') 
                    break;
                else 
                    j--;
            }
            result.insert(0, to_string(diff+10));
        }
      
    }

    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

string multiply(string lhs, string rhs) {
    int length = max(lhs.size(), rhs.size());
    
    while (lhs.size() < length) 
      lhs.insert(0,"0");

    while (rhs.size() < length) 
      rhs.insert(0,"0");

    if (length == 1)
        return to_string((lhs[0]-'0')*(rhs[0]-'0'));

    string lhs0 = lhs.substr(0,length/2);
    string lhs1 = lhs.substr(length/2,length-length/2);
    string rhs0 = rhs.substr(0,length/2);
    string rhs1 = rhs.substr(length/2,length-length/2);
    
    string p0 = multiply(lhs0,rhs0);
    string p1 = multiply(lhs1,rhs1);
    string p2 = multiply(add(lhs0,lhs1),add(rhs0,rhs1));
    string p3 = subtract(p2,add(p0,p1));

    for (int i = 0; i < 2*(length-length/2); i++)
        p0.append("0");
    for (int i = 0; i < length-length/2; i++)
        p3.append("0");
        
    string result = add(add(p0,p1),p3);

    return result.erase(0, min(result.find_first_not_of('0'), result.size()-1));
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << multiply(s1,s2) << endl;
    return 0;
}

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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  int X = A*B;
  int Y = C*D;
  if(X<Y){
    cout << Y << endl;
  }
  else{
    cout << X << endl;
  }
}


Measured memory_bytes: 3624
#!/usr/bin/python3
N, Q = [int(x) for x in input().split()]
S = input()

qs = []
for _ in range(Q):
    t, d = [x for x in input().split()]
    #print(t, d)
    qs.append((t,-1 if d == 'L' else 1))

memo = [None] * N
memo.append(N)

def move(i):
    org = i
    if memo[i]:
        return memo[i]
    for t, d in qs:
        if S[i] == t:
            i+=d
        if i == -1:
            break
        elif i == N:
            break
    memo[org] = i
    return i

def search_right(lo, hi, x):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if x < move(mid):
            hi = mid 
        else: # e <= t
            lo = mid +1
    return lo

def search_left(lo, hi, x):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if move(mid) < x:
            lo = mid +1
        else: # e <= t
            hi = mid
    return lo


#l = search(0, N-1, -1)
#assert move(l) == 2, "%d" % move(l)
#print("search(-1)=", l)

l = search_right(0, N, -1)
r = search_left(0, N, N)

if 1==0:
    print(S)
    for t, d in qs:
        print(t, {-1:'L', 1:'R'}[d])
    m = [move(i) for i in range(N+1)]
    print(" ".join("%2d" % i for i in range(N+1)))
    print(" ".join("%+d" % x for x in m))
    print(" ".join(" *" if l == i else "  " for i in range(N+1)))
    print(" ".join(" *" if r == i else "  " for i in range(N+1)))

print(r-l)





Measured memory_bytes: 19380
n,m = map(int,input().split())
a = [list(map(int,input().split()))for i in range(m)]
for i in range(10**n):
    tmp = str(i)
    if len(tmp)== n:
        f = True
        for s,c in a:
            if tmp[s-1] != str(c):
                f = False
                break
        if f:
            print(i)
            exit()
print(-1)

Measured memory_bytes: 9080
//containing t test cases
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define scan(n) ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define pi 3.1415926535897932384626433832795028841971
//#define int long long
using namespace std;
//typedef vector<int>vi ;
typedef vector<ll>vi ;
typedef vector<vector<ll> >vvl ; 
typedef pair<ll,ll> pll ;
typedef vector<pair<ll,ll> > vpll;
//cout<<fixed<<setprecision(15);
/*vi adj[200005];
ll vis[200005];
ll parent[200005];
ll level[200005];
ll arr[200005];
ll size[200005];*/
//endl mut bhool!!
void solve()
{
    ll a,b;
    cin>>a>>b;
    ll x=a*b;
    cout<<x;
}
int main()
{
    fast;
    ll test=1;
    //cin>>test;
    while(test--)
    {
        solve();
    }
    return 0;
}
/*
cout<<"YES"<<endl;
cout<<"NO"<<endl;
*/


Measured memory_bytes: 3600
#include <iostream>
#include <cmath>

int main(int argc, char *argv[]){
    int N,M;
    std::cin >> N >> M;
    int L[M], R[M];
    for(int i=0; i<M; ++i){
        std::cin >> L[i] >> R[i];
    }
    int left=L[0], right=R[0];
    for(int i=1; i<M; ++i){
        left = std::max(left,L[i]);
        right = std::min(right,R[i]);
        if(left > right){
            std::cout << 0 << std::endl;
            return 0;
        }
    }
    std::cout << (right-left+1) << std::endl;
    return 0;
}


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

#define int long long int 

int32_t main()
{
  string s,t;
  cin>>s>>t;
  t+=t;
  if(t.find(s)!=-1)
  cout<<"Yes"<<endl;
  else
  cout<<"No"<<endl;
}

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

using namespace std;

typedef long long ll;

#define db(m)  cout<<#m<<" = "<<m<<"\n"

#define MAX 100000

void bang(){
    ll n; cin>>n;
    vector<ll>v(n);
    for(auto& i : v) cin>>i;

    ll ans = 0;
    ll mx = v[0];
    for(int i = 0; i < n; i++){
        if(v[i] < mx) ans += mx - v[i];
        mx = max(mx, v[i]);
    }
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int q; cin>>q;
    // while(q--)
        bang();
    return 0;
}

Measured memory_bytes: 4764
a, b = map(int, input().split())

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

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}

int main(){
	int a,b;
cin>>a>>b;
if(a<=b)cout<<a<<endl;
else cout<<a-1<<endl;
	return 0;
}


Measured memory_bytes: 256