akhauriyash/Code-Regression huggingface dataset:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[-1 for _ in range(N)] for i in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            A[i][x-1] = y

    ans = 0
    for i in range(2 ** N):
        bit = format(i, "b").zfill(N)
        #print(bit)
        one = 0
        flag = True
        for j in range(N):
            if bit[j] == "1":
                for k in range(N):
                    if A[j][k] >= 0 and A[j][k] != int(bit[k]):
                        flag = False
                        break
                one += 1    
        if flag: ans = max(ans, one)

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def prim_heap(edge, n):
    '''
    プリム法で最小全域木を求める

    Parameters
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    
    Returns
    res : int
        最小全域木の全ての辺のコストの総和
    '''
    used = [True] * n #True:不使用
    edgelist = []
    edgelist = set_heapq(edgelist, edge, used, 0)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        edgelist = set_heapq(edgelist, edge, used, v)
        res += minedge[0]
    return res

V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for i in range(E):
    s, t, w = map(int, input().split())
    edge[s].append((w, t))
    edge[t].append((w, s))

print(prim_heap(edge, V))



Measured memory_bytes: 40160
import heapq as hq

x,y,a,b,c=map(int,input().split())
R=list(reversed(sorted(map(int,input().split()))))
G=list(reversed(sorted(map(int,input().split()))))
N=list(reversed(sorted(map(int,input().split()))))
A=[]
hq.heapify(A)
for i in range(x):
    hq.heappush(A,-R[i])
for i in range(y):
    hq.heappush(A,-G[i])
for n in N:
    hq.heappush(A,-n)

ans=0
for i in range(x+y):
    ans-=hq.heappop(A)
print(ans)

Measured memory_bytes: 28976
using System.Linq;
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var p = 0;
        while (p++ < n)
        {
            var s = Console.ReadLine().Trim();
            var ans = getAns(s);
            Console.WriteLine(ans);
        }
    }
    static int getAns(string s)
    {
        var sL = s.Length;
        var hs = new HashSet<string>();
        for (int i = 1; i < sL; i++)
        {
            var a = s.Substring(0, i);
            var b = s.Substring(i);
            hs.Add(a + b);
            hs.Add(a + getREV(b));
            hs.Add(getREV(a) + b);
            hs.Add(getREV(a) + getREV(b));
            hs.Add(b + a);
            hs.Add(b + getREV(a));
            hs.Add(getREV(b) + a);
            hs.Add(getREV(b) + getREV(a));
        }
        return hs.Count();
    }
    static string getREV(string s)
    {
        var a = s.ToCharArray();
        Array.Reverse(a);
        return new string(a);
    }
}



Measured memory_bytes: 26700
from sys import stdin
a,b = map(int,stdin.readline().split())
ans = 'Impossible'
c = a+b
x = [a,b,c]
def ch(n):
 if n==0:
  return 0
 if n%3:
  return 0
 return 1
for i in x:
 if ch(i):
  ans = 'Possible'
print ans

Measured memory_bytes: 2568
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);


ll h, w;

void solve() {
    ll longer = max(h, w);
    ll shorter = min(h, w);
    ll ans = ll_inf;
    if (h % 3 == 0 || w % 3 == 0) {
        cout << 0 << endl;
        return;
    }
    repone(i, longer - 1) {
        if (shorter % 2 == 0) ans = min(abs(shorter * (i) - (longer - i) * (shorter / 2)), ans);
        else {
            ans = min(max({abs(shorter * (i) - (longer - i) * (shorter / 2)),
                           abs(shorter * (i) - (longer - i) * (shorter / 2 + 1)),
                           abs((longer - i) * (shorter / 2) - (longer - i) * (shorter / 2 + 1))
                          }), ans);
        }
        if (longer - i % 2 == 0) ans = min(abs(shorter * i - (longer - i) / 2 * shorter), ans);
        else {
            ans = min(max({abs(shorter * i - (longer - i) / 2 * shorter),
                           abs(shorter * i - ((longer - i) / 2 + 1) * shorter),
                           abs((longer - i) / 2 * shorter - ((longer - i) / 2 + 1) * shorter)
                          }), ans);
        }
    };
    repone(i, shorter - 1) {
        if (longer % 2 == 0) ans = min(abs(longer * (i) - (shorter - i) * (longer / 2)), ans);
        else {
            ans = min(max({abs(longer * (i) - (shorter - i) * (longer / 2)),
                           abs(longer * (i) - (shorter - i) * (longer / 2 + 1)),
                           abs((shorter - i) * (longer / 2) - (shorter - i) * (longer / 2 + 1))
                          }), ans);
        }
        if (shorter - i % 2 == 0) ans = min(abs(longer * i - (shorter - i) / 2 * longer), ans);
        else {
            ans = min(max({abs(longer * i - (shorter - i) / 2 * longer),
                           abs(longer * i - ((shorter - i) / 2 + 1) * longer),
                           abs((shorter - i) / 2 * longer - ((shorter - i) / 2 + 1) * longer)
                          }), ans);
        }
    };
    cout << ans << endl;
}

