akhauriyash/Code-Regression huggingface dataset:
// Problem : B - Product Max
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// $%U%$
// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y==0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll nCr(ll n,ll r,ll m){if(r>n)return 0;ll a=1,b=1,i;for(i=0;i<r;i++){a=(a*n)%m;--n;}while(r){b=(b*r)%m;--r;}return (a*power(b,m-2,m))%m;}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
void solve()
{
	ll a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << max({a*c,a*d,b*c,b*d}) << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(void)
{
	int x;
	cin>>x;
	int i;
	for(i=0;pow(2,i)<=x;i++);
	cout<<pow(2,i-1)<<endl;
	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  int num = 1;
  for (int i = 0; i < N; i++) {
    if (num < K)
      num *= 2;
    else num += K;
  }
  cout << num << endl;
}

Measured memory_bytes: 256
import Control.Monad
import Data.Array

checkMan :: [(Int, Int)] -> Array Int Int -> Bool
checkMan [] _ = True
checkMan (p:ps) ar = check p ar && checkMan ps ar
  where check (idx, c) ar  = ar ! idx == c

patterns :: Int -> [Array Int Int]
patterns n = do
  xs <- replicateM n [0, 1]
  return $ listArray (1, n) xs

solve :: Int -> Array Int [(Int, Int)] -> [Array Int Int] -> Int
solve n ts [] = 0
solve n ts (x:xs) = if and cs then max (sum x) (solve n ts xs) else solve n ts xs
  where cs = do
          i <- [1..n]
          return (if x ! i == 1 then checkMan (ts ! i) x else True)

getTm :: IO [(Int, Int)]
getTm = do 
  a <- readLn
  replicateM a $ do 
    [i, t] <- (map read) . words <$> getLine :: IO [Int]
    return (i, t)

main = do
  n <- readLn
  xs <- replicateM n getTm 
  print $ solve n (listArray (1, n) xs) (patterns n)


Measured memory_bytes: 4220
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 500;

int n, a[N][N], m, c, b[N];
int32_t main(){_

   cin>>n>>m>>c;

   for (int i = 0; i < m; ++i)
   {
      cin>>b[i];
   }

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


   int ans = 0;
   for (int i = 0; i < n; ++i)
   {
      int vals = 0;
      for (int j = 0; j < m; ++j)
      {
         vals += a[i][j]*b[j];
      }
      vals += c;
      if(vals > 0)ans++;
   }

   cout<<ans;

   #warning make sure N size is correct!
   return 0;
}

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

using namespace std;
typedef pair<int, int> P;   // x, y
typedef pair<P, int> PP;    // x, y, step
static const int INF = 1e9;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};

void solve()
{
	int W, H;
	cin >> W >> H;
	vector< vector<char> > field(H, vector<char>(W));
	vector< vector<int> > step(H, vector<int>(W));
	P goal;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			cin >> field[i][j];
			if (field[i][j] == 't')
			{
				goal.first = j;
				goal.second = i;
			}
			step[i][j] = INF;
		}
	}
	int N;
	cin >> N;
	vector<P> release(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> release[i].first >> release[i].second;
	}
	step[0][0] = 0;
	queue<PP> que;
	que.push(make_pair(make_pair(0, 0), 1));
	int time = 0;
	for (int i = -1; i < N; ++i)
	{
		if (i >= 0)
		{
			++time;
			field[release[i].second][release[i].first] = '.';
			int minStep = INF;
			for (int j = 0; j < 4; ++j)
			{
				int x = release[i].first + dx[j];
				int y = release[i].second + dy[j];
				if (0 <= x && x < W && 0 <= y && y < H && step[y][x] < minStep)
				{
					minStep = step[y][x];
					step[release[i].second][release[i].first] = minStep + 1;
				}
			}
			if (minStep != INF)
			{
				que.push(make_pair(make_pair(release[i].first, release[i].second), minStep + 1));
			}
		}
		while (!que.empty())
		{
			PP pp = que.front();
			que.pop();
			if (pp.first.first == goal.first && pp.first.second == goal.second)
			{
				cout << time << endl;
				return;
			}
			for (int j = 0; j < 4; ++j)
			{
				int nx = pp.first.first + dx[j];
				int ny = pp.first.second + dy[j];
				if (0 <= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] != '#' && step[ny][nx] == INF)
				{
					step[ny][nx] = pp.second;
					que.push(make_pair(make_pair(nx, ny), pp.second + 1));
				}
			}
		}
	}
	cout << -1 << endl;
}

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

Measured memory_bytes: 6020
// Created by ahmed_drawy on 11/09/19.
///dp educational contest atcoder
#include <bits/stdc++.h>
#include <string.h>
#pragma clang diagnostic push
#pragma ide diagnostic ignored "OCUnusedMacroInspection"
using namespace std;
#define lp(i,start , end)       for(int i = start ; i<end ; ++i)
#define lllp(i,start , end)       for(ll i = start ; i<end ; ++i)
#define inN(arr ,  n) for(int i = 0 ; i< n ; ++i)  cin>>arr[i];
#define Rlp(i,start , end)      for(int i = start ; i>end ; --i)
#define all(v)                   ((v).begin(),(v).end())
#define sz(v)                  (int)((v).size())
#define clr(v,d)                memset(v , d , sizeof(v))
#define inf 0x3f3f3f3f
//#define dbg (v)    for(auto it : v)cout<<it<<' ';
typedef long long               ll;
typedef vector<int>             vi;
typedef vector  <ll>            vll;
typedef vector<vector<int> >    adj;
typedef pair<int ,int>          pii;
const double EPS =1e-7;
const int OO = 1e6;
#define endl '\n'
#define cint(c) (int)c -'0';
#define itc(c) (char)c +'A';
bool sortpair( const pair<int , int> & x, const pair<int , int> & y){
    return  x.first != y.first ? x.first < y.first : x.second > y.second ;
}
int dcomp(double x , double y){
    return fabs(x-y) <= EPS? 0: x>y?1:-1;
}

