akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        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:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

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

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        a: i64, b: i64,
    }
    for i in 1..10000 {
        if i * 8 / 100 == a && i * 10 / 100 == b {
            puts!("{}\n", i);
            return;
        }
    }
    puts!("-1\n");
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

using namespace std;

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

	int is4 = false;
	for (int i = 0; i < n; i++) {
		cin >> c;
		if (c == 'Y') {
			is4 = true;
			break;
		}
	}
	cout << (is4 ? "Four" : "Three") << endl;

	return 0;
}


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

int main(void){
  int n;
  std::vector<int> d;
  int tmp;
  int min,max;
  std::cin >> n;
  for(int i = 0; i < n; i++){
    std::cin >> tmp;
    d.push_back(tmp);
  }
  std::sort(d.begin(),d.end());

  int mid = n / 2;
  min = d[mid-1];
  max = d[mid];


  std::cout << (max - min);
  return 0;
}

Measured memory_bytes: 892
h, w = map(int, input().split())
a = [''] * h
for i in range(h):
	a[i] = input()

row = [False] * h
col = [False] * w
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			row[i] = True
			col[j] = True

for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j], end = '')
		print()

Measured memory_bytes: 4468
;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 1))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))))

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))


;; Hauptteil

(deftype uint nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (let ((n (read))
        (s-lst nil))
    (loop for i from 0
          with sum = 0
          when (= sum n)
            do (loop-finish)
          do (let ((b (if (zerop (mod (- n sum) (expt 2 (1+ i))))
                          0
                          1)))
               (push b s-lst)
               (when (= b 1)
                 (incf sum (expt -2 i)))))
    (if (null s-lst)
        (print-line 0)
        (dolist (s s-lst (terpri))
          (princ s)))))

#-swank(main)


Measured memory_bytes: 16232
use std::collections::HashSet;

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().split_whitespace()
        .map(|x| x.parse().ok().unwrap()).collect()
}

fn main() {
    let AB = read_vec::<i64>();
    println!("{}", vec!(AB[0] + AB[1], AB[0] - AB[1], AB[0] * AB[1]).iter().max().unwrap());
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mp(x,y)     make_pair(x,y) 
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,a,n)   for(ll i=a;i<n;i++)
#define frr(i,a,n)  for(ll i=n-1;i>=a;i--)


const ll N   =  500005;
const ll mod = 1e9 + 7;

using namespace std;


void solve()
{
// string s;
  ll n,m,k,x=0,y=0,c=0,q,ans=0;
  cin>>n>>m>>k;
  x = k/n;
  c(m*x);
}

signed main(){
    
      ios_base::sync_with_stdio(false);   
      cin.tie(NULL);
      ll T=1;
      //cin>>T;
      while(T--)
      {
      solve();
      }
      return 0;
    }


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

#define ll long long
#define mx 100005

int ar[mx];
char ch[mx];
int n,m;