int main() {
    cin >> h >> w;
    solve();
    return 0;
}

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

int main()
{
  int h, n;
  cin >> h >> n;
  vector<int>a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  int a_sum = accumulate(a.begin(), a.end(), 0);
  if (h - a_sum <= 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  vector<vector<int> > E(N, vector<int>());
  REP(i, M){
    int a, b; cin >> a >> b; a--; b--;
    E[a].push_back(b);
    E[b].push_back(a);
  }
  vector<int> ans(N, -1);
  vector<int> d(N, 1e9);
  vector<bool> f(N, false);
  queue<int> q;
  q.push(0);
  d[0] = 0;
  f[0] = true;
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(auto i : E[cur]){
      if(f[i]) continue;
      d[i] = d[cur] + 1;
      ans[i] = cur;
      f[i] = true;
      q.push(i);
    }
  }
  cout << "Yes" << endl;
  for(int i = 1; i < N; i++){
    cout << ans[i]+1 << endl;
  }
}

Measured memory_bytes: 10628
using System;

namespace aoj
{
    class Program
    {
        class MyQueue<T>
        {
            private readonly int unitLength;

            public int Count;

            private T[] array;
            private int head;
            private int tail;

            private bool isEmpty { get { return (this.Count <= 0); } }
            private bool isFull { get { return (unitLength <= this.Count); } }

            public MyQueue(int _length)
            {
                this.Count = 0;

                unitLength = _length;
                this.array = new T[unitLength];

                this.head = 0;
                this.tail = 0;
            }

            public T Pop()
            {
                if (isEmpty) { return default(T); }

                var result = this.array[this.head];
                this.array[this.head] = default(T);
                --this.Count;

                this.head = (this.head + 1) % unitLength;
                return result;
            }

            public bool Push(T _value)
            {
                if (isFull) { return false; }

                this.array[this.tail] = _value;
                this.tail = (this.tail + 1) % unitLength;
                ++this.Count;

                return true;
            }
        }

        public struct MyTask
        {
            public MyTask(string _name, int _time)
            {
                this.name = _name;
                this.time = _time;
            }

            public string name;
            public int time;
        }

        static void Main(string[] args)
        {
            string[] tmp = Console.ReadLine().Split(' ');
            var length = int.Parse(tmp[0]);
            var quantum = int.Parse(tmp[1]);
            
            MyQueue<MyTask> taskQueue = new MyQueue<MyTask>(length);
            for (var i = 0; i < length; ++i)
            {
                var input = Console.ReadLine().Split(' ');
                var name = input[0];
                var time = int.Parse(input[1]);
                var task = new MyTask(name, time);
                taskQueue.Push(task);
            }

            int elapsedTime = 0;
            while (0 < taskQueue.Count)
            {
                var task = taskQueue.Pop();
                task.time -= quantum;

                if (0 < task.time)
                {
                    elapsedTime += quantum;
                    taskQueue.Push(task);
                }
                else
                {
                    elapsedTime += quantum + task.time;
                    Console.Write(task.name + " ");
                    Console.WriteLine(elapsedTime);
                }
            }
        }
    }
}



Measured memory_bytes: 21928
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> w(n,0);
  for(auto & x : w){
    cin >> x;
  }
  int all = accumulate(w.begin(), w.end(), 0);
  int s1 = w[0];
  int s2 = all - w[0];
  int c = abs(s2 - s1);
  //cout << s1 << " " << s2 << " " <<abs(s2 - s1) << endl;
  for(unsigned int i = 1; i < w.size() - 1; i++){
    s1 += w[i];
    s2 -= w[i];
    //cout << s1 << " " << s2 << " " <<abs(s2 - s1) << endl;
    c = min(abs(s2 - s1), c);
  }
  cout << c;
  return 0;
}


Measured memory_bytes: 256
import * as fs from 'fs';
const input = (fs.readFileSync('/dev/stdin', 'utf8') as string).split('\n');
const num = parseInt(input[0].replace(' ', ''), 10)
let found = false
for (let i = 0; i <= 1000; i++) {
    if (i * i === num)　{
        found = true
        break
    }
}
console.log(found ? 'Yes' : 'No')

Measured memory_bytes: 7372
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char str[310];
int dp[310][310][310];

int main ()
{
//    freopen ("file.in", "r", stdin);

    fgets (str + 1, 310, stdin);

    int n = strlen (str + 1) - 1, k;
    scanf ("%d", &k);

    int ma = 1;

    for (int lg = 1; lg <= n; ++lg)
        for (int i = 1; i + lg - 1 <= n; ++i)
            for (int h = 0; h <= k; ++h)
            {
                int j = i + lg - 1;

                if (i == j) dp[i][j][h] = 1;
                else
                {
                    dp[i][j][h] = max (max (dp[i + 1][j][h], dp[i][j - 1][h]), dp[i + 1][j - 1][h] + 2 * (str[i] == str[j]));

                    if (h > 0)
                        dp[i][j][h] = max (dp[i][j][h], dp[i + 1][j - 1][h - 1] + 2);

                    ma = max (ma, dp[i][j][h]);
                }
            }

    printf ("%d\n", ma);

    return 0;
}