void smile() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
 //  freopen("/home/tw3/Desktop/Desktop/training/in.txt", "r", stdin);
//    freopen("/home/tw3/Desktop/Desktop/training/out.txt" , "w" , stdout);
#endif
}
#define fastin smile()

int n , m;
const int N = 3000 +3;
ll dp[N][N];
string s, t;
ll lcs(int i , int j ){
    if(i == n || j ==m )
        return 0 ;
    ll &ret = dp[i][j];
    if(~ret)
        return ret;
    ret = 0;
    if(s[i] == t[j])
        ret =1 +  lcs(i+1 , j+1);
    else {
        ret = max(ret, lcs(i + 1, j));
        ret = max(ret, lcs(i, j + 1));
    }
    return ret;
}
void build(int i , int j){
    if(i == n || j ==m )
        return  ;
    if(s[i] == t[j]) {
        cout << s[i];
        build(i+1, j+1);
        return ;
    }
    if(dp[i+1][j] > dp[i][j+1] )
        build(i+1, j);
    else build(i, j+1);
    return ;

}
int main() {
    fastin;
    cin >> s >> t;
    n = sz(s), m = sz(t);
    for (int i = n-1; i >=0 ; --i) {
        for (int j = m-1; j>=0 ; --j) {
            ll &ret = dp[i][j];
            ret = 0;
            if(s[i] == t[j])
                ret =1 +  dp[i+1][j+1];
            else {
                ret = max(ret, dp[i + 1][j]);
                ret = max(ret, dp[i][j+1]);

            }
        }
    }
//    clr(dp , -1);
//    lcs(0,0);
    build(0,0);


}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MAX max<ll>
#define MIN min<ll>
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll devc(ll x, ll y) { return (x + y - 1) / y; }

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

    ll a,b;
    cin >> a >> b;
    print((a * b) % 2 == 0 ? "Even" : "Odd");

    return 0;
}

Measured memory_bytes: 256
/* ALDS1_1_A: Insertion Sort - http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A

Insertion Sort
Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

for i = 1 to A.length-1
    key = A[i]
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j = i - 1
    while j >= 0 and A[j] > key
        A[j+1] = A[j]
        j--
    A[j+1] = key
Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

Input
The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

Output
The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

Constraints
1 ≤ N ≤ 100

Sample Input 1
6
5 2 4 6 1 3
Sample Output 1
5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6
Sample Input 2
3
1 2 3
Sample Output 2
1 2 3
1 2 3
1 2 3

*/
 
fn solve(A: &Vec<i32>, N: &usize) -> Vec<Vec<i32>> {
    // Returns a vector of vectors representing the intermediate steps
    // of the insertion sort algorithm.

    let mut ret: Vec<Vec<i32>> = Vec::new();    // List of vectors to be returned.
    let mut A: Vec<i32> = A.clone();

    ret.push(A.clone());    // Initial state of A.

    for i in 1..*N {
        let key = A[i];
        let mut j = (i-1) as i32;
        while j >= 0 && A[j as usize] > key {
            A[(j+1) as usize] = A[j as usize];
            j -= 1;
        }
        A[(j+1) as usize] = key;
        ret.push(A.clone());
    }
    return ret;
}
 
fn main() {
    let N = read_line().trim().parse().unwrap();
    let mut A: Vec<i32> = read_line()
        .trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let ans: Vec<Vec<i32>> = solve(&A, &N);

    let mut output = String::new();
    for A in ans {
        output.push_str(&array_to_str(&A));
        output.push_str("\n");
    }
    println!("{}", output.trim());
}

// ------------------------------------------------------------------
// Auxiliary methods.
fn array_to_str(A: &Vec<i32>) -> String {
    // Converts a numerical array to a string for output purposes.
    let mut ans = String::new();
    for a in A {
        ans.push_str(&format!("{} ", *a));
    }
    return ans.trim().to_string();
}

fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_
}



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

using namespace std;
using LL = long long;
const LL mod=1e9+7;
const int Max_Num=2e5+10;

