akhauriyash/Code-Regression huggingface dataset:
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

for i in range(N):
  a, b = AB[i]
  if a >= H:
    for j in range(H + 1):
      if i == 0:
        DP[i][j] = b
      else:
        DP[i][j] = min(DP[i - 1][j], b)
    continue
  for j in range(1, a + 1):
    if i == 0:
      DP[i][j] = b
    else:
      DP[i][j] = min(DP[i - 1][j], b)
  for j in range(a + 1, H + 1):
    if i == 0:
      DP[i][j] = DP[i][j - a] + b
    else:
      DP[i][j] = min(DP[i - 1][j], DP[i][j - a] + b)

print(DP[-1][H])


Measured memory_bytes: 119772
# coding: utf-8
# Your code here!

N, T, E = map(int, input().split())
# N：砂時計の個数
# T：理想の茹で時間
# E：許容誤差

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

min = T - E
max = T + E 

c = [0] * 100
for i in range(len(time)):
   for j in range(min, max + 1):
      if j % time[i] == 0:
         c[i] += 1

if sum(c) == 0:
   print(-1)
else:
   for i in range(len(c)):
      if c[i] > 0:
         print(i + 1)
         break



Measured memory_bytes: 5604
ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,d = ma()
cnt=0
for i in range(n):
    p,q = ma()
    if p**2 + q**2 <=d**2:
        cnt+=1
print(cnt)


Measured memory_bytes: 9408
#[allow(unused_macros)]
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.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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
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, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input!{
        s:chars,
        k:usize,
    }
    let mut memo = (1, 0);
    for i in 0..s.len() {
        if s[i] != '1' {
            memo = (s[i] as i64 - 48, i);
            break;
        }
    }
    // println!("{:?}", memo);
    if k<=memo.1 {
        println!("{}", 1);
    }else{
        println!("{}", memo.0);
    }
}

Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n;
char v[1001][1001];
int dp[1001][1001];

int main(void){
	while(1){
		int ans=0;
		for(int i=0;i<1000;i++){
			for(int j=0;j<1000;j++){
				dp[j][i]=1;
			}
		}
		cin >> n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin >> v[i];
			for(int j=0;j<n;j++){
				if(v[i][j]=='*')dp[i][j]=0;
			}
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<n;j++){
				if(v[i][j]!='*')dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
				ans=max(ans,dp[i][j]);
			}
		}
		cout << ans << endl;
	}
    return 0;
}

Measured memory_bytes: 6052
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;

mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> b(m);
    for(auto &x : b){
        cin >> x;
    }
    int res = 0;
    vector<vector<int>> a(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
        int ans = 0;
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            ans += (a[i][j] * b[j]);
        }
        if(ans + c > 0){
            res++;
        }
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

  
int main(){
  int x, y, max, min, i;
  
  for(i = 0; i<5000 ; i++){
  
   scanf("%d %d" ,&x ,&y);

    if(x == 0 && y == 0)
     break;
  if(x > y){
   max = x;
   min = y;
 }
  else{
   min = x;
   max = y;
 }
  printf("%d %d\n",min ,max);
 }
 return 0;
}

Measured memory_bytes: 600
X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)

D=[]
for i in range(1,X+1):
    for j in range(1,Y+1):
        if i*j>3000:
            break
        for k in range(1,Z+1):
            if i*j*k<=K:
                D.append((i-1,j-1,k-1))
            else:
                break

E=[]
for i in D:
    E.append(A[i[0]]+B[i[1]]+C[i[2]])

E.sort(reverse=True)
E=E[:K]
for i in E:
    print(i)

Measured memory_bytes: 17952
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int main(){
	int N,W;
	ll w[105];
	ll v[105];
	scanf("%d%d",&N,&W);
	for(int i = 1;i <= N;i++) scanf("%lld%lld",&w[i],&v[i]);
	ll dp[105][maxn];
	memset(dp,0,sizeof(dp));
	//dp[0][0] = 0;
	for(int i = 1;i <= N;i++){
		for(int j = 0;j <= W;j++){
			if(j >= w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else dp[i][j] = max(dp[i][j],dp[i-1][j]);
		}
	}
	printf("%lld\n",dp[N][W]);
	return 0;
}

Measured memory_bytes: 82304
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;string s;cin>>n>>s;
  for(int i=0;i<s.size();i++){
    int a=s.at(i)-'A';
    a=(a+n)%26;
    s.at(i)='A'+a;
  }
  cout<<s<<endl;
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairInt;
typedef tuple<int, int, int> tuple3Int;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[])
{
  int N, S;
  vector<int> a;

  scanf("%d%d", &N, &S);
  a.resize(N);

  FOR(i, N) {
    scanf("%d", &a[i]);
  }

  int sum(0), l(0), r(0), ans(INT_MAX);
  while (r < N) {
    while (r < N && sum < S) sum += a[r++];
    if (sum < S) break;
    while (sum >= S) sum -= a[l++];
    if (r - l + 1 < ans) ans = r - l + 1;
  }

  if (ans == INT_MAX) printf("0\n");
  else printf("%d\n", ans);
  
  return 0;
}

Measured memory_bytes: 3424
n,k,s = map(int,input().split())
ans = []
for _ in range(k):
  ans.append(str(s))