Measured memory_bytes: 114432
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
#define fast() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define digit(N) cout << fixed << setprecision((N))
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")

struct UnionFind
{
	vector<int> data;
	int component;

	UnionFind(int sz)
	{
		data.assign(sz, -1);
		component = sz;
	}

	bool unite(int x, int y)
	{
		x = root(x), y = root(y);
		if (x == y)
			return false;
		if (data[x] > data[y])
			swap(x, y);
		component--;
		data[x] += data[y];
		data[y] = x;
		return true;
	}

	int root(int k)
	{
		if (data[k] < 0)
			return k;
		data[k] = root(data[k]);
		return data[k];
	}

	int size(int k)
	{
		return (-data[root(k)]);
	}

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

	int connected_component()
	{
		return component;
	}
};

int main()
{
	int N, M;
	cin >> N >> M;
	UnionFind uf(N);
	int ans = N;
	for (int i = 0; i < M; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		x--, y--;
		if (uf.unite(x, y))
			ans--;
	}

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

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;
int main(){
	int n,k;	cin>>n>>k;
	string s;	cin>>s;
	bool rev=false;
	int order=n;
	while(order>=2&&s[order-1]=='A'&&s[order-2]=='B')	order-=2;
	while(order>=2&&k){
		if((rev&&s[0]=='B')||(!rev&&s[0]=='A')){
			s[0]='B'-s[0]+'A';
			k--;
		}
		else{
			rev^=1;
			s.erase(s.begin());
			s+=(rev?"B":"A");
			k--;
		}
		while(order>=2&&((!rev&&s[order-1]=='A'&&s[order-2]=='B')||(rev&&s[order-1]=='B'&&s[order-2]=='A'))){
			order-=2;
		}
	}
	if(k==0){
		if(rev){
			for(int i=0;i<n;i++)	s[i]='B'-s[i]+'A';
		}
		cout<<s<<endl;
		return 0;
	}
	else if(order==0){
		if(rev){
			for(int i=0;i<n;i++)	s[i]='B'-s[i]+'A';
		}
		cout<<s<<endl;
		return 0;
	}
	else{
		k%=2;
		if(rev){
			for(int i=0;i<n;i++)	s[i]='B'-s[i]+'A';
		}
		if(k)	s[0]='B'-s[0]+'A';
		cout<<s<<endl;
		return 0;
	}
}


Measured memory_bytes: 772
# coding: utf-8
N = int(input())
S = input()
letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"
ans = []
for i in range(len(S)):
    ans.append(letters[letters.index(S[i]) + N])
print("".join(ans))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;


int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    ll ans=0;
    sort(all(a));
    rep(i,n){
        for (int j=i-1;j>=0;j--){
            int it=upper_bound(all(a),a[i]-a[j])-a.begin();
            if (it<=j) it++;
            ans+=i-it;
        }
    }
    cout << ans/2 << endl;
}


Measured memory_bytes: 256
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split()))[1:] for _ in range(m)]
  li=[set(x) for x in li]
  p=tuple(map(int,input().split()))
  
  q=set()
  for x in li:
    q|=x
  
  r=set(range(1,n+1))
  v=r-q
  
  ans=0
  
  for i in range(0,len(q)+1):
    for s in itertools.combinations(q,i):
      s=set(s)
      for j,t in enumerate(li):
        u=s&t
        if len(u)%2==p[j]:
          continue
        else:
          break
      else:
        ans+=2**(len(v))
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <numeric>

using namespace std;

int64_t N, ans;

int main() {
    cin >> N;

    ans = 0;
    for(int64_t i=1;i*i<=N;i++){
        if( N % i == 0 ){
            int64_t j = N / i;
            if( 1<i && N / (i-1) == N % (i-1) ) ans += i-1;
            if( 1<j && N / (j-1) == N % (j-1) ) ans += j-1;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input!{
        n: usize,
        d: [[usize; 2]; n],
    }

    let d = d.iter().map(|x| x[0] == x[1]).collect::<Vec<_>>();

    for i in 0..(n-2) {
        if d[i] && d[i+1] && d[i+2] {
            println!("Yes");
            return;
        }
    }

    println!("No");
}


Measured memory_bytes: 2192
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

q = deque([0])
d = [-1]*n
d[0] = 0
ans = [0]*n
print("Yes")

while q:
    p = q.popleft() # 先に入れた要素を取り出す
    for node in g[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node) # リストへの追加
        else:
            if d[node] + 1 == d[p]: # 深さdに対してd+1の関係であるかのチェック
                ans[p] = node + 1

for i in range(1,n):
    print(ans[i])


Measured memory_bytes: 98868
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(unknown_lints)]
#![allow(unused_variables)]
#![allow(unused_must_use)]
#![allow(unused_mut)]
#![allow(dead_code)]
#![allow(unused_assignments)]

use std::collections::HashMap;
use std::process::exit;
use std::io::{
    stdin,
    stdout,
    stderr,
    Read,
    Write,
    BufReader,
    BufWriter
};

macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

macro_rules! stdin {
    () => ({
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    })
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => (
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input.to_string()), $output);
            )*
        }
    )
}

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    println!("{}", solve(stdin!()));
}