void solve()
{
    string s,tem;
    cin>>s;
    tem=s;
    reverse(s.begin(),s.end());
    if(tem!=s)
    {
        cout<<"No\n";
        return;
    }
    int len=(s.size()-1)/2;
    string tt="";
    for(int i=0;i<len;i++)tt+=tem[i];
    string ss=tt;
    reverse(ss.begin(),ss.end());
    if(ss!=tt)
    {
        cout<<"No\n";
        return;
    }
    len=(n+3)/2;
    tt="";
    for(int i=len-1;i<tem.size();i++)tt+=tem[i];
     ss=tt;
    reverse(ss.begin(),ss.end());
    if(ss!=tt)
    {
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}

int main()
{
    int t=1;
    while(t--)solve();
    return 0;
}


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

int main(){
  int N;
  cin >> N;
  int64_t sum = 0;
  for (int i = 1;i <= N; i++){
      if((i % 3 == 0)||(i % 5 == 0)){sum = sum + 0;}
      else{sum = sum + i;}
  }
  cout << sum << endl ;
}

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

class AGC027_A
{
    static void Main()
    {
        int sum = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList()[1];
        List<int> foods = Console.ReadLine().Split(' ').Select(x=>int.Parse(x)).ToList();
        foods.Sort();
        int happyChild=0;
        /*foreach(int food in foods)
        {
            if(sum-food >= 0)
            {
                sum -= food;
                happyChild++;
            }
            else
                break;
        }*/
        for(int i = 0; i < foods.Count();i++)
        {
            int food=foods[i];
            if(i+1 == foods.Count() && sum != food)
            {
                break;
            }
            if(sum-food < 0)
            {
                break;
            }
            if(sum-food >= 0)
            {
                sum -= food;
                happyChild++;
            }
        }
        Console.WriteLine(happyChild);
    }
}

Measured memory_bytes: 11348
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first fi;
#define second se;
using namespace std;
typedef pair<int, int> P;

signed main(){
    string s;
    int a;
    cin >> s >> a;
    s += "+0";
    vector<int> d;
    int now = s[0] - '0';
    int nowl = now;
    rep(i, 0, s.size() / 2){
        
        char c = s[i * 2 + 1];
        int tmp = s[i * 2 + 2] - '0';
        if(c == '+'){
            now += tmp;
            d.push_back(nowl);
            nowl = tmp;
         }else{
             now *= tmp;
             nowl *= tmp;
         }
    }
    int sum = 0;
    rep(i, 0, d.size()) sum += d[i];
    if(a == sum && a == now) cout << "U" << endl;
    else if(a == sum) cout << "M" << endl;
    else if(a == now) cout << "L" << endl;
    else cout << "I" << endl;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int N,M;
    cin >> N >> M;
    vector<int> A(N);
    double all;
    all =0;
    for (int i = 0; i < N; i++)
    {
        cin >>  A.at(i);
        all = all + A.at(i); 
    }
    sort(A.begin(),A.end(),greater<int>());
    if (A.at(M-1) >= all/(4*M))
    {
        cout << "Yes";
    }else
    {
        cout << "No";
    }    
}


Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) {
		try {

			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			String str = reader.readLine();
			String[] points = str.split(" ");
			double a = Double.parseDouble(points[0]);
			double b = Double.parseDouble(points[1]);
			double c = Double.parseDouble(points[2]);
			
			double S = a * b * Math.sin(Math.toRadians(c)) / 2;
			double L = a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Math.toRadians(c)));
			double h = b * Math.sin(Math.toRadians(c));
			
			System.out.println(S + " " + L + " " + h);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 24316
require 'set'

def main
    a,b,m = gets.chomp.split(" ").map(&:to_i)
    as = gets.chomp.split(" ").map(&:to_i)
    bs = gets.chomp.split(" ").map(&:to_i)
    ds = m.times.map { gets.chomp.split(" ").map(&:to_i) }

    as_sort = as.sort
    bs_sort = bs.sort
    ans = as_sort[0] + bs_sort[0]
    (0..m-1).each do |i|
        price = as[ds[i][0]-1] + bs[ds[i][1]-1] - ds[i][2]
        ans = price if ans > price
    end
    puts ans
end

main

## イディオムなど
# until s.empty? do
#
## 配列のインデックス
# s[0,6] # 0番目から6文字
# s[0..6] # 0番目から6番目まで
# s[5..-1] # 5番目から最後まで
#
## 全探索
# [0, 1].repeated_permutation(n) do |combination| # bit全探索
# array.combination(i) do |selected| # array から要素が i 個である部分列を全部抽出
#
## 無向グラフの幅優先探索(BFS)
# to = Array.new(n).map{Array.new()} # ある頂点と繋がる頂点のリスト
# m.times do
#     a,b = gets.chomp.split(" ").map(&:to_i)
#     to[a].push b
#     to[b].push a
# end
# q = Queue.new # BFS は queue
# ds = Array.new(n, -1)
# pre = Array.new(n, -1)
#
## その他
# a1 = Marshal.load(Marshal.dump(a2)) # 深いコピー
# matrix = Array.new(n).map{Array.new()} # 二次元配列の初期化
# 

Measured memory_bytes: 22188
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let s = read::<String>().chars().collect::<Vec<char>>();
    if n % 2 != 0 {
        println!("No");
        return;
    }
    if s[..n / 2] == s[n / 2..] {
        println!("Yes");
    } else {
    println!("No");
    }
}


Measured memory_bytes: 2168
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif
#include <iostream>
#include <vector>
using namespace std;

vector<int> dfs(int to,int use){
	vector<int> ret,add;
	if(use == 0 || __builtin_popcount(to&use)%2==0){
		return ret;
	}
	int dif = 0;
	while((use&(1<<dif))==0 || (to&(1<<dif))==0)
		dif++;
	if(__builtin_popcount(use)==1){
		ret.push_back(dif);
		return ret;
	}
	int nuse = use^(1<<dif);
	int change = 0;
	while((use&(1<<change))==0 || (change==dif) )
		change++;
	int mid = (1<<change);
	ret = dfs(mid,nuse);
	ret.push_back(dif);
	add = dfs((to^mid),nuse);
	ret.insert(ret.end(),add.begin(),add.end());
	return ret;
}