for _ in range(n-k):
  if s != 10 ** 9:
    ans.append(str(s+1))
  else:
    ans.append(str(s-1))
print(' '.join(ans))

Measured memory_bytes: 13464
P = 10**9 + 7
N = 200000
inv_t = [0]+[1]  # 逆元
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]


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

A.sort()
mini_count = 0
maxim_count = 0
pattern = 1
"""
minX, maxXとして選ばれるのはそれぞれ
minX:sortAの右からk番目(大きい数値からk個取った時の最小値)とそれより左の要素
maxX:sortAの左からk番目(小さい数値からk個取った時の最大値)とそれより右の要素
選ばれるパターンはminXの場合自分の要素より右にある要素からk-1個を選ぶパターン数
つまり最初は(k-1)C(k-1) = 1
選べる要素が一つ増えるごとに
tC(k-1) ⇒ (t+1)C(k-1)のように増えるので
t * t-1 * t-2 ... * t-k ⇒ t+1 * t * t-1 ... * t-k+1 であり
つまりパターン数は (t+1) / (t-k) 倍になる
"""
for idx in range(k, n + 1):
    mini = A[-idx]  #
    mini_count += mini * pattern % mod
    mini_count %= mod

    maxim = A[idx - 1]
    maxim_count += maxim * pattern % mod
    maxim_count %= mod

    pattern = pattern * (idx) * inv_t[idx + 1 - k] % mod # 割り算のmodは逆元をかける

ans = maxim_count - mini_count
ans %= mod

print(ans)

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

using namespace std;
#define MAX 100000

int main(){
    char s[MAX];
    cin >> s;

    int size = 0;
    while(s[size] != '\0')
        size++;

    char ans1[size+1], ans2[size+1];
    for(int i = 0; i < size; i++){
        if(i % 2){
            ans1[i] = '0';
            ans2[i] = '1';
        }else{
            ans1[i] = '1';
            ans2[i] = '0';
        }
    }

    int c1 = 0;
    int c2 = 0;
    for(int i = 0; i < size; i++){
        if(s[i] != ans1[i])
            c1++;
        if(s[i] != ans2[i])
            c2++;
    }

    cout << min(c1, c2) << endl;

    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void) {
	char n[8];
	int i;
	if (scanf("%7s", n) != 1) return 1;
	for (i = 0; n[i] != '\0'; i++) {
		int c = (unsigned char)n[i];
		putchar(c == '1' ? '9' : (c == '9' ? '1' : c));
	}
	putchar('\n');
	return 0;
}


Measured memory_bytes: 128
# N個のスペース区切りの数値を取得
N = int(input())
A = [int(N) for N in input().split()]


# 奇数番目と偶数番目に出てくる数字の頻度順にそれぞれソートして、
odd = []
even = []

for i in range(N):
    if i%2 == 0:
        odd.append(A[i])
    else:
        even.append(A[i])

import collections
c_odd = collections.Counter(odd)
c_even = collections.Counter(even)
#print(c_odd.most_common()[0][0], c_even.most_common()[0][0])



# 最頻な数字が一致してない場合はそれぞれの最頻値以外の合計値、
if c_odd.most_common()[0][0] != c_even.most_common()[0][0] :
    #print(len(set(odd))-1 + len(set(even))-1)
    print(N - c_odd.most_common()[0][1] - c_even.most_common()[0][1])
    exit()