fn make_values(v: &Vec<i32>, c: &Vec<i32>, len: usize) -> i32 {
    let mut res: i32 = 0;
    for i in 0..len {
        let value = v[i] / c[i];
        if value > 0 {
            res += v[i] - c[i];
        }
    }
    res
}

fn solve(src: String) -> String {
    let mut res = String::from("");
    input!{
        source = src,
        n: usize,
        v: [i32; n],
        c: [i32; n]
    }
    let x = 0;
    let y = 0;
    let value = make_values(&v, &c, n);
    res.push_str(&value.to_string());
    res.push_str("\n");
    res
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int x,y,s;

int main(){
	while(1){
		cin>>x>>y>>s;
		if(x==0&&y==0&&s==0)break;
		int mm=0;
		for(int i=1;i<=s;i++){
			for(int j=1;j<=s;j++){
				int ii=i*(100+x)/100;
				int jj=j*(100+x)/100;
				if(ii+jj!=s)continue;
				int ki=i*(100+y)/100;
				int kj=j*(100+y)/100;
				mm=max(ki+kj,mm);
			}
		}
		cout<<mm<<endl;
	}
	return 0;
}


Measured memory_bytes: 3076
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()


int main() {
	// ABC075D
	int n, k;
	cin >> n >> k;
	vector<ll>ox(n), oy(n);
	rep(i, n)cin >> ox[i] >> oy[i];
	vector<ll>x(ox), y(oy);
	
	sort(all(x));
	sort(all(y));
	ll ans = 1LL*(x[n - 1] - x[0])*(y[n - 1] - y[0]);
	rep(xi, n) {
		for (int xj = xi + 1; xj < n; xj++) {
			rep(yi, n) {
				for (int yj = yi + 1; yj < n; yj++) {
					int cnt = 0;
					rep(i, n) {
						if (x[xi] <= ox[i] && ox[i] <= x[xj] && y[yi] <= oy[i] && oy[i] <= y[yj])cnt++;
					}

					if (cnt >= k) {
						ll area = (x[xj] - x[xi])*(y[yj] - y[yi]);
						ans = min(ans, area);
					}
				}
			}
		}
	}
	cout << ans << endl;

	return 0;
}





Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

//Turn Left
public class Main{

	double EPS = 1e-10;
	int INF = 1<<29, M = 1000;
	int[] x, y;
	boolean ok(int pre, int v, int next){
		int x1 = x[v]-x[pre], y1 = y[v]-y[pre], x2 = x[next]-x[pre], y2 = y[next]-y[pre];
		return x1*y2-x2*y1>=0;
	}
	
	int[][] pass;
	double[][] d;
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int m = sc.nextInt(), n = sc.nextInt();
			if((m|n)==0)break;
			Map<String, Integer> ref = new HashMap<String, Integer>();
			x = new int[m]; y = new int[m];
			for(int i=0;i<m;i++){
				ref.put(sc.next(), i);
				x[i] = sc.nextInt(); y[i] = sc.nextInt();
			}
			double[][] dist = new double[m][m];
			List<Integer>[] adj = new List[m];
			for(int i=0;i<m;i++)adj[i]=new ArrayList<Integer>();
			while(n--!=0){
				int s = ref.get(sc.next()), t = ref.get(sc.next());
				adj[s].add(t); adj[t].add(s);
				dist[s][t] = dist[t][s] = Math.sqrt((x[s]-x[t])*(x[s]-x[t])+(y[s]-y[t])*(y[s]-y[t]));
			}
			int s = ref.get(sc.next()), g = ref.get(sc.next());
			d = new double[m][m];
			for(double[]a:d)Arrays.fill(a, INF);
			pass = new int[m][m];
			for(int[]a:pass)Arrays.fill(a, INF);
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(m, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					if(Math.abs(d[o1/M][o1%M]-d[o2/M][o2%M])<EPS)return pass[o1/M][o1%M]-pass[o2/M][o2%M];
					return (int)Math.signum(d[o1/M][o1%M]-d[o2/M][o2%M]);
				}
			});
			for(int v:adj[s]){
				d[v][s] = dist[s][v]; pass[v][s] = 2;
				q.add(v*M+s);
			}
			int res = INF;
			while(!q.isEmpty()){
				int a = q.poll();
				int v = a/M, pre = a%M;
				if(v==g){
					res = pass[v][pre];
					break;
				}
				for(int k:adj[v]){
					if(k==pre)continue;
					if(!ok(pre, v, k))continue;
					double w = d[v][pre] + dist[v][k];
					int t = pass[v][pre]+1;
//					if(Math.abs(w-d[k][v])<EPS&&t<pass[k][v]){
//						pass[k][v] = t; q.add(k*M+v);
//					}
//					else 
						if(w<d[k][v]){
						d[k][v] = w; pass[k][v] = t; q.add(k*M+v);
					}
				}
			}
			System.out.println(res==INF?"impossible":res);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
   int n;
   cin>>n;
   bool ok=true;
   rep(i, n){
      int a;
      cin>>a;

      if(a%2==0 && a%3!=0 && a%5!=0) ok=false;
   }

   if(ok) cout<<"APPROVED"<<endl;
   else cout<<"DENIED"<<endl;
   return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