int main(){
	int N,A,B;
	cin>>N>>A>>B;
	vector<int> ans;
	ans = dfs(A^B,(1<<N)-1);
	int begin = A;
	if(ans.size()==0){
		cout<<"NO"<<endl;
	}else{
		cout<<"YES"<<endl;
		cout<<begin<<" ";
		for(int i = 0;i < ans.size();i++){
			begin ^= (1<<ans[i]);
			cout<<begin;
			if(i+1 < ans.size()){
				cout<<" ";
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 1648
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <deque>
using namespace std;

#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(e, elem) for(auto& (e) : (elem))
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define all(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e);
using ll = long long;
using ull = unsigned long long;

vector<double> v;

int main() {
    int n;
    cin >> n;
    rep(i, n){
        double a;
        cin >> a;
        v.pb(a);
    }

    sort(all(v));

    double ans = (v[0] + v[1]) / 2;
    for(int i = 2; i < n; ++i){
        ans = (ans + v[i]) / 2;
    }

    println(ans);
}


Measured memory_bytes: 256
// 8/2 リアルタイム参加
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;

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

    // int ans = -1;

    // for (ll ans = K; ans <= K * K; ans += K) {
    //     ostringstream oss;
    //     oss << ans;
    //     string s = oss.str();

    //     bool ok = true;
    //     for (auto c : s) {
    //         if (c != '7') {
    //             ok = false;
    //             break;
    //         }
    //     }
    //     if (ok) {
    //         ans = s.size();
    //         break;
    //     }
    // }

    // cout << ans << endl;

    int count = 0;
    int now = 0;
    int ok = false;

    while (count < K) {
        now = now * 10 + 7;
        now %= K;
        count++;
        if (now == 0) {
            ok = true;
            break;
        }
    }

    if (ok) {
        cout << count << endl;
    } else {
        cout << "-1" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
import math
k = int(input())
b = 3*k*k - 3*k + 1
for i in range(2,k+1):
    for j in range(2,k+1):
        ij = math.gcd(i,j)
        for m in range(2,k+1):
            b += math.gcd(ij,m)
print(b)

Measured memory_bytes: 9116
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXH=1e4+5,MAXN=1005;
int h,n,a[MAXN],b[MAXN];
int f[MAXH];
int main(){
	scanf("%d%d",&h,&n);
	for(int i=1; i<=n; i++)
		scanf("%d%d",a+i,b+i);
	for(int i=1; i<=h; i++){
		f[i]=2e9;
		for(int j=1; j<=n; j++)
			f[i]=min(f[i],a[j]>i?b[j]:b[j]+f[i-a[j]]);
	}
	printf("%d\n",f[h]);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = 998244353ll;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll memo[4444][4444];
bool done[4444][4444];

int m,r[4444],b[4444];

ll solve(int i, int j){
	if(done[i][j]){
		return memo[i][j];
	}
	done[i][j] = true;
	if(i>r[i+j] || j>b[i+j]){
		return memo[i][j] = 0ll;
	}
	if(i+j==m){
		return memo[i][j] = 1ll;
	}
	memo[i][j] = solve(i+1,j)+solve(i,j+1);
	memo[i][j] %= MOD;
	return memo[i][j];
}

int main(void){
	int n,i;
	std::string s;
	std::cin >> s;
	n = s.l_ength(); m = n*2;
	for(i=0; i<n; ++i){
		r[i+1] = s[i]-'0';
		b[i+1] = '2'-s[i];
	}
	for(i=1; i<m; ++i){
		r[i+1] += r[i];
		b[i+1] += b[i];
	}
	std::cout << solve(0,0) << std::endl;
	return 0;
}


Measured memory_bytes: 160000
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int N, input, maxv, minv;
	cin >> N;

	cin >> input;
	minv = input;
	maxv = -input;
	for (int i = 1;i < N;i++)
	{
		cin >> input;
		maxv = max(maxv, input - minv);
		minv = min(minv, input);
	}

	cout << maxv << endl;

	return 0;
}

Measured memory_bytes: 1160
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

from collections import defaultdict
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
UF=UF(h*w)
for i in range(h):
  for j in range(w):
    if i!=0:
      if s[i][j]!=s[i-1][j]:UF.unite(i*w+j,(i-1)*w+j)
    if i!=h-1:
      if s[i][j]!=s[i+1][j]:UF.unite(i*w+j,(i+1)*w+j)
    if j!=0:
      if s[i][j]!=s[i][j-1]:UF.unite(i*w+j,i*w+(j-1))
    if j!=w-1:
      if s[i][j]!=s[i][j+1]:UF.unite(i*w+j,i*w+(j+1))
listB=[0 for i in range(h*w)]
listW=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      listB[UF.find_root(i*w+j)]+=1
    else:
      listW[UF.find_root(i*w+j)]+=1
ct=0
for i in range(h*w):
  ct+=listB[i]*listW[i]
print(ct)

Measured memory_bytes: 15048
n,p = map(int,input().split())
L = list(map(int,input().split()))
Le = [x for x in L if x%2 == 0]
Lo = [x for x in L if x%2 == 1]

if p == 0:
    if len(Lo) == 0:
        print(2**n)
    else:
        print(2**(n-1))
if p == 1:
    if len(Lo) == 0:
        print(0)
    else:
        print(2**(n-1))

Measured memory_bytes: 3064
//Apparat : drobucs, aleonov, vit_72
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <iomanip>
#include <algorithm>
#include <string>
#include <queue>
#include <numeric>

//#pragma warning(disable : 4996)
//#pragma GCC optimize("O3")

using namespace std;

#define nptr nullptr
#define all(x) (x).begin(), (x).end()
#define drobucs ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()

typedef  long long ll;

const int maxn = (int)1e6 + 13;
const ll INFL = 9223372036854775807;
const ll INF = 2147483647;
const ll MOD = (int)1e9 + 7, MOD2 = 998244353;//1e9 + 21, 1e9 + 33, 1e9 + 87, 1e9 + 93
const ll base = 101, base2 = 37;
bool vis[maxn];
int ans[maxn];
vector<int> gr[maxn];
void dfs(int v) {
	vis[v] = 1;
	for (auto t : gr[v])
		if (!vis[t])dfs(t);
}

int main() {
	drobucs;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	int cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (!vis[i])dfs(i), cnt++;
	if (cnt > 1) {
		cout << "No\n";
		return 0;
	}
	fill(vis, vis + n + 100, 0);
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		vis[v] = 1;
		for (auto t : gr[v]) {
			if (!vis[t]) {
				q.push(t);
				vis[t] = 1;
				ans[t] = v;
			}
		}
	}
	cout << "Yes\n";
	for (int i = 2; i <= n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Measured memory_bytes: 33684
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll n, i, k;
    vector <pll> a;
    vll dp;
    cin >> n >> k;
    ll l = 1;
    while(l <= n)
    {
        ll r = n / (n / l);
        a.pb(mp(n / l, r - l + 1));
        l = r + 1;
    }
    dp.resize(a.size());
    vll pre(a.size(), 0);
    for(i = 0; i < dp.size(); i++)
        dp[i] = a[i].S;
    pre[0] = dp[0];
    for(i = 1; i < a.size(); i++)
        pre[i] = (pre[i - 1] + dp[i]) % mod;
    for(i = 1; i < k; i++)
    {
        ll ptr = a.size() - 1;
        for(ll j = 0; j < a.size(); j++, ptr--)
            dp[j] = (a[j].S * pre[ptr]) % mod;
        pre[0] = dp[0];
        for(ll j = 1; j < a.size(); j++)
            pre[j] = (pre[j - 1] + dp[j]) % mod;
    }
    cout << pre[a.size() - 1] << endl;
    return 0;
}

Measured memory_bytes: 2292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define fori(i, m, n) for(int i = m; i < (int)n; i++)
#define forl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define all(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string btos(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  string n;cin>>n;
  bool ans=true;
  if(n=="AAA"||n=="BBB"){
    ans=false;
  }
  cout<<btos(ans)<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [N] = string_to_int(inputs[0])
    V = string_to_int(inputs[1])
    C = string_to_int(inputs[2])

    ret = 0
    for i, _ in enumerate(V):
        if V[i] - C[i] > 0:
            ret += V[i] - C[i]
    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(3))
    print(ret)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

// input
int N;
long long h[100010];

// DP table
long long dp[100010];

long long rec(int i) {
    if (dp[i] < INF) return dp[i];
    
    if (i == 0) return 0;

    long long res = INF;
    chmin(res, rec(i-1) + abs(h[i] - h[i - 1]));
    if (i > 1) chmin(res, rec(i-2) + abs(h[i] - h[i - 2]));

    return dp[i] = res;
}

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

    // initialization
    for (int i = 0; i < N; ++i) dp[i] = INF;

    // answer
    cout << rec(N-1) << endl;
}

Measured memory_bytes: 6528
using System;
using System.Collections.Generic;

namespace AtCoder
{
    internal static class Program
    {
        private static void Main()
        {
            int S = int.Parse(Console.ReadLine());
            List<int> fn = new List<int>();
            int res = -1;
            fn.Add(S);

            for (int i = 0; i < 1000000; i++)
            {
                if (S % 2 == 0)
                    S /= 2;
                else
                    S = S * 3 + 1;

                fn.Add(S);

                for (int y = 0; y < fn.Count; y++)
                {
                    for (int x = 0; x < fn.Count && x != y; x++)
                    {
                        if (fn[y] == fn[x])
                        {
                            res = fn.Count;
                            break;
                        }
                    }
                }

                if (res != -1)
                    break;
            }

            Console.WriteLine(res);
        }
    }
}

Measured memory_bytes: 13140
// 解き直し.
// ABC 118 解説.
// https://img.atcoder.jp/abc118/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
const int MATCH[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
int dp[12321];
struct match{
    int n; // マッチ棒で表現する数字.
    int u; // 数字1文字を構成するのに必要なマッチの使用本数.
    bool operator<(const match& rhs) const {
        return (u < rhs.u) || ((u == rhs.u) && (n > rhs.n));
    }
};

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<match> A;
    FOR(i, 0, M){
        int a;
        scanf("%d", &a);
        match m;
        m.n = a, m.u = MATCH[a - 1];
        A.push_back(m);
    }
    
    // 2. 初期化, sort.
    FOR(i, 0, N + 1) dp[i] = -123454321;
    sort(A.begin(), A.end());
    // for(auto &a : A) printf("%d %d\n", a.u, a.n);
    
    // 3. 解説通り.
    // dp[i]: ちょうどi本のマッチ棒を使って, 条件を満たす整数を作る場合の最大桁数.
    dp[0] = 0;
    FOR(i, 1, N + 1) for(auto &a : A) if(i >= a.u) dp[i] = max(dp[i], dp[i - a.u] + 1);
    // printf("dp[%d]=%d\n", N, dp[N]);
    
    // 4. dp の 結果をもとに, 出力.
    while(N > 0){
        // 4-1. 最上位の桁 を 抽出.
        int d = 0;
        for(auto &a : A){
            // a.n が 最上位の桁 に使えるかどうかは, 
            // dp[N - a.u] = dp[N] - 1 であるかを確認すれば良い, とのこと.
            if(N - a.u >= 0 && dp[N - a.u] == dp[N] - 1) d = max(d, a.n);
        }
        // 4-2. 最上位の桁が確定したので, 未使用のマッチ棒の本数 N を デクリメント.
        N -= MATCH[d - 1];
        printf("%d", d);
    }
    return 0;
    
}

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

using namespace std;

int main()
{
    int n;
    cin>>n;
    bool flag = false;

    for(int i=0;i<=floor(n/4);i++)
    {
        for(int j=0;j<=floor(n/7);j++)
        {
            if(n==4*i+7*j)
            {
                flag = true;
            }
        }
    }
    if(flag)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
)

func main() {
	sc := NewScanner()

	n := sc.NextInt()

	mp := map[int]int{}
	for i := 0; i < n; i++ {
		tmp := sc.NextInt()
		mp[tmp] = i + 1
		//		fmt.Printf("%+v %v\n", i+1, tmp) // output for debug
	}
	//	fmt.Printf("%+v\n", mp) // output for debug

	for i := 1; i <= n; i++ {
		fmt.Printf("%+v ", mp[i]) // output for debug
	}
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 8448
n = int(input())
def calc(c, p):
    res = 0
    while c:
        res += c % p
        c = c // p
    return res
ans = n
for i in range(n+1):
    cand = calc(i, 6) + calc(n - i, 9)
    ans = min(ans, cand)
print(ans)


Measured memory_bytes: 41964
N = int(input())
p = [int(i) for i in input().split(" ")]
p.insert(0,10000)
need_swap = [0 for i in range(N+1)]
for index,value in enumerate(p):
    if index == value:
        need_swap[index] = 1
flag = 0
double = 0
for i in need_swap:
    if flag == 0 and i == 1:
        flag = 1
    elif flag == 1 and i == 1:
        double += 1
        flag = 0
    elif flag == 1 and i == 0 :
        flag = 0
print(sum(need_swap)-double)

Measured memory_bytes: 13880
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int h,w;
    cin>>h>>w;
    int dp[10][10];
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cin>>dp[i][j];
        }
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            for(int k=0;k<10;k++){
                for(int ii=0;ii<10;ii++){
                    dp[j][k]=min(dp[j][k],dp[j][ii]+dp[ii][k]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<h*w;i++){
        int a;
        cin>>a;
        if(a!=-1){
            ans+=dp[a][1];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	fmt.Println(resolve(parseProblem()))
}

func parseProblem() int {
	s := scanString(sc)
	max, num := 0, 0
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case 'S':
			if max < num {
				max = num
			}
			num = 0
		case 'R':
			num++
		}
	}
	if max < num {
		max = num
	}
	return max
}

func resolve(n int) int {
	return n
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main() {
  using lint = long long int;
  using P = pair<lint, lint>;

  int n;
  lint t;
  cin >> n >> t;
  vector<lint> a(n);
  map<lint, int> pos;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  ///最大の利益を達成するペアを探す
  P max_pair = {a[0], 0};
  P temp = {a[0], 0};
  auto benefit = [&](P p)
  {
    lint b = p.first * (n / 2);
    lint s = p.second * (n / 2);
    return s - b;
  };
  for (int i = 1; i < n; ++i) {
    if(a[i] > temp.second)
    {
      temp.second = a[i];
    }else if(a[i] < temp.first)
    {
      lint temp_benefit = benefit(temp);
      lint max_benefit = benefit(max_pair);
      if(temp_benefit > max_benefit)
      {
        max_pair.first = temp.first;
        max_pair.second = temp.second;
      }
      temp.first = a[i];
      temp.second = 0;
    }
  }
  lint temp_benefit = benefit(temp);
  lint max_benefit = benefit(max_pair);
  if(temp_benefit > max_benefit)
  {
    max_pair.first = temp.first;
    max_pair.second = temp.second;
  }
  //cout  << "max pair = " << max_pair.first << " " << max_pair.second << endl;
  ///最大の利益を達成する互いに素なペアをカウントする
  vector<bool> counted(n, false);
  lint result = 0;
  for (int i = 0; i < n; ++i) {
    if(pos.count(a[i] + max_pair.second - max_pair.first) != 0)
    {
      if(pos[a[i] + max_pair.second - max_pair.first] > i &&
          !counted[pos[a[i] + max_pair.second - max_pair.first]])
      {
        result++;
        //cout << a[i] << " " << a[i] + max_pair.second - max_pair.first << endl;
        counted[i] = true;
        counted[pos[a[i] + max_pair.second - max_pair.first]] = true;
      }
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 7296
#include "bits/stdc++.h"
#include <unordered_map>
#include <unordered_set>
using namespace std;

const long long INF = 1e9 + 7;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> nums(n);

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

	vector<int> dp(n, INF);

	dp[0] = 0;
	dp[1] = abs(nums[1] - nums[0]);

	for (int i = 2; i < n; i++) {
		for (int j = k; j > 0; j--) {
			if (i - j >= 0) {
				dp[i] = min(dp[i], dp[i - j] + abs(nums[i] - nums[i - j]));
			}
		}
	}

	cout << dp[n - 1];
}


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

n = int(input())

ls = list(map(int, input().split()))

ans = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            a = ls[i]
            b = ls[j]
            c = ls[k]

            nums = [a,b,c]
            nums.sort()

            maxi = nums[2]
            mid = nums[1]
            mini = nums[0]

            if maxi < mid + mini and maxi != mid and mid != mini:
                ans += 1

print(ans)



Measured memory_bytes: 9196
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

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

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

  int x, y;
  cin >> x >> y;

  if(x % y == 0){
    cout << -1 << endl;
    return 0;
  }

  cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
/**
 *		author:  zvm
 *		created: 28.09.2020 17:53:16
**/

#include <bits/stdc++.h>

using namespace std ;

template <typename T>
class Segment_tree {
	public :
		Segment_tree( int _n ) {
			n = _n ;
			tree.resize(2*n,0) ;
		}

		T combine( T lchild, T rchild ) {
			return max(lchild, rchild);
		}

		void update( int idx, T val ) {
			for( tree[idx+=n] = val, idx /= 2 ; idx >= 1 ; idx /= 2 ) {
				tree[idx] = combine( tree[idx<<1], tree[idx<<1|1] );
			}
		}

		T query( int l, int r ) {
			T ans = 0 ;
			for( l += n, r += n ; l <= r ; l /= 2, r /= 2 ) {
				if( l&1 ) {
					ans = combine( ans, tree[l++] ) ;
				}
				if( !(r&1) ) {
					ans = combine( ans, tree[r--] ) ;
				}
			}
			return ans ;
		}

	private :
		int n ;
		vector<T> tree ;
};

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

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

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

	int sz = 1<<19 ;
	Segment_tree<int> dp(1<<19) ;

	// dp[i] stores max length of flat subseq ending with val i
	dp.update(a[0],1);
	
	for( int i = 1 ; i < n ; ++i ) {
		dp.update( a[i], 1+dp.query( max(a[i]-k,0), min(a[i]+k,300000) ) );
	}

	cout << dp.query(0,sz-1) << endl ;
}


Measured memory_bytes: 8484
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    cin>>n;
    double a;
    if (n==1)
        cout<<"1.0000000000";
    else if (n>=2 && n%2==0)
        cout<<"0.5000000000";
    else
    {

         x= (int)n/2+1;
        a=(double)x/n;
        cout<<a;

    }
//        cout<<"0.6000000000";


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<typename T>
class BIT {
    int n;
    vector<T> val;
public:
    BIT(int n):n(n),val(n+1,0) {}
    void add(int i,T x=1) {
        i++;
        while(i <= n) {
            val[i] += x;
            i += i&-i;
        }
    }
    T sum(int i) {
        T ret = 0;
        i++;
        while(i > 0) {
            ret += val[i];
            i -= i&-i;
        }
        return ret;
    }
    // [l,r)
    T sum(int l,int r) { return sum(r-1)-sum(l-1); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vi a(n);
    cin >> a;
    vl sum(n+1,0);
    rep(i,n) sum[i+1] = sum[i]+a[i];
    rep(i,n+1) sum[i] -= (ll)k*i;
    vl press = sum;
    sort(all(press));
    press.erase(unique(all(press)),press.end());
    map<ll,int> ma;
    rep(i,press.size()) ma[press[i]] = i;
    ll ans = 0;
    BIT<int> bt(press.size());
    bt.add(ma[0]);
    rep2(i,1,n+1) {
        ans += bt.sum(ma[sum[i]]);
        bt.add(ma[sum[i]]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 17408
N, K = map(int, input().split())
table = [[int(i) for i in input().split()] for _ in range(K * 2)]

ans_list = []
sunuke_set = set(list(range(1, N + 1)))

for i in range(1, K * 2 + 1, 2):
    ans_list += table[i]

ans_set = set(ans_list)

print(len(sunuke_set - ans_set))


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

int main(){
    int n, k;
    std::cin >> n >> k;

    int x;
    int ans = 0;
    for(int i = 0; i < n; ++i){
        std::cin >> x;
        if(k - x > x){
            ans += 2 * x;
        }else{
            ans += 2 * (k - x);
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mx 1000007
#define ll long long int
#define ff first
#define ss second
#define pii pair<ll,ll>
#define faster ios_base::sync_with_stdio(false);
#define m 998244353

bool vis[mx];

ll cnt[mx];
ll a[mx];

ll sum[mx];
ll multiply(ll a, ll b){
    ll res = 0; a %= m; b %= m;
    while(b){
        if(b & 0x1)
            res = (res + a)%m;
        b >>= 1;
        if(a < m-a) a<<=1;
        else a -= (m-a);
    }
    return res;
}
ll power(ll x,ll y,ll p)
{
    ll res=1;
    while(y>0) {
        if(y&1)
            res=(res*x)%p;
        y=y>>1;
        x=(x*x)%p;
    }
    return res;
}

int main()
{


    ll tt=1;
    //cin>>tt;
    ll c=0;
    while(tt--){
        ll n;
        cin>>n;


        for(ll i=1;i<=n;i++){
            cin>>a[i];
            cnt[a[i]]++;
        }
        ll inv=power(2,m-2,m);
        ll pre=0;
        for(ll g=1;g<=mx;g++){
            pre=0;
            for(ll i=g;i<=mx;i+=g){

                sum[g]+=(((((pre%m)*(cnt[i]%m))%m)*i)%m);
                sum[g]%=m;
                ll x=((((cnt[i]*(cnt[i]-1))%m)*((i*i)%m))%m);
                x%=m;
                sum[g]+=((x*inv)%m);
                sum[g]%=m;
                pre+=(cnt[i]*i)%m;
                pre%=m;

            }

        }
        ll ans=0;
        for(ll g=mx;g>=1;g--){
            for(ll i=g+g;i<=mx;i+=g){

                sum[g]-=sum[i];
                if(sum[g]<0) sum[g]=((sum[g]+m)%m);
                //sum[g]=(sum[g]+m+m)%m;
            }

            ll x=power(g,m-2,m);
            ans+=((sum[g]*x)%m);
            ans%=m;


        }
        cout<<ans%m<<endl;
    }
}


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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

const int len = 2e4+5, mx = 1e4;
ll dp[len];
pair<ii, int> arr[len];

bool comp(pair<ii, int> a, pair<ii, int> b){
    return (a.fi.fi+a.fi.se > b.fi.fi+b.fi.se);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d", &arr[i].fi.fi, &arr[i].fi.se, &arr[i].se);
    sort(arr+1, arr+1+n, comp);

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= mx; j++)
            if (j <= arr[i].fi.se)
                dp[j] = max(dp[j], dp[j+arr[i].fi.fi]+arr[i].se);

    printf("%lld\n", dp[0]);
    return 0;
}


Measured memory_bytes: 384
def Eratosthenes(n):

    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    for i in range(2,n):
        if dp[i]:
            continue
        prime.append(i)
        for j in range(i*2,n,i):
          dp[j] = True
    return prime

N = int(input())
E = Eratosthenes(55555)
A = []
for e in E:
  if e % 5 == 1:
    A.append(e)
  if len(A) == N:
    break
print(*A)

Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define ll long long
#define f(i,l,r) for(int i=l;i<r;i++)
#define debug(x) cout<<#x<<'='<<(x)<<endl
using namespace std;
int n,k,s[101];
int dp[100001][2];
int solve(int left,int turn)
{
    if(dp[left][turn]!=-1)  return dp[left][turn];
    if(left==0)
        return dp[left][turn]=turn^1;
    else
    {
        int temp;
        f(i,0,n){
            if(left>=s[i])
            {
                temp=solve(left-s[i],turn^1);
                if(temp==turn)
                    return dp[left][turn]=temp;
            }
        
        }
        
    }
    return dp[left][turn]=turn^1;
}
    


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    f(i,0,n)    cin>>s[i];
    f(i,0,100001)   f(j,0,2)    dp[i][j]=-1;   
    int winner=solve(k,0);
    if(winner)  cout<<"Second";
    else        cout<<"First";
    return 0;
}

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

using namespace std;
using ll = long long;

#define int ll

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "CONTINUE"
#define FALSE__ "GAMEOVER"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define YES(f) if((f)){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(f) if((f)){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))

#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
#define fcout cout << fixed << setprecision(12)

#define MOD 1000000007

template<class T>
inline T GET() {
	T x;
	cin >> x;
	return x;
}

void init();
void solve();

signed main()
{
	init();
	solve();
}

void init()
{
	int N, S;
	cin >> N >> S;
	vector<int> a;
	CINV(a, N);
	int l = 0, r = 1;
	ll sum = a[0];
	int mi = INT_MAX;
	while (true) {
		while (r < N && sum < S) {
			sum += a[r];
			r++;
		}
		if (sum < S) break;
		chmin(mi, r-l);
		sum -= a[l];
		l++;
	}
	cout << (mi == INT_MAX ? 0 : mi) << endl;
}


void solve()
{
}






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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int a,b; cin >> a >> b;
  int k = (a+b)/2;
  bool test = true;
  if(2*k!=a+b) test = false;

  if(!test) cout << "IMPOSSIBLE" << endl;
  else cout << k << endl;
  
  return 0;
}


Measured memory_bytes: 3616
// header {{{
#include <bits/stdc++.h>

#include <cmath>

using namespace std;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;
using f80 = __float80;
// }}}

constexpr i64 INF = 1'010'000'000'000'000'017LL;

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}

template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}
// }}}

// init {{{
struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
// }}}

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


signed main() {


	i64 ans = 0;
	i64 H, A;
	cin >> H >> A;
	ans = (H + (A - 1)) / A;
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256