# 一致してる場合は片方が最頻を諦めた場合の合計値を両パターン求めて小さい方
if c_odd.most_common()[0][0] == c_even.most_common()[0][0] :

    # 偶数と奇数の数列が完全一致のパターンでないかチェック
    if len(c_odd.most_common()) == 1 and len(c_even.most_common()) == 1:
        print(N//2)

    # oddが1種類しかない場合
    elif len(c_odd.most_common()) == 1:
        print(N//2 - c_even.most_common()[1][1])
    # evenが1種類しかない場合
    elif len(c_even.most_common()) == 1:
        print(N//2 - c_odd.most_common()[1][1])
    #両方が2種類以上で構成されている場合
    else:
        ans = N - max(c_odd.most_common()[0][1]+c_even.most_common()[1][1], c_odd.most_common()[1][1]+c_even.most_common()[0][1] )
        print(ans)

'''
        # 最頻を諦める ＝ 2番めに頻出な数値を採用
        temp_odd_retire = N//2 - c_odd.most_common()[1][1] #個数
        temp_even_retire = N//2 - c_even.most_common()[1][1] #個数
        #print('temps are ', temp_odd_retire, temp_even_retire)

        # oddを諦めたほうが良い場合
        if temp_odd_retire < temp_even_retire:
            print(temp_odd_retire + N//2 - c_even.most_common()[0][1])
        # even()
        else:
            print(temp_even_retire + N//2 - c_odd.most_common()[0][1])
        exit()
'''


Measured memory_bytes: 20516
use std::cmp::max;
use std::collections::BTreeMap;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let s = sc.chars();
    let k: usize = sc.read();
    let ans = dfs(0, s.len(), k, &mut BTreeMap::new(), &s);
    println!("{}", ans);
}

fn dfs(
    left: usize,
    right: usize,
    remain: usize,
    dp: &mut BTreeMap<(usize, usize, usize), usize>,
    s: &Vec<char>,
) -> usize {
    assert!(left <= right);
    let segment_size = right - left;
    if segment_size <= 1 {
        return segment_size;
    }
    if let Some(&v) = dp.get(&(left, right, remain)) {
        return v;
    }

    let mut max_length = 0;
    if s[left] == s[right - 1] {
        max_length = max(max_length, dfs(left + 1, right - 1, remain, dp, s) + 2);
    } else if remain > 0 {
        max_length = max(max_length, dfs(left + 1, right - 1, remain - 1, dp, s) + 2);
    }
    max_length = max(max_length, dfs(left + 1, right, remain, dp, s));
    max_length = max(max_length, dfs(left, right - 1, remain, dp, s));
    dp.insert((left, right, remain), max_length);
    max_length
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 188796
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <vector>
#include <string>
#include <iomanip>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define sz(x) ((int)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define RSORT(x) sort((x).begin(), (x).end(), greater<int>() )
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int n;
int out = 0,point = 0;
bool base[3];
string str;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	while(true){
		cin >> str;
		if(str[0] == 'O'){
			out++;
			if(out%3 == 0){
				cout << point << endl;
				point = 0;
				rep(i,3) base[i] = 0;
			}
			if(out == n*3) break;
		} else if(str[1] == 'O'){
			point++;
			rep(i,3) if(base[i]) point++;
			rep(i,3) base[i] = 0;
		} else{
			if(base[2]) point++;
			if(base[1]) base[2] = 1;
			if(base[0]) base[1] = 1;
			base[0] = 1;
		}
	}
}

Measured memory_bytes: 1208
unittest
{
	assert( [ "20 4", "3 7 8 4" ].parse.expand.solve == "777773" );
	assert( [ "101 9", "9 8 7 6 5 4 3 2 1" ].parse.expand.solve == "71111111111111111111111111111111111111111111111111" );
	assert( [ "15 3", "5 4 6" ].parse.expand.solve == "654" );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nm = input.front.split.to!( long[] );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( nm[ 0 ], as );
}

auto solve( long n, long[] as )
{
	const cs = [ 2L, 5L, 5L, 4L, 5L, 6L, 3L, 7L, 6L ];
	
	auto dp_v = new string[][]( n + 1, as.length );
	auto dp_d = new bool[][]( n + 1, as.length );
	foreach( ref d; dp_d[ 0 ] )
	{
		d = true;
	}
	
	for( auto ni = 1L; ni < dp_v.length; ni++ )
	{
		for( auto mi = 0L; mi < dp_v[ ni ].length; mi++ )
		{
			auto v = "";
			auto d = false;
			auto c = cs[ as[ mi ] - 1 ];
			if( 0 <= ni - c )
			{
				for( auto pi = 0L; pi < dp_v[ ni ].length; pi++ )
				{
					if( !dp_d[ ni - c ][ pi ] ) continue;
					
					auto w = dp_v[ ni - c ][ pi ] ~ as[ mi ].to!string;
					if(      v.length <  w.length ) v = w;
					else if( v.length == w.length ) v = max( v, w );
					d = true;
				}
			}
			dp_v[ ni ][ mi ] = v;
			dp_d[ ni ][ mi ] = d;
		}
	}
	
	auto ans = "";
	foreach( v, d; lockstep( dp_v[ $ - 1 ], dp_d[ $ - 1 ] ) )
	{
		if( !d ) continue;
		
		if(      ans.length <  v.length ) ans = v;
		else if( ans.length == v.length ) ans = max( ans, v );
	}
	
	return ans;
}


Measured memory_bytes: 738812
class BellmanFord:
    def __init__(self, graph, num_v, start_point):
        self.num_v = num_v
        self.graph = graph
        self.start_point = start_point


    def execute(self):
        dist = [float("inf") for _ in range(self.num_v)]
        dist[self.start_point] = 0
        negative = [False for _ in range(self.num_v)]
        for i in range(self.num_v - 1):
            for src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
        for i in range(self.num_v):
            for src in range(self.num_v):
                for dest, cost in self.graph[src].items():
                    if dist[dest] > dist[src] + cost:
                        dist[dest] = dist[src] + cost
                        negative[dest] = True
                    if negative[src]:
                        negative[dest] = True
        return dist, negative


n, m = map(int, input().split())
graph = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = -c
bellman = BellmanFord(graph, n, 0)
result, negative = bellman.execute()

if negative[-1]:
    print("inf")
else:
    print(-result[-1])


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

void solve() {
    int n;
  	cin>>n;
  	cout<<n + (n*n) + (n*n*n);
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    long long t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3608
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, m) revi(i, m, 0)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define allr(n) (n.rbegin(), n.rend())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数
// __builtin_popcount bitの個数

int main() {
  int H, W;
  ci(H, W);
  ve<ve<char>> C(H, ve<char>(W));
  rep(i, H){
    rep(j, W){
      ci(C.at(i).at(j));
    }
  }
  rep(i, H){
    rep(j, 2){
      rep(k, W){
        cout << C.at(i).at(k);
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(n):
    minj = i
    for j in range(i, n):
        if A[j] < A[minj]:
            minj = j
    if minj > i:
        A[i], A[minj] = A[minj], A[i]
        count += 1
print(*A)
print(count)



Measured memory_bytes: 5612
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
c = 0
for i in range(N):
  A = list(map(int, input().split()))
  prod = C
  for j in range(M):
    prod += A[j]*B[j]
  if prod>0:
    c += 1
print(c)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int r,d;
int y[11];
cin >> r >> d >> y[0];
REP(i,10) {
  y[i+1] = r*y[i] - d;
  cout << y[i+1] << endl;
}
return 0;
}


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

int main(){
  int N,K,ant;
  cin >> N >> K;
  while(N--){
    int x;
    cin >> x;
    if(x < (K-x)){
      ant += 2*x;
    }
    else ant += 2*(K-x);
      }
  cout << ant;
}  

Measured memory_bytes: 256
def move_up(count)
  count.times { print 'U' }
end

def move_down(count)
  count.times { print 'D' }
end

def move_right(count)
  count.times { print 'R' }
end

def move_left(count)
  count.times { print 'L' }
end

input = gets.chomp.split.map {|i| i.to_i}
dx = input[2] - input[0]
dy = input[3] - input[1]

# x, y ともに同軸上にない
if input[0] != input[2] && input[1] != input[3]
  # 目標が右にある
  if dx > 0
    # 目標が上にある
    if dy > 0
      move_up(dy)
      move_right(dx)
      move_down(dy)
      move_left(dx)

      move_down(1)
      move_right(dx+1)
      move_up(dy+1)
      move_left(1)

      move_up(1)
      move_left(dx+1)
      move_down(dy+1)
      move_right(1)
    # 下にある
    else
      move_down(dy)
      move_right(dx)
      move_up(dy)
      move_left(dx)

      move_up(1)
      move_right(dx+1)
      move_down(dy+1)
      move_left(1)
      
      move_down(1)
      move_left(dx+1)
      move_up(dy+1)
      move_right(1)
    end

  # 目標が左にある
  else
    # 目標が上にある
    if dy > 0
      move_up(dy)
      move_left(dx)
      move_down(dy)
      move_right(dx)

      move_down(1)
      move_left(dx+1)
      move_up(dy+1)
      move_right(1)

      move_up(1)
      move_right(dx+1)
      move_down(dy+1)
      move_left(1)
    # 下にある
    else
      move_down(dy)
      move_left(dx)
      move_up(dy)
      move_right(dx)

      move_up(1)
      move_left(dx+1)
      move_down(dy+1)
      move_right(1)
      
      move_down(1)
      move_right(dx+1)
      move_up(dy+1)
      move_left(1)
    end
  end

# x が同軸
elsif input[0] != input[2]
  if dx > 0
    move_right(dx)
    move_up(1)
    move_left(dx)
    move_down(1)

    move_down(1)
    move_right(dx)
    move_up(1)
    move_right(1)
    move_down(2)
    move_left(dx+2)
    move_up(2)
    move_right(1)
  else
    move_left(dx)
    move_up(1)
    move_right(dx)
    move_down(1)

    move_down(1)
    move_left(dx)
    move_up(1)
    move_left(1)
    move_down(2)
    move_right(dx+2)
    move_up(2)
    move_left(1)
  end

else
  if dy > 0
    move_up(dx)
    move_right(1)
    move_down(dx)
    move_left(1)

    move_left(1)
    move_up(dx)
    move_right(1)
    move_up(1)
    move_left(2)
    move_down(dx+2)
    move_right(2)
    move_up(1)
  else
    move_down(dx)
    move_right(1)
    move_up(dx)
    move_left(1)

    move_left(1)
    move_down(dx)
    move_right(1)
    move_down(1)
    move_left(2)
    move_up(dx+2)
    move_right(2)
    move_down(1)
  end
end

Measured memory_bytes: 1788
x,k,d = map(int,input().split())
if x >= 0:
    if x >= k*d:
        print(x-k*d)
    else:
        a = x%d
        b = a-d
        c = x//d
        if (k-c)%2 ==0:
            print(a)
        else:
            print(-1*b)
else:
    if -1*x >=k*d:
        print(-1*x-k*d)
    else:
        a = -1*x%d
        b = a-d
        c = -1*x//d
        if (k-c)%2 ==0:
            print(a)
        else:
            print(-1*b)

Measured memory_bytes: 9204
#include<stdio.h>

int main() {
	int a, b, c, k;
	int total;
	scanf("%d %d %d %d", &a, &b, &c, &k);
	if (k <= a) {
		total = k;
	}
	if (k > a && k <= a + b) {
		total = a;
	}
	if (k > a + b) {
		total = a - (k-a-b);
	}

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

	return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

struct edge
{
    int from, to, cost;
};

edge es[2000];

int main()
{

    int v, e, r;
    cin >> v >> e >> r;

    rep(i, e) cin >> es[i].from >> es[i].to >> es[i].cost;

    int d[v];
    rep(i, v) d[i] = INF;
    d[r] = 0;
    int cnt = 0;

    while (1)
    {
        bool update = 0;
        rep(i, e)
        {
            if (d[es[i].from] != INF && d[es[i].from] + es[i].cost < d[es[i].to])
            {
                d[es[i].to] = d[es[i].from] + es[i].cost;
                update = 1;
            }
        }
        if (!update)
            break;
        cnt++;
        if (cnt == v - 1)
        {
            OP("NEGATIVE CYCLE");
            return 0;
        }
    }
    rep(i, v) d[i] == 1e9 ? OP("INF") : OP(d[i]);

    return 0;
}


Measured memory_bytes: 3124
#include<stdio.h>

int main(void){
	int i,n,b,f,r,v;
	int build[4][3][10]={0};

	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d %d",&b,&f,&r,&v);
		build[b-1][f-1][r-1]+=v;
	}
	for(b=0;b<4;b++){
		for(f=0;f<3;f++){
			for(r=0;r<10;r++){
				printf(" %d",build[b][f][r]);
			}
		printf("\n");
		}
	if(b!=3)
		printf("####################\n");
	}

	return 0;
}

Measured memory_bytes: 612
/*====Corycle====*/
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=105;
int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*f;
}
int n,Ans,a[N];
int Solve(int x){
	int ans=0;
	for(int i=1;i<=n;i++)ans+=(a[i]-x)*(a[i]-x);
	return ans;
}
int main(){
//	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	n=read();Ans=inf;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=-100;i<=100;i++)Ans=min(Ans,Solve(i));
	printf("%d\n",Ans);
	return 0;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
#define ll  long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define e endl
#define bc __builtin_popcount
#define MAXN 2000005
#define debug cout<<"we are debuuging"<<endl;
#define MOD 998244353
ll fast_expo(ll x,ll p)
{if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
int mark[MAXN];
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
         cin>>a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
         if(i>0&&a[i]==a[i-1])
         {mark[a[i]]=1;mark[a[i-1]]=1;}
         if(!mark[a[i]])
         {
              for(int j=2*a[i];j<=1e6;j+=a[i])
              {
                   mark[j]=1;
              }
         }
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
         if(!mark[a[i]])
          ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8216
h, w = map(int, input().split())
s = ["." * (w+2)] + ["." + input() + "." for _ in range(h)] + ["." * (w+2)]
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      if s[i-1][j]=="." and s[i+1][j]=="." and s[i][j-1]=="." and s[i][j+1]==".":
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <string.h>
using namespace std;

#define HUNDRED 100
#define THOUSAND 10000
#define TENTHOUSAND 10000
#define HUNDREDTHOUSAND 100000

int kaibun(int number);

int main() {
	int n;
	vector<int> a;
	int temp;

	cin >> n;

	for(int i=0; i < n ;i++){
		cin >> temp;
		a.push_back(temp);
	}


	cout << *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end());


}

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

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

using namespace std;
int main() {

	int a, b;
	cin >> a >> b;

	int ans = 0;
	for (int i = a; i <= b; i++)
		if (i / 10000 == i % 10 && i / 1000 % 10 == i % 100 / 10)
			ans++;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#define llong long long
#define pb(a) push_back(a)
#define strVecSORT(strVec) sort(strVec.begin(), strVec.end());
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;

int main(){
  string S;
  cin>>S;
  int ii;
  vector<char> strVec;
  for(ii=0;ii<S.size();ii++){
  int i,count,n;
  count=0;
  int size =S.size()-ii-1;
    for(n=0;n<size;n++){
      char a=S[n];
      strVec.push_back(a);
    }
  if(size%2==0){
    for(i=0;i<(size/2);i++){
      if(strVec[i]==strVec[(size/2)+i]){
        count++;
      }
        if(count==size/2){
          cout<<size<<endl;
          exit(0);
        }
    }
  }
}
}

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

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int M = scan.nextInt();
        // 0 min_distance
        // 1 min_from
        int[][] ans = new int[N][2];
        for (int i = 0; i < N; i++) {
            Arrays.fill(ans[i], Integer.MAX_VALUE);
        }
        ans[0][0] = 0;
        ans[0][1] = -1;
        List<Integer>[] edges = new List[N];
        for (int i = 0; i < N; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int from = scan.nextInt()-1;
            int to = scan.nextInt()-1;
            edges[from].add(to);
            edges[to].add(from);
        }
        Deque<Edge> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        for (int to : edges[0]) {
            queue.add(new Edge(0, to));
            visited.add(0);
        }
        while(!queue.isEmpty()) {
            Edge target = queue.poll();
            int target_to = target.to;
            int target_from = target.from;
            visited.add(target_to);
            if (ans[target_to][0] != Integer.MAX_VALUE && ans[target_to][0] <= ans[target_from][0] + 1) {
                continue;
            }
            ans[target_to][0] = ans[target_from][0] + 1;
            ans[target_to][1] = target_from;
            for (int to : edges[target_to]) {
                if (visited.contains(to)) {
                    continue;
                }
                queue.add(new Edge(target_to, to));
            }
        }
        System.out.println("Yes");
        for (int i = 1; i < N; i++) {
            System.out.println(ans[i][1]+1);
        }
    }
    private long key(int from, int to) {
        int min = Math.min(from, to);
        int max = Math.min(from, to);
        return min * 1000000 + max;
    }
    class Edge {
        int from;
        int to;
        Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}


Measured memory_bytes: 85088
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#define NUM 100

using namespace std;

vector<int> int2vec(long long num, int n){
    vector<int> v;
    for(int i = 0; i < n; i++){
        v.push_back(num % 2);
        num = num / 2;
    }
    /*
    for(int i = 0; i < v.size(); i++){
        printf("%d", v[i]);
    }
    printf("\n");
    */
    return v;
}

int main(void){
    int n, m;
    scanf("%d %d", &n, &m);

    vector<vector<int>> K(m);
    for(int i = 0; i < m; i++){
        int k;
        scanf("%d", &k);
        for(int j = 0; j < k; j++){
            int s;
            scanf("%d", &s);
            K[i].push_back(s - 1);
        }
    }

    vector<int> P;
    for(int i = 0; i < m; i++){
        int p;
        scanf("%d", &p);
        P.push_back(p);
    }

    long long pow_2_n = 1;
    for(int i = 0; i < n; i++){
        pow_2_n *= 2;
    }

    long long cnt = 0;
    for(long long i = 0; i < pow_2_n; i++){
        vector<int> v = int2vec(i, n);
        bool all_light = true;
        for(int j = 0; j < m; j++){
            int sum = 0;
            for(int l = 0; l < K[j].size(); l++){
                sum += v[K[j][l]];
            }
            if(sum % 2 != P[j]){
                all_light = false;
            }
        }
        if(all_light){
            cnt++;
        }
    }

    printf("%lld\n", cnt);
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

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

  rep(man, N + 1)
  {
    rep(gosen, N + 1)
    {
      int sen = N - man - gosen;
      int sum = man * 10000 + gosen * 5000 + sen * 1000;
      if (sen >=0 && N >= sen && sum == Y)
      {
        printf("%d %d %d", man, gosen, sen);
        return 0;
      }
    }
  }
  cout << "-1 -1 -1";
}


Measured memory_bytes: 3704
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
const ll MOD = 1e9+7;
void Main(){
    string s;
    cin >> s;
    int n=s.size();
    int qnum=count(ALL(s),'?');
    vector<ll> pw(n+1);
    pw[0]=1;
    For(i,0,n) pw[i+1]=(pw[i]*3%MOD);
    ll A=0,q=0,AB=0,Aq=0,qB=0,qq=0;
    For(i,0,n){
        if(s[i]=='A') A++;
        else if(s[i]=='B') {
            AB += A;
            qB += q;
        }
        else if(s[i]=='C') {
            ans += AB * pw[qnum] % MOD;
            ans += Aq * pw[qnum-1] % MOD;
            ans %= MOD;
            ans += qB * pw[qnum-1] % MOD;
            ans += qq * pw[qnum-2] % MOD;
        }
        else{
            ans += AB * pw[qnum-1] % MOD;
            ans += Aq * pw[qnum-2] % MOD;
            ans %= MOD;
            ans += qB * pw[qnum-2] % MOD;
            ans += qq * pw[qnum-3] % MOD;
            Aq += A;
            qq += q;
            q ++;
        }
        AB %= MOD;
        Aq %= MOD;
        qB %= MOD;
        qq %= MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;
int main(){
  int H,N;
  cin>>H>>N;
  int sou = 0;
  for(int i = 0;i<N;i++){
    int temp;
    cin>>temp;
    sou += temp;
  }
  if(H>sou){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    int n,i,j;
    int a[3][510],s[3][510];
    while(cin>>n)
    {
        for(i=1;i<=2;i++)
        {
            for(j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        memset(s,0,sizeof(s));
        for(i=1;i<=2;i++)
        {
            for(j=1;j<=n;j++)
            {
                s[i][j]=max(s[i-1][j],s[i][j-1])+a[i][j];
            }
        }
        cout<<s[2][n]<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import bisect
n = int(input()) 
A = sorted([int(i) for i in input().split()] )
B = sorted([int(i) for i in input().split()] )
C = sorted([int(i) for i in input().split()] )

b_count = []
pre_b = 0
for b in B:
    current_count = bisect.bisect_left(A,b)
    b_count.append(pre_b + current_count)
    pre_b += current_count

result = 0
for c in C:
    index = bisect.bisect_left(B,c)
    if index == 0:
        continue
    result += b_count[index-1]
    
print(result)

Measured memory_bytes: 23220
package main

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

func main() {
	nextReader = NewScanner()
	line1 := nextInt()
	count := line1[1] / line1[0]

	if line1[2] > count {
		fmt.Println(count)
	} else {
		fmt.Println(line1[2])
	}
}

// ------ Mathライブラリ ---------------------------------//
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}

func maxIdx(a ...int) int {
	r := a[0]
	index := 0
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
			index = i
		}
	}
	return index
}

func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}

func minIdx(a ...int) int {
	r := a[0]
	index := 0
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
			index = i
		}
	}
	return index
}

func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

// ------ Mathライブラリ ---------------------------------//

// ----- 標準入力用の関数 ----------------------------------//
var nextReader func() []string

func NewScanner() func() []string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	return func() []string {
		r.Scan()
		return strings.Fields(r.Text())
	}
}

func nextString() []string {
	return nextReader()
}

func nextInt() []int {
	var intArray []int
	strArray := nextReader()
	for _, v := range strArray {
		i, _ := strconv.Atoi(v)
		intArray = append(intArray, i)
	}
	return intArray
}

func nextFloat64() []float64 {
	var floatArray []float64
	strArray := nextReader()
	for _, v := range strArray {
		f, _ := strconv.ParseFloat(v, 64)
		floatArray = append(floatArray, f)
	}
	return floatArray
}

// ------ 標準入力用の関数 ---------------------------------//

// ------ あまり使わない -----------------------------------//
func nextInt64() []int64 {
	var int64Array []int64
	strArray := nextReader()
	for _, v := range strArray {
		i, _ := strconv.ParseInt(v, 10, 64)
		int64Array = append(int64Array, i)
	}
	return int64Array
}

// ------ あまり使わない -----------------------------------//


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N;
 cin >> N;
 string str1;
 cin >> str1;
  
  int res = N;
  for(int i=1;i<N;i++){
    if(str1.at(i)==str1.at(i-1)){
      res = res-1;
    }
    
  }
  
  cout << res;
}

Measured memory_bytes: 512
N, M = map(int, input().split())
List = [list(map(int, input().split())) for i in range(M)]

LList = []
RList = []

for i in range(M):
    L = List[i][0]
    R = List[i][1]
    
    LList.append(L)
    RList.append(R)
    

print(max((min(RList)-max(LList))+1,0))

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

////////////
// ModInt //
////////////

// 四則演算の最も左に存在する値がModIntでなければキャストでバグる
// 例えばx = mint * 1000;やx = ModInt(1000) * mint;はいいがx = 1000 * mint;は駄目。
template<int64_t mod_ = 1'000'000'007>
class ModInt {
private:
	int64_t integer_;

public:
	constexpr ModInt(const int64_t initial_number = 0)
		: integer_(initial_number){}
	
	// 四則演算
	constexpr ModInt operator+(const ModInt& operand) const
	{
		ModInt ret{this->integer_ + operand.integer_};
		if (ret.integer_ >= mod_)
			ret.integer_ -= mod_;
		return ret;
	}
	constexpr ModInt operator-(const ModInt& operand) const
	{
		ModInt ret{this->integer_ - operand.integer_};
		if (ret.integer_ < 0)
			ret.integer_ += mod_;
		return ret;
	}
	constexpr ModInt operator*(const ModInt& operand) const
	{
		return {this->integer_ * operand.integer_ % mod_};
	}
	constexpr ModInt operator/(const ModInt& operand) const
	{
		return *this * (operand ^ (mod_ - 2));
	}

	// 累乗
	constexpr ModInt operator^(const int64_t operand) const
	{
		ModInt ret{1}, pow_ope{this->integer_};
		for (int64_t pow{operand}; pow > 0; pow >>= 1)
		{
			if (pow & 1) ret *= pow_ope;
			pow_ope *= pow_ope;
		}
		return ret;
	}

	// 代入
	constexpr ModInt& operator=(const ModInt& operand)
	{
		this->integer_ = operand.integer_;
		return *this;
	}
	constexpr ModInt& operator+=(const ModInt& operand)
	{
		*this = *this + operand;
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt& operand)
	{
		*this = *this - operand;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt& operand)
	{
		*this = *this * operand;
		return *this;
	}
	constexpr ModInt& operator/=(const ModInt& operand)
	{
		*this = *this / operand;
		return *this;
	}

	// その他
	constexpr operator int64_t() { return integer_; }

	constexpr ModInt getOne() const
	{
		return ModInt(1ll);
	}
	constexpr ModInt getZero() const
	{
		return ModInt(0ll);
	}
};
using Mint = ModInt<>;

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	using v1i = std::vector<Mint>;
	using v2i = std::vector<v1i>;
	using v3i = std::vector<v2i>;
	v3i dp(n + 1, v2i(n + 1, v1i(k + 1)));
	dp[0][0][0] = Mint(1ll);
	for (int i{}; i < n; i++)
		for (int unused{}; unused <= i; unused++)
		{
			// 対応
			for (int odd_i{}; odd_i + 2 * unused <= k; odd_i++)
				dp[i + 1][unused][odd_i + 2 * unused] += dp[i][unused][odd_i];
			if (unused >= 1)
			{
				// 使う使う
				for (int odd_i{}; odd_i + 2 * (unused - 1) <= k; odd_i++)
					dp[i + 1][unused - 1][odd_i + 2 * (unused - 1)] += Mint(unused) * Mint(unused) * dp[i][unused][odd_i];
				// 使う保留
				for (int odd_i{}; odd_i + 2 * unused <= k; odd_i++)
					dp[i + 1][unused][odd_i + 2 * unused] += Mint(2ll) * Mint(unused) * dp[i][unused][odd_i];
			}
			// 保留保留
			for (int odd_i{}; odd_i + 2 * (unused + 1) <= k; odd_i++)
				dp[i + 1][unused + 1][odd_i + 2 * (unused + 1)] += dp[i][unused][odd_i];
		}
	std::cout << dp[n][0][k] << std::endl;

	return 0;
}

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

typedef long long ll;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    #ifdef acm
    freopen("a.in","r",stdin);
    #endif // acm

    int n;

    cin >> n;

    long long sol = 0;
    for( int i = 1; i <= n; i++ ){
        if( !(i % 3 == 0 || i % 5 == 0) )
            sol += i;
    }

    cout << sol << "\n";

    return 0;
}


Measured memory_bytes: 3640
#include<stdio.h>
int main()
{
    int a,b,c,x,y,temp;
    scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
    int ans=1e9;
    if(x>y)
    {
        temp=x;
        x=y;
        y=temp;
        temp=a;
        a=b;
        b=temp;
    }
    if(x*a+y*b<ans)ans=x*a+y*b;
    if(x*2*c+(y-x)*b<ans)ans=x*2*c+(y-x)*b;
    if(2*y*c<ans)ans=2*y*c;
    printf("%d\n",ans);
    return 0;

}

Measured memory_bytes: 256
n=int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
ans=0
for i in make_divisors(n):
  if i-1>0:
    if n//(i-1)==n%(i-1):
      ans+=i-1

print(ans)

Measured memory_bytes: 38896
#include "bits/stdc++.h"
using namespace std;
int books[105];
int m,n;
bool check(int mid){
    int now = 0; int d = 0; int l = 0;
    while(now < n && d < m){
        if(l + books[now] <= mid){
            l += books[now++];
        }
        else{
            d++; l = 0;
        }
    }
    if(d > m-1)return false;
    else return true;
}
int main(){
    while(scanf("%d%d",&m,&n),(m|n)){
        int sum = 0;
        int ma = -1;
        for(int i = 0; i < n; i++){
            scanf("%d",&books[i]);
            sum += books[i];
            ma = max(ma,books[i]);
        }

        int l = ma,r = sum;
        int mid=0;
        for(int i = 0;i < 100; i++){
            mid = (l+r)/2;
            if( check(mid) ){
                r = mid;
            }
            else l = mid;
        }
        printf("%d\n",r);
    }
    return 0;
}

Measured memory_bytes: 3152
n = int(input())
evidence = [[] for i in range(n)]
for i in range(n):
    A = int(input())
    for j in range(A):
        x, y = map(int,input().split())
        evidence[i].append((x-1, y))

result = 0
for i in range(1, 2 ** n):
    consistent = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidence[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count("1"))
print(result)



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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, M; scanf("%d %d", &N, &M);
  vector<int> freqs(N + 5, 0);
  int a, b;
  for (int i = 0; i < M; ++i) {
    scanf("%d %d", &a, &b);
    if (a == 1) { ++freqs[b]; }
    if (b == N) { ++freqs[a]; }
  }

  string ans = "IMPOSSIBLE";
  for (int i = 1; i <= N; ++i) {
    if (freqs[i] >= 2) {
      ans = "POSSIBLE";
      break;
    }
  }
  printf("%s\n", ans.c_str());
  return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);

    int n, m, c;
    cin >> n >> m >> c;
    vi vb(m);
    REP(i, m)
        cin >> vb[i];
    vi va(m);
    int ans = 0;
    REP(i, n)
    {
        int cnt = c;
        REP(j, m)
            cin >> va[j];
        REP(j, m)
            cnt += va[j] * vb[j];
        if (cnt > 0)
            ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <numeric>
#include <algorithm>
using namespace std;

char left_s[15]={'q', 'a', 'z', 'w', 's', 'x', 'e', 'd', 'c', 'r', 'f', 'v', 't', 'g', 'b'};
char right_s[11]={'y', 'h', 'n', 'u', 'j', 'm', 'i', 'k', 'o', 'l', 'p'};
int main() {
    string str;
    while(cin >> str, str!="#"){
        int n=str.size();
        int state=0, cnt=0;
        for(int i=0; i<n; ++i){
            for(int j=0; j<15; ++j){
                if(left_s[j]==str[i]){
                    if(state!=-1) cnt++;
                    state = -1;
                }
            }
            for(int j=0; j<11; ++j){
                if(right_s[j]==str[i]){
                    if(state!=1) cnt++;
                    state=1;
                }
            }
        }
        cout << cnt-1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
a, b, c = map(int, input().split())
print(a*b//2)


Measured memory_bytes: 3060
import java.util.*;


public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        int[] A = new int[N+1];		//?????????index?????? 1~N+1?????????
        for(int i=0; i<N; i++)		
            A[1+i] = sc.nextInt();	
 
 	for(int i=1; i<N+1; i++){	
	    int parent = i/2;
	    int left = 2*i;
	    int right = 2*i +1;

	    String id,k,pk,lk,rk;
	    id = "node "+i+": ";
	    k  = "key = "+ A[i] + ", ";
	    pk = ( (i!=1)? "parent key = " + A[parent] + ", " : "" );
	    lk = ( (left<=N)?  "left key = "+A[left] + ", " : "");
            rk = ( (right<=N)? "right key = "+A[right] + ", " : "");
            
            System.out.print(id + k + pk + lk + rk + "\n");
	}
    }
}

Measured memory_bytes: 27668