LL modpow(LL x, LL n){
	LL r=1;
	while(n){
		if(n&1) r=r*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return r;
}

LL modinv(LL x){
	LL m=mod, u=1, v=0;
	while(m){
		LL t=x/m;
		x-=t*m; swap(x,m);
		u-=t*v; swap(u,v);
	}
	u%=mod;
	if(u<0) u+=mod;
	return u;
}

int main(){
	LL n, a, b;
	cin >> n >> a >> b;
	vector<LL> comb;
	comb.emplace_back(1LL);
	rep(i,Max_Num){
		LL c=comb[i]*(n-i)%mod*modinv(i+1);
		c%=mod;
		comb.emplace_back(c);
	}
	LL ans=modpow(2,n)-1;
	ans-=comb[a]+comb[b];
	while(ans<0) ans+=mod;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define int long long int 

int32_t main()
{
     int n;
     cin>>n;
     int a[n];
     map<int,int> m;
     for(int i=0;i<n;i++)
     {
      cin>>a[i];m[a[i]]++;
      
     }
      sort(a,a+n);
   
     int ans=INT_MIN;
      for(int i=0;i<n;i++)
      {
          int ans1=upper_bound(a,a+n,a[i]-1)-lower_bound(a,a+n,a[i]-1);
          int ans2=upper_bound(a,a+n,a[i]+1)-lower_bound(a,a+n,a[i]+1);
           ans=max(ans,ans1+m[a[i]]+ans2);
      }
      cout<<ans<<endl;
      return 0;


    
}

Measured memory_bytes: 8336
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, k, l int
	fmt.Fscan(r, &n)
	fmt.Fscan(r, &k)
	fmt.Fscan(r, &l)

	ps := make([]int, k)
	qs := make([]int, k)
	for i := 0; i < k; i++ {
		fmt.Fscan(r, &ps[i])
		fmt.Fscan(r, &qs[i])
		ps[i]--
		qs[i]--
	}
	rs := make([]int, l)
	ss := make([]int, l)
	for i := 0; i < l; i++ {
		fmt.Fscan(r, &rs[i])
		fmt.Fscan(r, &ss[i])
		rs[i]--
		ss[i]--
	}

	// 道路での連結グループを作成
	roadConn := newUnionFind(n)
	for i := 0; i < k; i++ {
		roadConn.unite(ps[i], qs[i])
	}
	// 鉄道での連結グループを作成
	railConn := newUnionFind(n)
	for i := 0; i < l; i++ {
		railConn.unite(rs[i], ss[i])
	}

	// N個の都市で道路、鉄道両方でつながっている
	ans := make(map[int]map[int]int)
	for i := 0; i < n; i++ {
		x := roadConn.find(i)
		y := railConn.find(i)
		if ans[x] == nil {
			ans[x] = make(map[int]int)
		}
		ans[x][y]++
	}

	wtr := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		x := roadConn.find(i)
		y := railConn.find(i)
		fmt.Fprintf(wtr, "%d ", ans[x][y])
	}
	wtr.Flush()
}

// Union-Find
type unionFind struct {
	d []int
}

func newUnionFind(n int) *unionFind {
	uf := new(unionFind)
	uf.d = make([]int, n)
	for i := 0; i < n; i++ {
		uf.d[i] = -1
	}
	return uf
}

func (uf *unionFind) find(x int) int {
	if uf.d[x] < 0 {
		return x
	}
	uf.d[x] = uf.find(uf.d[x])
	return uf.d[x]
}

func (uf *unionFind) unite(x, y int) bool {
	rootX := uf.find(x)
	rootY := uf.find(y)
	if rootX == rootY {
		return false
	}

	if uf.d[rootX] < uf.d[rootY] {
		uf.d[rootX] += uf.d[rootY]
		uf.d[rootY] = rootX
	} else {
		uf.d[rootY] += uf.d[rootX]
		uf.d[rootX] = rootY
	}

	return true
}