int main()
{
    ll N;
    scanf("%lld", &N);

    ll th = 26;
    ll i;
    for (i = 0; i < 100; i++)
    {
        if (N <= th)
        {
            break;
        }
        N -= th;
        th *= 26;
    }

    if (N != 0)
    {
        N -= 1;
        i++;
    }
    //printf("%lld %lld %lld\n", N, i, th);
    //i文字
    vector<char> ans(i);
    for (ll j = 0; j < i; j++)
    {
        ll k = N / (th / 26);
        //printf("\n%lld %lld %lld ", N, th, k);

        printf("%c", (char)((ll)'a' + k));
        th /= 26;
        N -= k * th;
    }
    printf("\n");
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
int main(){

int n;
cin >> n;
vector<char> s(n);
vector<char> t(n);

for (int i = 0; i < n; i++){
    cin >> s.at(i);
}

for (int i = 0; i < n; i++)
{
    cin >> t.at(i);
}

for (int i = 0; i < n; i++){
    cout << s.at(i) << t.at(i);
}
cout << endl;

return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        int v = n % 1000;
        if (v == 0)
            System.out.println("0");
        else
            System.out.println(1000 - v);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 32844
#include<stdio.h>
int main(){
  int N,p,max=0,sum=0;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&p);
    if(p>max){sum+=max;max=p;}
    else sum+=p;
  }
  sum+=(max/2);
  printf("%d",sum);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int r[4005]={0},g[4005]={0},b[4005]={0},rr[4005]{0},gg[4005]={0},bb[4005]={0};
int main()
{
    int t;
    scanf("%d",&t);
    string s;
    cin>>s;
    for(int i=s.size()-1;i>0;i--)
    {
        if(s[i]=='R')
        {
            r[i]=r[i+1]+1;
            g[i]=g[i+1];
            b[i]=b[i+1];
        }
        else if(s[i]=='G')
        {
            g[i]=g[i+1]+1;
            r[i]=r[i+1];
            b[i]=b[i+1];
        }
        else {
            b[i]=b[i+1]+1;
            g[i]=g[i+1];
            r[i]=r[i+1];
        }
    }
        for(int i=0;i<s.size();i++)
    {
        if(s[i]=='R')
        {
            if(i==0)
                rr[i]=1;
            else{
                rr[i]=rr[i-1]+1;
                gg[i]=gg[i-1];
                bb[i]=bb[i-1];
            }

        }
        else if(s[i]=='G')
        {
            if(i==0)
                gg[i]=1;
            else{
                gg[i]=gg[i-1]+1;
                rr[i]=rr[i-1];
                bb[i]=bb[i-1];
            }

        }
        else {
                if(i==0)
                    bb[i]=1;
                else{
                     bb[i]=bb[i-1]+1;
                     gg[i]=gg[i-1];
                     rr[i]=rr[i-1];
                }

        }
    }
    long long ans=0;
    for(int i=1;i<t-1;i++)
    {
        if(s[i]=='R')
        {
            ans+=gg[i]*b[i];
            ans+=g[i]*bb[i];
            for(int j=0;j<i;j++)
            {
                if(s[j]=='G')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='B')
                        ans--;
                }
                else if(s[j]=='B')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='G')
                        ans--;
                }
            }
        }
        else if(s[i]=='G')
        {
            ans+=rr[i]*b[i];
            ans+=r[i]*bb[i];
            for(int j=0;j<i;j++)
            {
                if(s[j]=='R')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='B')
                        ans--;
                }
                else if(s[j]=='B')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='R')
                        ans--;
                }
            }
        }
        else{
             ans+=rr[i]*g[i];
             ans+=gg[i]*r[i];
             for(int j=0;j<i;j++)
            {
                if(s[j]=='G')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='R')
                        ans--;
                }
                else if(s[j]=='R')
                {
                    if(i+i-j<t)
                    if(s[i+i-j]=='G')
                        ans--;
                }
            }
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3796
#include <stdio.h>

int main(void)
{
	int y1, m1, d1, y2, m2, d2;
	int cnt;
	int ans;
	int i;

	scanf("%d %d %d %d %d %d", &y1, &m1, &d1, &y2, &m2, &d2);

	while(y1 > 0 && m1 > 0 && d1 > 0 && y2> 0 && m2 > 0 && d2 > 0){
		cnt = 0;

		for (i = 1; i < m1; i++){
			if (i == 2 && (y1 % 400 == 0 || (y1 %4 == 0 && y1 % 100 != 0))){
				cnt += 29;
			}
			else if(i == 2){
				cnt += 28;
			}
			else if (i == 4 || i == 6 || i == 9|| i == 11){
				cnt += 30;
			}
			else {
				cnt += 31;
			}
		}

		cnt += d1;
		ans = 365 - cnt;
		if (y1 % 400 == 0 || (y1 %4 == 0 && y1 % 100 != 0)){
			ans++;
		}


		for (i = y1 + 1;  i <= y2; i++){
			ans += 365;
			if (i % 400 == 0 || (i %4 == 0 && i % 100 != 0)){
				ans ++;
			}
		}


		for (i = 12; i >= m2; i--){
			if (i == 2 && (y2 % 400 == 0 || (y2 %4 == 0 && y2 % 100 != 0))){
				ans -= 29;
			}
			else if(i == 2){
				ans -= 28;
			}
			else if (i == 4 || i == 6 || i == 9|| i == 11){
				ans -= 30;
			}
			else {
				ans -= 31;
			}
		}
		ans += d2;
		

		printf("%d\n", ans);
		scanf("%d %d %d %d %d %d", &y1, &m1, &d1, &y2, &m2, &d2);
	}

	return (0);
}

Measured memory_bytes: 596
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int[] v = new int[100010];

		for (int i = 0; i < n; i++) {
			v[i] = Integer.parseInt(sc.next());
		}

		Integer[] vo = new Integer[100010];
		Integer[] ve = new Integer[100010];
		Integer[] vt = new Integer[100010];
		Arrays.fill(vo, 0);
		Arrays.fill(ve, 0);
		Arrays.fill(vt, 0);

		for (int i = 0; i < n; i++) {
			vt[v[i]]++;
			if (i % 2 == 0) {
				ve[v[i]]++;
			} else {
				vo[v[i]]++;
			}
		}

		Arrays.sort(vo, Collections.reverseOrder());
		Arrays.sort(ve, Collections.reverseOrder());
		Arrays.sort(vt, Collections.reverseOrder());

		int ans = 0;

		if (vo[0] + ve[0] == vt[0]) {
			ans = Math.min(n - vo[0] - ve[1], n - vo[1] - ve[0]);
		} else {
			ans = n - vo[0] - ve[0];
		}
		System.out.println(ans);

		sc.close();
	}

}

Measured memory_bytes: 48324
mod = 10**9 + 7
x,y = map(int,input().split())
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
if (x + y)%3 != 0 :
    print(0)
else :
    n = int((x + y)/3) 
    if x - n < 0 or y - n < 0:
        print(0)
    else:
        ans = cmb(n,x-n)
        print(ans%mod)


Measured memory_bytes: 102028
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("Ofast")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>

using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define sfind(i) (*find_by_order(i))
// #define ord(i) order_of_key(i)
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define mod 1000000007
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define repc(i, a, b, c) for (ll i = a; (c > 0 ? i < b : i > b) and c != 0; i += c)
#define vi vector<int>
#define vl vector<ll>
#define _max(vec) (*max_element(all(vec)))
#define _min(vec) (*min_element(all(vec)))
#define fi first
#define si second
#define pb push_back
#define all(name) name.begin(), name.end()
#define ral(name) name.rbegin(), name.rend()
#define fact(n) rep(i, 1, n+1)ft.pb((ft[i-1]*i)%mod)
#define mod_in(a) power(a, mod - 2)
#define ncr(n, r) (n>=r?((ft[n]*mod_in((ft[r]*ft[(n)-(r)])%mod))%mod):0LL)
#define deb(x) cerr << "[" << #x << " " << x << "]" << endl;
#define endl '\n'  //....????
#define int ll
vector<ll> ft(1, 1LL);
/*======================================================================*/