func (uf *unionFind) same(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func (uf *unionFind) size(x int) int {
	return -uf.d[uf.find(x)]
}

// Utility

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

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


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

using namespace std;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int x;
	cin >> x;

	int ans = (x / 500) * 1000;
	x %= 500;

	ans += (x / 5) * 5;

	cout << ans;

	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int h,w,i,j,sq;
	
	while(1){
		scanf("%d %d",&h,&w);
		if(h == 0 && w == 0) break;
		
		for(i=0;i < h;i++){
			for(j=0;j < w;j++){
				if(i % 2 == 0 && j % 2 == 0 || i % 2 == 1 && j % 2 == 1){
					printf("#");
				}else{
					printf(".");
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 572
N = gets.to_i
A = gets.split.map(&:to_i).sort
B = gets.split.map(&:to_i).sort
C = gets.split.map(&:to_i).sort

bi_to_count = Hash.new { 0 }
prev_count = 0
B.reverse.each.with_index do |b, i|
  ci = C.bsearch_index { |c| c > b }
  count = ci.nil? ? 0 : N - ci
  bi_to_count[N - i - 1] = prev_count + count
  prev_count += count
end

ans = 0
A.each do |a|
  bi = B.bsearch_index { |b| b > a }
  next unless bi
  ans += bi_to_count[bi]
end
puts ans


Measured memory_bytes: 32104
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;
const int mod2 = 998244353;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

bool comp(const pair<ll, ll> &a, const pair<ll, ll> &b) {
  return a.second < b.second;
}

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

  int n;
  cin >> n;

  vector<pair<long long, long long>> AB(n);
  for (int i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    AB[i] = make_pair(a, b);
  }
  if (n & 1) {
    sort(AB.begin(), AB.end());
    long long low = AB[n / 2].first;

    sort(AB.begin(), AB.end(), comp);
    long long high = AB[n / 2].second;

    cout << high - low + 1 << "\n";
  } else {
    sort(AB.begin(), AB.end());
    long long low = AB[n / 2 - 1].first + AB[n / 2].first;

    sort(AB.begin(), AB.end(), comp);
    long long high = AB[n / 2 - 1].second + AB[n / 2].second;

    cout << high - low + 1 << "\n";
  }

  return 0;
}

Measured memory_bytes: 6320
//#define _GLIBCXX_DEBUG
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1000000000;

int main() {
    IOS;
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    // [a,b+1) と[c,d+1)の最大値
    
    ll ans = - 1e18;
    chmax(ans, a*c);
    chmax(ans, a*d);
    chmax(ans, b*c);
    chmax(ans, b*d);

    if ((a <= 0 and 0 <= b ) or (c<= 0 and 0 <= d))chmax(ans,(ll)0);

    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =999999999;

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}

//素数判定
ll isprime(ll n){
  bool prime=true;
  for(int i=2;i<n;i++){
    if(n%i==0){
      prime=false; break;
    }
  }
if(prime){cout<<n<<" is prime"<<endl;
         }else{cout<<n<<" is not prime"<<endl;}

}
//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




//10億7。　　　100000007
//2*2行列 H*W
//vector<vector<int>> vec(H,vector<int>(W));
//for(int i=0;i<H;i++){
//for(int j=0;j<W;j++){
//cin>>vec[i][j];
//  }
//}

//文字列→数列
//string S;int A=atoi(S.c_str());
//数列→文字列
//int A;string S=to_string(A);
//数字判定　isdigit(a)
//pair宣言　pair<int,int> p(5,7);
//ソート　sort(vec.begin(),vec.end());



int main(){
cout<<fixed<<setprecision(10);

  
  int N,K;cin>>N>>K;
  vector<int> vech(N);
  for(int i=0;i<N;i++){
    cin>>vech[i];
  }
vector<int> dp(100010);
  for(int i=0;i<100010;i++){
    dp[i]=INF;
  }
  dp[0]=0;
  
  for(int i=0;i<N;i++){
    for(int j=1;j<K+1;j++){
      if(i+j<N){
    dp[i+j]=min(dp[i+j],dp[i]+abs(vech[i]-vech[i+j]));}
  }}
  

  cout<<dp[N-1]<<endl;
                
                
  

}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll t1,t2,a1,a2,b1,b2;
	cin>>t1>>t2>>a1>>a2>>b1>>b2;
	ll f1=a1-b1;ll f2=a2-b2;
	if(f1>0&&f2>0||f1<0&&f2<0){
		cout << 0;
		return 0;
	}
	f1=abs(f1);f2=abs(f2);
	ll dx1=t1*f1;
	ll dx2=t2*f2;
	if(dx1-dx2>0){
		cout << 0;
		return 0;
	}
	if(dx1==dx2){
		cout <<"infinity";
		return 0;
	}
	dx2=abs(dx2-dx1);
	ll cnt=(dx1+dx2-1)/dx2;
	ll ans=cnt*2;
	if(dx1%dx2!=0){
		ans--;
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define dd(x) cout << #x << "=" << x << ","
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(b-1);i>=a;--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define lowbit(x) x&(-x)
const int N = 20000;
const int M = 1e9+7;

int num[100010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	ll n,a,b,c;
	cin>>n>>a>>b>>c;
	ll x=0,y=0,z=0;
	for (int i=1; i<=n; i++){
		string s;
		cin>>s;
		if (s=="AB") num[i]=1;
		if (s=="AC") num[i]=2;
		if (s=="BC") num[i]=3;	
	}
	num[n+1]=4;
	vector<char> ans;
	for (int i=1; i<=n; i++){
		// cout<<a<<b<<c<<endl;
		if (num[i]==1){
			if (num[i+1]==2 && a==1 && c==0){
				a++;b--;ans.pb('A');continue;
			} 
			if (num[i+1]==3 && b==1 && c==0){
				a--;b++;ans.pb('B');continue;
			} 
			if (a<b){
				a++;b--;ans.pb('A');
			}
			else{
				a--;b++;ans.pb('B');
			}
		}
		if (num[i]==2){
			if (num[i+1]==1 && a==1 && b==0){
				a++;c--;ans.pb('A');continue;
			} 
			if (num[i+1]==3 && c==1 && b==0){
				c++;a--;ans.pb('C');continue;
			} 
			if (a<c){
				a++;c--;ans.pb('A');
			}
			else{
				a--;c++;ans.pb('C');
			}
		}
		if (num[i]==3){
			if (num[i+1]==1 && b==1 && a==0){
				b++;c--;ans.pb('B');continue;
			} 
			if (num[i+1]==2 && c==1 && a==0){
				c++;b--;ans.pb('C');continue;
			} 
			if (b<c){
				c--;b++;ans.pb('B');
			}
			else{
				c++;b--;ans.pb('C');
			}
		}
		if (a<0 || b<0 || c<0){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	for (int i=0; i<sz(ans); i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 4184
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define REP(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define INF 10000000
#define ll long long

using namespace std;

typedef pair<int, int> P;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

string str;

int main(){
    cin >> str;

    if(str == "abc" || str == "acb" || str == "bac" || str == "bca" || str == "cab" || str == "cba"){
        printf("Yes\n");
    } else {
        printf("No\n");
    }

	return 0;
}

Measured memory_bytes: 256
#create date: 2020-07-03 14:46

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    h, w = na()
    g = [[1] * (w+2)]
    white = 0
    for i in range(h):
        r = ns()
        white += r.count(".")
        g.append([1] + [1 if s=="#" else 0 for s in r] + [1])
    g.append([1] * (w+2))
    q = deque([[1,1]])
    move = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while q:
        x, y = q.popleft()
        for dx, dy in move:
            nx, ny = x + dx, y + dy
            if g[nx][ny] > 0:
                continue
            g[nx][ny] = g[x][y] + 1
            q.append((nx, ny))
    if g[h][w] == 0:
        print(-1)
    else:
        print(white - g[h][w] - 1)



if __name__ == "__main__":
    main()

Measured memory_bytes: 9384
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
using ll = long long;
const int MOD = 1000000007;
bool custom(pair<int, int> a, pair<int, int> b) {
  return (a.second < b.second);
}
int main() {
  vector<int>v(4);
  rep(i, 4) cin >> v[i];
  sort(v.begin(), v.end());
  cout << abs(v[3] + v[0] - v[1] - v[2]) << endl;
  return 0;
}



Measured memory_bytes: 3172
#include <stdio.h>

struct dice {
	int N[6];
};
struct dice DICE;

int main(void) {
	char str[100];
	char dicenum[5] = { 4, 3, 0, 2, 1};
	int i;
	scanf("%d%d%d%d%d%d", &DICE.N[0], &DICE.N[1], &DICE.N[2], &DICE.N[3], &DICE.N[4], &DICE.N[5]);
	for (i = 0; i < 6; i++) {
		if (DICE.N[i] < 0) { DICE.N[i] = 0; }
		if (DICE.N[i] > 100) { DICE.N[i] = 100; }
	}
	getchar();
	i = 0;
	scanf("%s", str);
	while (str[i] != '\0'){
		switch (str[i]) {
		case 'N':
			dicenum[0] = dicenum[2];
			dicenum[2] = dicenum[4];
			dicenum[4] = 5 - dicenum[0];
			break;
		case 'S':
			dicenum[4] = dicenum[2];
			dicenum[2] = dicenum[0];
			dicenum[0] = 5 - dicenum[4];
			break;
		case 'E':
			dicenum[3] = dicenum[2];
			dicenum[2] = dicenum[1];
			dicenum[1] = 5 - dicenum[3];
			break;
		case 'W':
			dicenum[1] = dicenum[2];
			dicenum[2] = dicenum[3];
			dicenum[3] = 5 - dicenum[1];
			break;
		default:
			break;
		}
		i++;
	}
	printf("%d\n", DICE.N[dicenum[2]]);
	return 0;
}


Measured memory_bytes: 2104
def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a%b)
N=int(input())
L=list(map(int,input().split()))
s=L[0]
for i in range(N-1):
  s=gcd(L[i+1],s)
print(s)

Measured memory_bytes: 20072
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main(){
    vector<int> m(10);
    for(int a; cin>>a;){
        m.push_back(a);
    }
    sort(m.begin(), m.end(), greater<int>());
    for(int i=0; i<3; i++){
        cout << m[i] << "\n";
    }
    return 0;
}


Measured memory_bytes: 3132
#include<bits/stdc++.h>
#include <stdio.h>
#include <algorithm>

#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pr(x) printf("%d",x)
#define prl(x) printf("%lld",x)
#define LL long long
#define pb push_back
#define PB pop_back
#define PF pop_front
#define F first
#define S second
#define inrow(vec)    for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";
#define incoloum(vec) for(int i=0;i<vec.size();i++)cout<<vec[i]<<endl;

const double PI=3.1415926;
const int KL=1e6;

using namespace std;

LL q,x,y,z,n,m,p[KL],mn=1e9,mx=-1e9,ans;
string t;
vector <LL> vec;
set <int> s;
map <int,int> M;


int main()
{
    scl(n);scl(x);
    while(n!=0)
    {
        vec.pb(n%x);
        n/=x;
    }
    cout<<vec.size();
    return 0;
}


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

	return 0;
}

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

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

  int ans = 0;
  rep(i,N){
    int digits = log10(i) + 1;
    if((digits % 2) == 1) ans++;
  }
  
  cout << ans << endl; 
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main()
{

    int a,b,x,c,d,e;
    scanf("%d %d",&a,&b);
     c=a+b;
    if(a%3==0){
        printf("Possible");
    }else if(b%3==0){
        printf("Possible");
    }else if(c%3==0){
        printf("Possible");
    }else{
    printf("Impossible");
    }
    return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=7+1e9;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
ll qpow(ll a,ll b,ll p){a%=p; ll ret=1;for(;b;b>>=1,a=a*a%p) if(b&1) ret=ret*a%p; return ret;}
ll getInv(ll x,ll p){return qpow(x,p-2,p);}

int main(){
    string s; cin>>s;
    int n=s.size()-1;
    if(s[n]=='2'||s[n]=='4'||s[n]=='5'||s[n]=='7'||s[n]=='9') puts("hon");
    if(s[n]=='0'||s[n]=='1'||s[n]=='6'||s[n]=='8') puts("pon");
    if(s[n]=='3') puts("bon");

}

Measured memory_bytes: 3628
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

ll n, a, b;

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

    ll sum = a + b;
    cout << n / sum * a + min(n - sum * (n/sum), a) << '\n';

    return 0;
}


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

int main() {

  int N, M;
  cin >> N >> M;

  vector<pair<int,int>> sc(N);
  for (int i = 0; i < M; i++) {
    cin >> sc[i].first >> sc[i].second;
  }

  int start[3] = {0,10,100};
  int end[3] = {9,99,999};

  for (int i = start[N - 1]; i <= end[N - 1]; i++) {
    string str = to_string(i);
    bool flg = true;
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < M; k++) {
        if (j + 1 == sc[k].first) {
          if (sc[k].second != str[j] - '0'){
            flg = false;
          }
        }
      }
    }
    if (flg) {
      cout << i << endl;
      return 0;
    }
  }

  cout << -1 << endl;

  return 0;

}

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

int main(){

    char c[4]; cin>>c;

    sort(c,c+4);

    if(c[0] == c[1] && c[2] == c[3] && c[1] != c[2]) cout<<"Yes"<<endl;

    else cout<<"No"<<endl;

    return 0;
}

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

using namespace std;

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

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

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

	if (l[0] < sum) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N;
    static int[] A;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        solve();
    }

    public static void solve() {

        long count = 0;
        long sum = 0;
        int right = 0;
        for (int left = 0; left < N; left++) {

            while (right < N && (sum ^ A[right]) == sum + A[right]) {
                sum += A[right];
                right++;
            }

            count += right - left;

            if (left == right) {
                right++;
            } else {
                sum -= A[left];
            }
        }

        System.out.println(count);
    }

}


Measured memory_bytes: 83160
def splitter(s):
    cnt = 0
    prev = None
    ret = []
    for c in s:
        if prev is None:
            prev = c
            cnt = 1
            continue
        if c == prev:
            cnt += 1
        else:
            ret.append([cnt, prev])
            cnt = 1
            prev = c
    ret.append([cnt, prev])
    return ret

n = int(input())
s = input()
a = splitter(s)

left = 0
right = 0

if a[0][1] == ")":
    left += a[0][0]
    a.pop(0)

prev = 0
for i in a:
    if i[1] == ")":
        if prev > i[0]:
            prev -= i[0]
        else:
            left += i[0] - prev
            prev = 0
    else:
        prev += i[0]
right = prev

print("("*left + s + ")"*right)

Measured memory_bytes: 3064
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
	  
    int main(){
      ll n,m;
      cin>>n>>m;
      ll ans;
      if(n*2>m)ans = m/2;
      else {
        ans = n;
        m -= n*2;
        n = 0;
        ans += m/4;
      }
      cout<<ans;
    }

Measured memory_bytes: 256
a,b,c=map(str,input().split())
ans = max(int(a+b)+int(c),int(a)+int(b+c))
hoge = max(int(b+a)+int(c),int(a)+int(c+b))
fuga = max(int(b)+int(a+c),int(b)+int(c+a))

print(max(max(ans,hoge),fuga))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int>A;
void out(){
  for(int i=0;i<N;i++)cout<<A[i]<<(i!=N-1?" ":"\n");
}
void insertionSort(){
  for(int i=1;i<N;i++){
    int v=A[i];
    int j=i-1;
    while(j>=0&&A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    out();
  }
}
int main(void){
  cin>>N;
  A.resize(N);
  for(int i=0;i<N;i++)cin>>A[i];
  out();
  insertionSort();
  return 0;
}



Measured memory_bytes: 3100
N = int(input())
words = [0 for i in range(0,N)]
for i in range(0,N):
    words[i] = input()
M = int(input())

for i in range(0,M):
    t = input()
    words.append(t)
SUM = []
#print(words)
for i in range(0,N+M):
    count = 0
    for j in range(0,N):
        if words[i] == words[j]:
            count += 1

    for j in range(N,N+M):
        if words[i] == words[j]:
            count -= 1
    SUM.append(count)

#print(SUM)
ans = max(SUM)
if ans >= 0:
    print(ans)
else:
    print(0)


Measured memory_bytes: 3064
n = input()
 
d = [ [0] * 10 for _ in range(10) ]
for i in range( 1, int( n ) + 1 ):
  k = str(i)
  d[ int( k[ 0 ])][ int( k[ -1 ])] += 1

ans = 0
for i in range(10):
  for j in range(10):
    ans += d[i][j] * d[j][i]
print(ans)

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

using namespace std;
#define int1(a) scanf("%d",&a)
#define int2(a,b) scanf("%d %d",&a,&b)
#define int3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define int4(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define lint1(a) scanf("%lld",&a)
#define lint2(a,b) scanf("%lld %lld",&a,&b)
#define lint3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define lint4(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define lli long long int
#define pint(x) printf("%d",x)
#define ps printf(" "); 
#define plint(x) printf("%lld",x)
//#define sort(a,n) qsort(a,n,sizeof(int),cmpfunc)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define bg begin()
#define ed end()
#define Set(a, s) memset(a, s, sizeof (a))
#define mod 1000000007
#define tmod(k) if ((k) >= mod) k %= mod;
#define endl '\n'
#define nl printf("\n");
#define fors(i,n) for(int i=0; i<n; i++)
#define fore(i,n) for(int i=n-1; i>=0; i--)
#define forv(i,a,n) for(int i=a; i<n; i++)
#define fora(i,ele) for(auto i: ele)
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
typedef string st;
typedef vector<int> vi;
typedef vector<st> vs;
const int INF = 0x3f3f3f3f;
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

class node{
public:
	int id;
	int prio;
	int prd;
};

class compare{
public:
	bool operator()(node &n1, node &n2){
		if(n1.prio>n2.prio)//ascending
			return true;
		else if(n1.prio==n2.prio){
			return n1.id>n2.id;
		}
		return false;
	}
};
//priority_queue<node, vector<node>, compare> pq;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /*#ifdef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #else
    // online submission
    #endif*/
    
   int n; int1(n);
   int t=1,prev=1;
   while(1){
       
       prev=t;
       t*=2;
       if(t>n) break;
   }
   pint(prev);
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{int A,B,max;
  
scanf("%d", &A);
scanf("%d", &B);

max = A+B;

if(max<=A-B)
 max=A-B;

if(max<=A*B)
 max=A*B;

printf("%d", max);


return(0);

}

Measured memory_bytes: 128
#include <stdio.h>
int max(int a, int b){
	return a>b? a : b;
}
int main(void){
	int a, b;
	scanf("%i %i", &a, &b);
	int mop = max(a+b, a-b);
	mop = max(mop, a*b);
	printf("%i\n", mop);
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    map<int, int> m;
    auto prime_factrize = [&](int x) -> void {
        for (int i = 2; i*i <= x; i++) {
            if (x%i != 0) continue;
            int y = 0;
            while (x%i == 0) {
                y++;
                x /= i;
            }
            m[i] += y; 
        }
        if (x > 1) m[x]++;
    };

    for (int i = 1; i <= n; i++)
    {
        prime_factrize(i);
    }
    
    auto rec = [&](auto &&rec, auto a, int b) -> ll {
        if (a == m.end()) {
            if (b == 1) return 1;
            else return 0;
        }

        int res = 0;
        for (int i = 0; i <= a->second; i++){
            if (b%(i+1) != 0) continue;
            res += rec(rec, ++a, b/(i+1));
            a--;
        }
        return res;
    };

    cout << rec(rec, m.begin(), 75) << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import time

value_weight = {}
value_list = []
weight_list = []
input_data = input().split()
N, W = map(int, input_data)
for i in range(int(N)): 
    input_data = input().split()
    v, w = map(int, input_data)
    value_list.append(v)
    weight_list.append(w)

value_weight = [[0 for i in range(10010)] for j in range(110)]

for i in range(N):
    for w in range(W + 1):
        if w >= weight_list[i]:
            value_weight[i + 1][w] = max(value_weight[i][w - weight_list[i]] + value_list[i], value_weight[i][w])
        else:
            value_weight[i + 1][w] = value_weight[i][w]
print(value_weight[N][W])


Measured memory_bytes: 43160
#include<iostream>
#include<sstream>

using namespace std;

const int MAX = 1000001;

/*
  <DNA> := (<string>) || <char> || <number><DNA> || <number><DNA> <number><DNA>
  <string> := <string> <char> || <char>
  <char> := 'A'-'Z'
  <number> := 0-1000
 */

bool isNum(char c){return '0' <= c && c <= '9';}
bool isAlf(char c){return 'A' <= c && c <= 'Z';}

bool isChar(string s){
  if(s.length() != 1) return false;
  return isAlf(s[0]);
}

bool isString(string s){
  for(int i = 0; i < s.length(); i++)
    if(!isAlf(s[i])) return false;
  return true;
}

bool isNumberDNA(string s){
  int pos=0;
  for(int i = 0; i < s.length() && isNum(s[i]); i++) pos++;
  string tmp = s.substr(pos);

  if(tmp.length() == 1) return isAlf(tmp[0]);
  
  int p = 0;

  for(int i = 0; i < tmp.length()-1; i++){
    if(tmp[i] == '(') p++;
    if(tmp[i] == ')') p--;
    if(p == 0) return false;
  }
  return true;
}

string rmPara(string s){
  int st = 0, en = s.length()-1;
  if(s[st] != '(' || s[en] != ')') return s;
  int p = 0;
  for(int i = 0; i < en; i++){
    if(s[i] == '(') p++;
    if(s[i] == ')') p--;
    if(p == 0) return s;
  }
  return s.substr(1,s.length()-2);
}


string parse(string s){

  s = rmPara(s);

  if(isString(s) || isChar(s)) return s;

  // cout << "s " << s << endl;
   if(isNumberDNA(s)){
    int pos = 0;
    for(int i = 0; i < s.length() && isNum(s[i]); i++) pos++;
    string nums = s.substr(0,pos);
    string other = s.substr(pos);
  
    stringstream ss(nums);
    int num;
    ss >> num;
    string ret = "";
    string tmp = parse(other);
    for(int i = 0; i < num; i++){
      if(ret.length() > MAX) return ret.substr(0,MAX);
      ret += tmp;
    }
    return ret;    
  }else{
   
    int pos = 0;
    for(int i = 0; i < s.length() && isNum(s[i]); i++) pos++;

    int p = 0;

    for(int i = pos; i < s.length(); i++){
      if(s[i] == '(') p++;
      if(s[i] == ')') p--;
      pos++;
      if(!isNum(s[i]) && p == 0) break;
    }
    
    string A = s.substr(0,pos);
    string B = s.substr(pos);
    string C = parse(A)+parse(B);
    int len = min((int)C.length(),MAX);
    return C.substr(0,len);
  }
}


int main(){
  string s;
  int n;

  while(cin >> s >> n && s != "0"){
    string ans = parse(s);
    if(ans.length() > n) cout << ans[n] << endl;
    else cout << 0 << endl;
  }
}

Measured memory_bytes: 10756
#include <stdio.h>

int solve(int i, int m, int n, int A[])
{
	int res;

	if ( m == 0 )
		return 1;

	if ( i >= n )
		return 0;
	
	res = solve(i + 1, m, n, A) || solve(i + 1, m - A[i], n, A);
	return res;
}

int main () {
	int i, n, q, p;
	int A[40];

	scanf("%d", &n);
	for ( i = 0; i < n; i++ )
		scanf("%d", &A[i]);

	scanf("%d", &q);
	for ( i = 0; i < q; i++ )
	{
		scanf("%d", &p);
		if ( solve(0, p, n, A) )
			printf("yes\n");
		
		else
			printf("no\n");
	}

	return 0;
}


Measured memory_bytes: 1964
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long A, B, C, K;
  cin>>A>>B>>C>>K;
  if(K<=A){
    cout<<K<<endl;
    return 0;
  }else if(K<=A+B){
    cout<<A<<endl;
    return 0;
  }else{
    cout<< (A- (K-A-B) )<<endl;
    return 0;
  }
}

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

using namespace std;

typedef long long ll;

int main(){
    int N; 
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; ++i){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    ll sum = 0;
    if(N % 2 != 0){
        ll temp = 0;
        int limit = N / 2;
        for(int i = 0; i < N; ++i){
            if(i < limit){
                temp -= 2 * A[i];
            }
            else{
                temp += 2 * A[i];
            }
        }
        temp -= A[limit] + A[limit + 1];
        sum = max(sum, temp);
        
        temp = 0;
        for(int i = 0; i < N; ++i){
            if(i <= limit){
                temp -= 2 * A[i];
            }
            else{
                temp += 2 * A[i];
            }
        }
        temp += A[limit - 1] + A[limit];
        sum = max(sum, temp);
    }
    else{
        int limit = N / 2;
        for(int i = 0; i < N; ++i){
            if(i < limit){
                sum -= 2 * A[i];
            }
            else{
                sum += 2 * A[i];
            }
        }
        sum += A[limit - 1];
        sum -= A[limit];
    }
    cout << sum << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

/*素因数分解*/
template<class Type>
map<Type,int> prime_factor(Type n){
	map<Type,int> res;//自然数nの約数firstがsecond個ある.
	for(Type i=2;i*i<=n;++i){
		while(n%i==0){
			res[i]++;
			n/=i;
		}
	}
	if(n!=1) res[n]=1;
	return res;
}

int main(){
	llong n;
	cin>>n;
	
	map<llong,int> mp=prime_factor(n);
	
	int ans=0;
	for(auto elem:mp){
		int tmp=elem.second;
		for(int i=1;tmp>=i;++i){
			tmp-=i;
			ans++;
		}
	}
	
	cout<<ans<<endl;
}

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

int main() {
    int field[1001][101];
    while (true) {
        int n, m, a;
        cin >> n >> m >> a;
        if (n==0 && m==0 && a==0) {
            break;
        }
        memset(field,0,sizeof(field));
        int st=0;
        for (int i=0; i<m; i++) {
            int h, p, q;
            cin >> h >> p >> q;
            field[h][p]=q;
            field[h][q]=p;
            st=max(st,h);
        }
        for (int i=st; i>0; i--) {
            if (field[i][a]!=0) {
                a=field[i][a];
            }
        }
        printf("%d\n",a);
    }
    return 0;
}

Measured memory_bytes: 3496
package main
import (
    "fmt"
    "sort"
)

func main(){
  var N,M int
  sum := 0
  fmt.Scan(&N)
  fmt.Scan(&M)
  if N >= M {
    fmt.Println(sum)
    return
  }
  var temp int
  var X []int
  for i:=0;i<M;i++{
    fmt.Scan(&temp)
    X  = append(X,temp)
  }

  sort.Ints(X)
  var kyori []int
  for i:=1;i<M;i++{
    kyori = append(kyori,X[i]-X[i-1])
  }
  sort.Ints(kyori)
  for i:=0;i<(M-N);i++{
    sum += kyori[i]
  }
  fmt.Println(sum)
}


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

int main() {
    int N,M,C;
    cin >> N >> M >> C;

    int B[M+1];
    for(int i = 0; i < M; i++)
    {
        /* code */
        cin >> B[i];
    }

    int A[N+1][M+1];

    int ans = 0;
    int ansNum = 0;
    for(int i = 0; i < N; i++)
    {
        ans = 0;
        ans += C;
        /* code */
        for(int j = 0; j < M ; j++)
        {
            /* code */
            cin >> A[i][j];
            ans += A[i][j] * B[j];
            //cout <<"aa:" << A[i][j] << B[j] << endl;
        }
        //cout << "ans:" << ans << endl;
        if(ans > 0){
            ansNum += 1;
        }
    }
    
    cout << ansNum << endl;
    




}

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

#print(N)
#print(A)

#合計を求める
sum = 0
for i in range(N):
  sum += A[i]

#半分を超える要素pを求める
half1st = 0
half1st2 = 0
half2nd = 0
i = 0
temp = 0
flag = 0
for i in range(N):
  if( half1st <= (int)(sum/2) ):
    half1st += A[i]
    temp += 1
  else:
    half2nd += A[i]
thre = temp-1
half1st2 = half1st - A[thre]
half2nd1 = half2nd + A[thre]
#その要素pを減らす/増やす，あるいは要素p-1を減らす/増やす，どちらが早いか判定
P = abs(half1st2 - half1st)
Q = abs(half1st - half2nd)
R = abs(half1st2 - half2nd1)
#ちょうど半分
if (half1st2 == half2nd1):
  print(0)
#P > Q
elif ( P < Q and P < R):
  #print('ans = '+str(Q))
  print(P)
elif (Q < R):
  #print('ans = '+str(P))
  print(Q)
else:
  print(R)


#A[i-1] が要素p 
#要素のインクリ数，でクリ数を計算
#出力
#print(sum)
#print(A[thre])
#print('h1 = '+str(half1st))
#print('h2 = '+str(half2nd))

#print('h12 = '+str(half1st2))
#print('h21 = '+str(half2nd1))
#print(R)

Measured memory_bytes: 27468
N = input()
K = int(input())

dp = [[[0] * 2 for j in range(K+1)] for i in range(len(N)+1)]

dp[0][0][0] = 1

for i in range(len(N)):
  n = int(N[i])
  for j in range(K+1):
    for ltn in range(2):
      for x in range(10 if ltn else n+1):
        if j + (x > 0) > K : continue
        dp[i+1][j + (x > 0)][ltn | (x < n)] += dp[i][j][ltn]

print(sum(dp[len(N)][K]))

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

int main () {
  int N;
  cin >> N;
  double N2 = N;
  cout << fixed << setprecision(10);
  if (N%2 == 1) cout << (N/2+1)/N2 << endl;
  else cout << 0.5 << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();      
		int o=0;
      	int[] b=new int[n-1];
        //PriorityQueue<Integer> num=new PriorityQueue<>();
        for(int i=0;i<n-1;i++){
        	b[i]=sc.nextInt();
        }
        o+=b[0];
        for(int i=1;i<n-1;i++){
            int m=Math.min(b[i],b[i-1]);
        	o+=m;
     	}
        o+=b[n-2];
      	System.out.println(o);
    }  
 
}

Measured memory_bytes: 22868