void solve() {
    int ans = 0;
    int n;
    cin >> n;
    for(int i = 2; i*i < n; i++){
        int c = 0;
        while(n%i == 0)c++, n /= i;
        int x = 0;
        while(((x+2)*(x+1))/2 <= c)x++;
        ans += x;
    }
    ans += (n!=1);
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> Vector;
typedef vector<vector<ll>> DVector;

#define fi          first
#define se          second
#define pb          push_back
#define INF         INT_MAX/3
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define dbg(x)      cout<<#x"="<<x<<endl
#define ub(x,y)     upper_bound(all(x),y)-x.begin()
#define lb(x,y)     lower_bound(all(x),y)-x.begin()
#define uni(x)      x.erase(unique(all(x)),x.end())
#define rep(i,n)    repl(i,0,n-1)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<int>())
#define mkp(x,y)    make_pair(x,y)
ll gcd(ll a,ll b){
  if(b>a)gcd(b,a);
  ll r = a%b;
  if(r==0)return b;
  return gcd(b,r);
}

int main(){
  cin.sync_with_stdio(false);
  int n;
  cin >> n;
  Vector t(n);
  rep(i,n)cin >> t[i];
  rep(i,n-1) t[i+1] = t[i]*(t[i+1]/gcd(t[i],t[i+1]));
  cout << t[n-1]<< endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, k, t;
vector<int> edge[2001];

pii dfs(int x, int p, int d) {
    pii ret = pii(0, 0);
    if (k + 1 < d) ret.first = 1;
    else if (k + 1 == d) ret.second = 1;
    for (int i : edge[x]) {
        if (i == p) continue;
        pii c = dfs(i, x, d + 1);
        ret.first += c.first;
        ret.second += c.second;
    }
    return ret;
}

int getAns(int x) {
    int sum = 0, mx = 0;
    
    for (int i : edge[x]) {
        pii ret = dfs(i, x, 1);
        sum += ret.first + ret.second;
        mx = max(mx, ret.second);
    }
    return sum - mx * t;
}

int main() {
    int x, y;
    scanf("%d%d", &n, &k);
    t = k & 1;
    k /= 2;
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int ans = n;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, getAns(i));
    }
    printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const string YES = "YES";
const string NO = "NO";

int main(){
    ll a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;
    if(t * (v - w) >= abs(a - b)){
        cout << YES << endl;
    }else{
        cout << NO << endl;
    }
    return 0;
}


Measured memory_bytes: 3640
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

int main(){
	ll n, k; cin>>n>>k;
	vector<int> v(n); rep(i, n) cin>>v[i];
	map<ll, ll> d;
	rep(i, n) d[v[i]]++;
	vector<ll> a; a.reserve(n);
	for(auto x: d){
		a.push_back(x.snd);
	}
	sort(all(a));
	ll res = 0;
	for(int i = 0; i < (int)a.size()-k; i++){
		res += a[i];
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 15104
from math import factorial

def nCr(n, r):
  return factorial(n) // (factorial(n - r) * factorial(r))
  
mod = 10**9 + 7 
 
N,K = map(int,input().split())

for i in range(K):
  if (N - K - i) < 0:
    print(0)
  else:
    # 赤を仕切りと考える、仕切りの左右には箱(N-K+1個)がある、その中のどの箱(i+1個)を用いるか
    box_comb = nCr(N-K+1, i+1) % mod
    # 各箱にK個の青を入れる組み合わせ、空箱はナシ→K個の青の間(K-1)に仕切りをi個入れる
    blue_comb = nCr(K-1, i) % mod
    print((box_comb * blue_comb) % mod)

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

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7


B0=[]

for i in range(N):
    ANS=0
    k=A[i]
    for j in range(i+1,N):
        if A[j]<k:
            ANS+=1

    B0.append(ANS)

count=[0]*(max(A)+1)

for a in A:
    count[a]+=1

from itertools import accumulate
S=list(accumulate(count))

ANS=0

for i in range(N):
    t=S[A[i]-1]
    ANS=(ANS+B0[i]*K+t*K*(K-1)//2)%mod

print(ANS)


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

int main() {
    int X;
    cin >> X;
    int list[6] = {100, 101, 102, 103, 104, 105};
    int a = X / list[0];
    if (X > a * list[5])
    {
        cout << 0 << endl;
    } else
    {
        cout << 1 << endl;
    }
    
    

  return 0;
}

Measured memory_bytes: 256
import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019

#print(b)
for i in reversed(range(0, n)):
 #   print((b[n-i-1])*int(s[i]) % 2019)
    k += (b[n-i-1])*int(s[i]) % 2019
  #  print(k, k % 2019)
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)


Measured memory_bytes: 16452
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int K ,N;
    cin >> K >>N;
    vector<int> vec(N);
    for(int i=0;i<N;i++){
        cin >>vec.at(i);
    }
    int sum=0;
    for(int i=1;i<N;i++){
        int sumsum=0;
        sumsum = vec.at(i)-vec.at(i-1);
        sum =max(sum,sumsum);
     }
      int MINMIN=0;
      MINMIN=max(vec.at(0)+K-vec.at(N-1),sum);
      cout << K -MINMIN <<endl;
}

Measured memory_bytes: 4036
n = int(input())

pos_max = 100000

dic = dict()

for _ in range(n):
    x, y = map(int, input().split())
    y += pos_max
    if not x in dic:
        dic[x] = set()
    if not y in dic:
        dic[y] = set()
    dic[x].add(y)
    dic[y].add(x)
checked = set()

count = 0
for x in dic:
    if x in checked:
        continue
    checked.add(x)

    member = {x}
    next_items = {x}
    while next_items:
        v = next_items.pop()
        member |= dic[v]
        next_items |= dic[v] - checked
        checked |= dic[v]
    x_n = sum(w <= pos_max for w in member)
    y_n = sum(w >  pos_max for w in member)
    count += x_n * y_n
print(count - n)

Measured memory_bytes: 131220
S = input()
MOD = 10**9 + 7
# A,B,Cまで作れた個数、および保留中
a,b,c,d = 0,0,0,1

for s in S:
  if s == 'A':
    a += d
    a %= MOD
  elif s == 'B':
    b += a
    b %= MOD
  elif s == 'C':
    c += b
    c %= MOD
  else:
    # 使わなかった ? 分も増える
    a,b,c,d = 3*a+d,3*b+a,3*c+b,3*d
    a %= MOD
    b %= MOD
    c %= MOD
    d %= MOD

answer = c
print(c)

Measured memory_bytes: 3188
import math

def main():
    N, P = map(int, input().split())
    A = tuple(map(int, input().split()))

    for i in range(N):
        if A[i] % 2:
            odd = 1
            break
    else:
        odd = 0

    if odd:
        ans = 2 ** (N - 1)
    else:
        if P:
            ans = 0
        else:
            ans = 2 ** N

    print(ans)

main()


Measured memory_bytes: 3060
import heapq

k = int(input())

num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
mae = 0

if k <= 9:
    print(k)
else:
    k -= 9
    q = []
    heapq.heapify(q)
    for i in range(1, 10):
        heapq.heappush(q, i)
    temp = 0
    while temp < 9:
        temp += 1
        num = heapq.heappop(q)
        if temp == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
    while k > 0:
        k -= 1
        num = heapq.heappop(q)
        if num == mae:
            k += 1
            continue
        elif num%10 == 0:
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        elif num%10 == 9:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
        else:
            heapq.heappush(q, num*10 + num_list[(num%10)-1])
            heapq.heappush(q, num*10 + num_list[(num%10)])
            heapq.heappush(q, num*10 + num_list[(num%10)+1])
        mae = num
    print(num)


Measured memory_bytes: 19544
/*
    A - Changing a Character
    https://atcoder.jp/contests/abc126/tasks/abc126_a
*/
#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (i == k - 1)
            cout << (char)(s[i] + 32);
        else
            cout << s[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
// Code for A - Disjoint Set Union
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
	int N, q;

  cin >> N >> q;

	dsu d(N);

	while(q--){
		int t, u, v;
		cin >> t >> u >> v;
		if (t == 0) {
      d.merge(u, v);
    } else {
      cout << d.same(u,v) << endl;
    }
	}
	return 0;
}


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

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

using namespace std;

int main(){
	int h,w; cin>>h>>w;
	int hist[128]={};
	rep(i,h){
		string s; cin>>s;
		rep(j,w) hist[s[j]]++;
	}

	if(h%2==0 && w%2==0){
		for(int c='a';c<='z';c++){
			if(hist[c]%4!=0) return puts("No"),0;
		}
		puts("Yes");
	}
	else if(h%2==0 || w%2==0){
		if(h%2==1) swap(h,w);

		int two=0;
		for(int c='a';c<='z';c++){
			if(hist[c]%2==1) return puts("No"),0;
			if(hist[c]%4==2) two++;
		}
		puts(two<=h/2?"Yes":"No");
	}
	else{
		int one=0;
		for(int c='a';c<='z';c++){
			if(hist[c]%2==1) one++;
		}
		if(one!=1) return puts("No"),0;

		for(int c='a';c<='z';c++){
			if(hist[c]%2==1) hist[c]--;
		}

		int two=0;
		for(int c='a';c<='z';c++){
			if(hist[c]%4==2) two++;
		}
		puts(two<=h/2+w/2?"Yes":"No");
	}

	return 0;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n , W;
	scanf("%d%d",&n,&W);
	vector<ll> dp(W+1,0);// dp[i] is max value at weight i
	for(int i = 0 ; i < n ; ++i){
		ll weight , value;	
		scanf("%lld%lld",&weight , &value);
		for(int j = W - weight ; j >= 0 ; j--){
			dp[j+weight] = max(dp[j+weight] , dp[j] + value);	
		}
	}
	ll ans = 0;
	for(ll i:dp){
		ans = max(ans , i);	
	}
	printf("%lld\n",ans);
	return 0;	
}


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

const int MOD = (int)1e9+7;

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

	vector<string> ans={"SUN","MON","TUE","WED","THU","FRI","SAT"};
	for(int i=0;i<7;i++){
		if(ans.at(i)==S)	cout << 7-i << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public Main(int opt1, int opt2) {
		String[] A = {"f","t","t","t"};
		A[opt1]="f";
		A[opt2]="f";
		for(int i =1; i<4; i++)
		{
			if(A[i]=="t")
			{
				System.out.println(i);
				break;
			}
		}
 
	}
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int opt1 = sc.nextInt();
		int opt2 = sc.nextInt();
		Main m = new Main(opt1, opt2);
	}	
}

Measured memory_bytes: 22868