akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

class UnionFind {
    int[] roots;
	
	public UnionFind(int N) {
		this.roots = new int[N];
		for(int i = 0; i < N; ++i) this.roots[i] = i;
	}
	
	int getRoot(int x) {
		if(this.roots[x] == x) return x;
		else return this.roots[x] = getRoot(this.roots[x]);
	}
	
	boolean isSameSet(int x, int y) {
		return getRoot(x) == getRoot(y);
	}
	
	void unite(int x, int y) {
	    int rx = getRoot(x);
	    int ry = getRoot(y);
	    if(rx == ry) return;
	    roots[rx] = ry;
	}
}

public class Main {
    static Scanner sc = new Scanner(System.in);
    
    public static void main (String[] args) {
        int N = sc.nextInt();
        UnionFind uf = new UnionFind(N);
        int M = sc.nextInt();
        
        int[] p = new int[N];
        for(int i = 0; i < N; ++i) p[i] = sc.nextInt() - 1;
        
        for(int i = 0; i < M; ++i) {
            uf.unite(sc.nextInt() - 1, sc.nextInt() - 1);
        }
        
        int ans = 0;
        for(int i = 0; i < N; ++i) {
            if(uf.isSameSet(i, p[i])) ++ans;
        }
        System.out.println(ans);
        
    }
}

Measured memory_bytes: 90096
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    d, n = i_map()

    if d == 0:
        if n == 100:
            print(101)
        else:
            print(n)
        exit()

    if n == 100:
        if d == 1:
            print(10100)
        elif d == 2:
            print(1010000)
        exit()

    print(pow(100, d) * n)

if __name__ == '__main__':
    main()


Measured memory_bytes: 76768
#include<stdio.h>
#include<math.h>
int a[105];
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        int sum;
        scanf("%d",&sum);
        a[i]=a[i-1]+sum;
    }
    int temp=a[n];
    for(i=1;i<=n;i++)
    {
        int t=fabs(a[n]-a[i]-a[i]);
        if(t<temp)
            temp=t;
    }
    printf("%d\n",temp);
    return 0;
}


Measured memory_bytes: 128
// Try AtCoder
// author: Leonardone @ NEETSDKASU

fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(
        &mut std::io::stdin(), &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let n = get!();
    if n >= 3200 {
        let s = get!(String);
        println!("{}", s);
    } else {
        println!("red");
    }
}

Measured memory_bytes: 4352
R, G, B, N = map(int, input().split())
color = [R, G, B]
color.sort(reverse = True)
maxr = N // color[0]
count = 0
for i in range(maxr+1):
    nokori = N - i * color[0]
    maxg = nokori // color[1]
    for j in range(maxg+1):
        nokorinow = nokori - j * color[1]
        amari = nokorinow % color[2]
        if amari == 0:
            count += 1

print(count)


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

int main() {
	int N,maxi=-101,mini=101,sum,mincos=1000000000;
	cin>>N;
	int a[N];
	for(int i=0;i<N;i++) {
		cin>>a[i];
		maxi=max(maxi,a[i]);
		mini=min(mini,a[i]);
	}
	if(mini==maxi){
		mincos=0;
	}else{
		for(int i=mini;i<=maxi;i++){
			sum=0;
			for(int j=0;j<N;j++){
				sum+=(a[j]-i)*(a[j]-i);
			}
			mincos=min(mincos,sum);
		}
	}
	cout<<mincos<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9+7;
const int maxn = 100005;
double dp[3005][3005];
void go() {
	dp[0][0] = 1;
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; i++) {
		double x;
		cin >> x;
		for (int j = 0 ; j <= i ; j++) {
			dp[i + 1][j] += dp[i][j] * (1.0 - x);
			dp[i + 1][j + 1] += dp[i][j] * x;
		}
	}
	double ans = 0;
	for (int i = n / 2 + 1 ; i <= n ; i++) {
		ans += dp[n][i];
	}
	cout << fixed << setprecision(10) << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
    
}

Measured memory_bytes: 49872
def main():
    n = input()
    Adj = [[0]*n for m in xrange(n)]
    for i in xrange(n):
        a = map(int,raw_input().split())
        for j in xrange(a[1]):
            Adj[i][a[2:][j]-1] = 1

    for i in xrange(n):
        for j in xrange(n):
            if j == n-1:
                print Adj[i][j]
            else:
                print Adj[i][j],

if __name__ == '__main__':
    main()

Measured memory_bytes: 6468
# coding: utf-8
# Your code here!
def san(x):
    y=q/2
    while True:
        y=y-(y**3-x)/(3*y**2)
        if abs(y**3-x)<0.00001*x:
            break
    print(f'{y:.6f}')
    
while True:
    q=int(input())
    if q==-1:
        break
    san(q)


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

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

  vector<int> C(26);  // 0 to 25
  rep(i, 26) {
    cin >> C.at(i);
  }

  vector<vector<int>> S(D, vector<int>(26));  // 0 to 364, 0 to 25
  rep(i, D) {
    rep(j, 26) {
      cin >> S.at(i).at(j);
    }
  }

  // int ans = 0;
  vector<int> T(D);      // 0 to 364
  vector<int> L(26, 0);  // 0 to 25
  rep(i, D) {
    // int diff = 0;
    // rep(j, 26) {
    //   diff -= C.at(j) * (i + 1 - L.at(j));
    // }
    int maxplus = -1;
    int t = -1;
    rep(j, 26) {
      int plus = C.at(j) * (i + 1 - L.at(j)) + S.at(i).at(j);
      if (plus > maxplus) {
        t = j;
        maxplus = plus;
      }
    }
    L.at(t) = i + 1;
    T.at(i) = t + 1;
    // todo
  }

  rep(i, D) {
    cout << T.at(i) << endl;
  }
}


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

import numpy as np

MOD = 10**9+7
N = int(input())
M = 10**6
A = np.array(input().split(), dtype=np.int64)
Nsq = 10**3
fact = np.arange(M, dtype=np.int64).reshape(Nsq,Nsq)
fact[0,0] = 1
for n in range(1,Nsq):
    fact[:,n] *= fact[:,n-1]; fact[:,n] %= MOD
for n in range(1,Nsq):
    fact[n] *= fact[n-1,-1]; fact[n] %= MOD
fact = fact.ravel()
j = np.arange(N)
inv = np.array([pow(i+1, MOD-2, MOD) for i in range(N)])
inv = np.cumsum(inv)%MOD
temp = inv[j] + inv[N-1-j] - 1
ans = (A*temp%MOD).sum()
ans %= MOD
ans *= fact[N]
ans %= MOD
print(ans)

Measured memory_bytes: 26168
#include <stdio.h>


int main(void){
  int k, x, i;
  
  scanf("%d %d", &k, &x);
  
  if(k == 1){
    printf("%d\n", x);
  }else{
   	for(i = 0; i < k * 2  - 1; i++){
     printf("%d ", x - k + 1 + i);
    }
  }
  

 return 0; 
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int bitcnt(int x){
	int cnt = 0;
	for(int mask = 1; mask <= (1 << 16); mask <<= 1) if((x & mask) != 0) cnt++;
	return cnt;
}
int dp[31][1 << 16];
int main(void){
	while(1){
		int n, c;
		cin >> n >> c;
		if(n == 0) break;
		int p, a[n];
		fill(a ,a + n, 0);
		for(int i = 0; i < n; i++){
			for(int j = 15; j >= 0; j--){
				cin >> p;
				a[i] += p * (1 << j);
			}
		}
		int b[c];
		fill(b, b + c, 0);
		for(int i = 0; i < c; i++){
			for(int j = 15; j >= 0; j--){
				cin >> p;
				b[i] += p * (1 << j);
			}
		}
/*		for(int i = 0; i < n; i++) cout << a[i] << endl;
		for(int i = 0; i < c; i++) cout << b[i] << endl;*/
		fill((int*) dp, (int*) dp + (n + 1) * (1 << 16), -1);
		dp[0][0] = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < (1 << 16); j++){
				if(dp[i][j] != -1){
					for(int k = 0; k < c; k++){
						int to, add, t;
						t = (j | a[i]) & b[k];
						to = (j | a[i]) ^ t;
						add = bitcnt(t);
						dp[i + 1][to] = max(dp[i + 1][to], dp[i][j] + add);
					}
				}
			}
		}
		int mx = -1;
		for(int i = 0; i < (1 << 16); i++) mx = max(mx, dp[n][i]);
		cout << mx << endl;
	}
	return 0;
}


Measured memory_bytes: 11012
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define VV(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a); i>n; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
int main() {
	cout << setprecision(13) << fixed;
	double r; cin >> r;
	cout << r * r * M_PI << " " << r * 2 * M_PI << endl;
	return 0;
}

Measured memory_bytes: 3284
N = int(input())

def sumsum(n):
  flag = True
  res = 0
  while flag:
    res += n % 10
    n = n //10
    if n == 0:
      flag = False
  return res

nn = sumsum(N)
if N % nn == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9048
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let K: usize = sc.get();
    let mut ans = String::new();
    for _ in 0..K {
        ans.push_str("ACL");
    }
    println!("{}", ans);
}


Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
int t=0, i=0, ans=0, j=0, k=0, m=0, n=0, x=0, y=0, tn=0, ans1=0, min1=0, max1=0, flag=0;
map<int,int> m1, m2;
int a[200001];
int main()
{
	cin>>n;
	max1=0;
	for(i=0;i<n;i++)
    {
        cin>>tn;
        a[i]=tn;
        if(m1[tn]==2)
        {
        	m2[tn]=2;
        	//cout<<j<<"m2 set as 2 repeat"<<"\n";
        }
        m1[tn]=2;
        if(tn>max1)
        {
        	max1=tn;
        }
    }
    for(i=0;i<n;i++)
    {
    	tn=a[i];
    	for(j=2*tn;j<=max1;j=j+tn)
    	{
    		m2[j]=2;
    		//cout<<j<<" m2 set as 2 "<<m2[j]<<"\n";
    	}
    }
    for(i=0;i<n;i++)
    {
    	tn=a[i];
    	//cout<<tn<<" "<<m2[tn]<<"\n";
    	if(m2[tn]!=2)
    	{
    		//cout<<tn<<" "<<m2[tn]<<"*\n";
    		ans++;
    	}
    }
    cout<<ans;
}


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

int main(){
  long long  n, a, b, c, d, e;
  cin >> n >> a >> b >> c >> d >> e;
  long long pos = 0;
  long long time = 0;
  time = (n + (a-1)) / a;
  pos++;
  if(a <= b){
    time++;
    b = a;
  }
  else time = (n + (b-1)) / b + pos;
  pos++;
  if(b <= c){
    time++;
    c = b;
  }
  else time = (n + (c-1)) / c + pos;
  pos++;
  if(c <= d){
    time++;
    d = c;
  }
  else time = (n + (d-1)) / d + pos;
  pos++;
  if(d <= e){
    time++;
    e = d;
  }
  else time = (n + (e-1)) / e + pos;
  pos++;
  cout << time << endl;
  return 0;
}
    
  

Measured memory_bytes: 3620
def main():
    a,b,c,k = map(int,input().split())
    cnt = 0
    res = 0
    if a <= (k-cnt):
        res += a
        cnt += a
    else:
        res += (k-cnt)
        cnt += (k-cnt)
    if b <= (k-cnt):
        cnt += b
    else:
        cnt += (k-cnt)
    if c <= (k-cnt):
        cnt += c
        res -= c
    else:
        res -= (k-cnt)
        cnt += (k-cnt)
    print(res)

if __name__ == '__main__':
    main()



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

#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

  int N;
  cin>>N;
  vector<int>x(N),y(N);
  for(int i=0;i<N;i++)cin>>x[i]>>y[i];
  
  vector<pii>p(N);
  for(int i=0;i<N;i++)p[i]={x[i],y[i]};
  sort(rng(p));
  //a->上,b->下
  int Maxa=-LONG_MAX,Maxb=-LONG_MAX;
  int a,b;
  int ans=0;
  for(int i=0;i<N;i++){
    if(i==0){
      a=p[i].second;
      b=p[i].second;
      Maxa=-(p[i].first-p[i].second);
      Maxb=-(p[i].first+p[i].second);
    }
    else{
      if(a>p[i].second)ans=max(ans,p[i].first-p[i].second+Maxa);
      if(b<p[i].second)ans=max(ans,p[i].first+p[i].second+Maxb);

      if(Maxa<-(p[i].first-p[i].second)){
        Maxa=-(p[i].first-p[i].second);
        a=p[i].second;
      }
      if(Maxb<-(p[i].first+p[i].second)){
        Maxb=-(p[i].first+p[i].second);
        b=p[i].second;
      }
    }
  }

  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 9508
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
namespace mydef {
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
bool dbg = false;
}  // namespace mydef
using namespace mydef;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
#define pi pair<int, int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define asn ans

vector<pair<int, int>> prime_factorize(int n) {
    vector<pair<int, int>> ret;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int num = 0;
            while (n % i == 0) {
                num++;
                n /= i;
            }
            ret.push_back({i, num});
        }
    }
    if (n != 1)
        ret.push_back({n, 1});
    return ret;
}


int N;
int cnt[1010101];

void solve() {
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        auto V = prime_factorize(A);
        for (auto& p : V) {
            cnt[p.first]++;
        }
    }
    int flag1 = 1, flag2 = 1;
    for (int i = 0; i < 1010000; i++) {
        if (cnt[i] >= 2) {
            flag1 = 0;
        }
        if (cnt[i] == N) {
            flag2 = 0;
        }
    }
    if (flag1) {
        cout << "pairwise coprime" << endl;
    } else if (flag2) {
        cout << "setwise coprime" << endl;
    } else
        cout << "not coprime" << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N;

    solve();
    return 0;
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//template end

vector<int> z_algo(vector<int> a){
   int n=a.size(); vector<int> res(n);
   for(int i=1,j=0;i<n;i++){
      if(i+res[i-j]<j+res[j])res[i]=res[i-j];
      else{
         int k=max(0,j+res[j]-i);
         while(i+k<n&&a[k]==a[i+k])k++;
         res[i]=k; j=i;
      }
   } res[0]=n; return res;
}

int main(){
   int n; scanf("%d",&n);
   vector<int> a(n),b(n);
   rep(i,0,n)scanf("%d",&a[i]);
   rep(i,0,n)scanf("%d",&b[i]);
   vector<int> c(3*n);
   rep(i,0,n){
      int idx=(i+1)%n;
      c[i]=b[i]^b[idx];
      c[i+n]=c[i+2*n]=a[i]^a[idx];
   }
   vector<int> res=z_algo(c);
   rep(i,0,n)if(res[i+n]>=n)printf("%d %d\n",i,(b[0]^a[i]));
   return 0;
}

Measured memory_bytes: 9688
import numpy as np
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
total_v=sum(v)
INF=sum(w)+1
dp=[INF for i in range(total_v+1)]
dp[0]=0
dp=np.array(dp)
for i in range(N):
    dp[v[i]:]=np.minimum(dp[v[i]:],dp[:-v[i]]+w[i])
for i in reversed(range(1,total_v+1)):
    if dp[i]<=W:
        print(i)
        break



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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

int a, bcd[3];

int main()
{
  string s;
  cin >> s;
  a = s[0]-'0', bcd[0] = s[1]-'0', bcd[1] = s[2]-'0', bcd[2] = s[3]-'0';
  for (int i = 0; i < (1 << 3); i++) {
    int v = a;
    for (int b = 0; b < 3; b++) {
      if (i & (1 << b)) v += bcd[b];
      else v -= bcd[b];
    }
    if (v == 7) {
      cout << a;
      for (int b = 0; b < 3; b++) {
        if (i & (1 << b)) cout << '+';
        else cout << '-';
        cout << bcd[b];
      }
      cout << "=7" << endl;
      return 0;
    }
  }
  return 0;
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a;
	cin >> a;
	if (a % 10 == 9 || a / 10 == 9)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include<string>
#include<stack>
#include<queue>
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<set>
#include<vector>

#define _CRT_SECURE_NO_WARNINGS

using namespace std;
struct Human
{
	int age;
	double weight;
	char name[256];
};

int findSumOfDigits(int n) {
	int sum = 0;
	while (n > 0) { // n が 0 になるまで
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

int main()
{
	int l[10000];
	int n = 6;

	string s; // s.size() to_string char string %s
	int a,b,c,d;
	int sum = 0;
	vector<string> lang;
	vector<int> data;


	//cin>>N;
	// for (int i = 0; i < N; ++i) cin >> A[i];
	//while(true){break; ++res;}
	//cout << res << endl;
	//sort(a, a+N, greater<int>()) 大きい順ソート
	//set<int>values; values.insert() values.size()
	//map<string,int>salary; salary["John"] = 1400;
	// string num = to_string(counter);

	int count=0;
	int kari = 0;
	int N, K;

	cin >>a>>b>>c;

	if (a < b && b < c)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}




	return 0;
}



Measured memory_bytes: 3088
N,A,B = map(int,input().split())

ans=0

for i in range(1,N+1):
    sum_all=0
    tmp=i
    while(tmp>9):
        sum_all += tmp%10
        tmp//=10
    sum_all += tmp

    if sum_all>=A and sum_all<=B:
        ans+=i
        # print(i)

print(ans)


Measured memory_bytes: 9144
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const ll mod = 1000000007;

vector<bool> visited;

void dfs(const Graph &G, int v) {

    visited[v] = true;

    for (auto u : G[v]) { 
        if(visited[u]) {
            continue;
        }
        dfs(G, u);
    }
}

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

    Graph G(n);
    rep(i, m) {
        int x, y, z;
        cin >> x >> y >> z;
        x--;  y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    int ans = 0;
    visited.assign(n, false);
    rep(i, n) {
        if(visited[i]) {
            continue;
        } 
        dfs(G, i);
        ans++;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10368
import java.util.Scanner;
import java.lang.Math;

public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		System.out.println(Math.min(b/a,c));

	}
}



Measured memory_bytes: 22612
module deque_mod
    implicit none
    type deque
        integer(4),pointer:: v(:)
        integer(4):: l,r
        integer(4):: lmax, rmax
    end type
    private
    public:: deque
    public:: init_deque
    public:: append, appendleft
    public:: pop, popleft
    public:: right, left
    public:: remaining_elements
    public:: remain

contains
    subroutine init_deque(dq)
        ! 初期化
        type(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end subroutine


    subroutine append(dq,num)
        ! 右端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%r+1 > dq%rmax) call add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine appendleft(dq,num)
        ! 左端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%l-1 < dq%lmax) call add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine add_(dq)
        ! arrayの延長
        type(deque):: dq
        integer(4):: l
        integer(4),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(2*dq%lmax:2*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 2*dq%lmax
        dq%rmax = 2*dq%rmax
    end subroutine


    function pop(dq) result(ret)
        ! 右端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function popleft(dq) result(ret)
        ! 左端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function right(dq) result(ret)
        ! 右端を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
    end function

    function left(dq) result(ret)
        ! 左端を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
    end function

    function remaining_elements(dq) result(ret)
        ! 残りの要素数
        type(deque):: dq
        integer(4):: ret 
        ret = dq%r - dq%l + 1
    end function

    function remain(dq) result(ret)
        ! 要素が残っているかどうか
        type(deque):: dq
        logical:: ret
        ret = remaining_elements(dq) > 0
    end function
end module


program name
    use deque_mod
    implicit none
    integer(4):: n,i,cnt,nmax
    type(deque) d

    call init_deque(d)

    read*, n

    call append(d,3)
    call append(d,5)
    call append(d,7)

    nmax = popleft(d)
    cnt=0
    do while(nmax <= n)
        if (shitigosan(nmax))cnt=cnt+1
        call append(d,10*nmax+3)
        call append(d,10*nmax+5)
        call append(d,10*nmax+7)
        nmax = popleft(d)
    end do

    print*, cnt


contains
function shitigosan(num) result(ret)
    logical:: ret, ok3, ok5, ok7
    integer(4):: num,inum,i

    inum = num
    ok3=.false.
    ok5=.false.
    ok7=.false.
    do while(inum>0)
        i = mod(inum,10)
        if (i==3) ok3=.true.
        if (i==5) ok5=.true.
        if (i==7) ok7=.true.
        inum=inum/10
    end do
    ret = ok3 .and. ok5 .and. ok7

end function



end program name

Measured memory_bytes: 3520
import java.util.Arrays;
import java.util.Iterator;
import java.util.PrimitiveIterator;
import java.util.Scanner;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main{
	static Scanner s=new Scanner(System.in);

	void solve(){
		int n=gInt();
		int[]a=new int[n];
		for(int i:rep(n))
			a[i]=gInt()-i;
		Arrays.sort(a);
		int c=a[n/2];
		for(int i:rep(n)){
			a[i]-=c;
		}
		System.out.println(Arrays.stream(a).mapToLong(Math::abs).sum());
	}

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

	static int gInt(){
		return Integer.parseInt(s.next());
	}
	static long gLong(){
		return Long.parseLong(s.next());
	}
	static double gDouble(){
		return Double.parseDouble(s.next());
	}

	SupplyingIterator<Integer> ints(int n){
		return new SupplyingIterator<>(n,Main::gInt);
	}
	SupplyingIterator<Long> longs(int n){
		return new SupplyingIterator<>(n,Main::gLong);
	}
	SupplyingIterator<Double> doubles(int n){
		return new SupplyingIterator<>(n,Main::gDouble);
	}
	SupplyingIterator<String> strs(int n){
		return new SupplyingIterator<>(n,s::next);
	}

	Range rep(int i){
		return Range.rep(i);
	}
	Range rep(int f,int t,int d){
		return Range.rep(f,t,d);
	}
	Range rep(int f,int t){
		return rep(f,t,1);
	}
	Range rrep(int f,int t){
		return rep(t,f,-1);
	}

	IntStream REP(int v){
		return IntStream.range(0,v);
	}
	IntStream REP(int l,int r){
		return IntStream.rangeClosed(l,r);
	}

	IntStream INTS(int n){
		return IntStream.generate(Main::gInt).limit(n);
	}
	Stream<String> STRS(int n){
		return Stream.generate(s::next).limit(n);
	}

}
class SupplyingIterator<T> implements Iterable<T>,Iterator<T>{
	int			t;
	Supplier<T>	supplier;

	SupplyingIterator(int t,Supplier<T> supplier){
		this.t=t;
		this.supplier=supplier;
	}

	@Override
	public Iterator<T> iterator(){
		return this;
	}

	@Override
	public boolean hasNext(){
		return t>0;
	}

	@Override
	public T next(){
		--t;
		return supplier.get();
	}

}
class Range implements Iterable<Integer>,PrimitiveIterator.OfInt{
	int to,cur,d;

	Range(int from,int to,int d){
		this.cur=from-d;
		this.to=to;
		this.d=d;
	}

	Range(int n){
		this(0,n-1,1);
	}

	@Override
	public Iterator<Integer> iterator(){
		return this;
	}

	@Override
	public boolean hasNext(){
		return cur+d==to||(cur!=to&&(cur<to==cur+d<to));
	}

	@Override
	public int nextInt(){
		return cur+=d;
	}

	static Range rep(int i){
		return new Range(i);
	}
	static Range rep(int f,int t,int d){
		return new Range(f,t,d);
	}
	static Range rep(int f,int t){
		return rep(f,t,1);
	}
	static Range rrep(int f,int t){
		return rep(f,t,-1);
	}

}


Measured memory_bytes: 51520
import java.io.*;

class Elem {
    Elem next;
    Elem prev;
    int key;
     
    Elem(int key) {
        this.key = key;
    }
}
 
class DoubleyLinkedList {
    Elem head;
     
    DoubleyLinkedList() {
        head = new Elem(-1);
        head.next = head;
        head.prev = head;
    }
     
    void insert(int key) {
        Elem e = new Elem(key);
        e.next = head.next;
        e.prev = head;
        e.next.prev = e;
        head.next = e;
    }
     
    void delete(int key) {
        for (Elem e = head.next; e != head; e = e.next) {
            if (e.key == key) {
                e.prev.next = e.next;
                e.next.prev = e.prev;
break;
            }
        }
    }
     
    void deleteFirst() {
        Elem e = head.next;
        e.next.prev = head;
        head.next = e.next;
    }
     
    void deleteLast() {
        Elem e = head.prev;
        e.prev.next = head;
        head.prev = e.prev;
    }
     
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Elem e = head.next; e != head; e = e.next) {
            sb.append(e.key);
            sb.append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append('\n');
        return sb.toString();
    }
}
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new FileReader("in1.txt"));
        // BufferedReader br = new BufferedReader(new FileReader("in2.txt"));
        int n = Integer.parseInt(br.readLine());
 
        DoubleyLinkedList list = new DoubleyLinkedList();
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            if (line[0].equals("insert")) {
                list.insert(Integer.parseInt(line[1]));
            } else if (line[0].equals("delete")) {
                list.delete(Integer.parseInt(line[1]));
            } else if (line[0].equals("deleteFirst")) {
                list.deleteFirst();
            } else if (line[0].equals("deleteLast")) {
                list.deleteLast();
            }
        }
        System.out.print(list.toString());
    }
}


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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列 -92
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}



int main(){
    int h,w,a,b;
    cin >> h>>w>>a>>b;
    cout << (h-a)*(w-b) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cstdlib>
using namespace std;
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a==0||b==0)
        printf("Zero\n");
    else if(a<0&&b>0)
        printf("Zero\n");
    else if(b<0)
    {
        if(a==b)
            printf("Positive\n");
        else
        {
            int d=b-a+1;
            if(d%2==0)
                printf("Positive\n");
            else
                printf("Negative\n");
        }
    }
    else if(a>0)
        printf("Positive\n");
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
#define mp make_pair
#define pb push_back
int n;
int a[210];
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)scanf("%d",&a[i]);
	sort(a+1,a+2*n+1);
	int ans=0;
	for(int i=1;i<=n;i++)ans+=a[2*i-1];
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define erep(i, a, b) for (int i = a; i <= (int)(b); i++)
#define per(i, a, b) for (int i = (b)-1; i > (a); i--)
#define eper(i, a, b) for (int i = ((int)(a)); i >= b; i--)
#define pb push_back
#define mp make_pair
#define INF (1 << 30) - 1
#define MOD 1000000007
using namespace std;
typedef long long ll;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int n, m, ans;
map<string, int> s, t;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  rep(i, 0, n) {
    string tmp;
    cin >> tmp;
    s[tmp]++;
  }
  cin >> m;
  rep(i, 0, m) {
    string tmp;
    cin >> tmp;
    s[tmp]--;
  }
  for (auto itr = s.begin(); itr != s.end(); itr++) {
      ans = max(ans, itr->second);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int n,p;
LL dp[55][5555],x[55];
LL solve(int i,int sum)
{
    if(i==n)return (sum%2==p&&sum);
    LL &a=dp[i][sum];
    if(a==-1)
    {
        a=solve(i+1,sum+x[i])+solve(i+1,sum);
    }
    return a;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n>>p;
    for(int i=0;i<n;i++)cin>>x[i];
    cout<<solve(0,0)+(!p);
return 0;
}


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

using ll = long long;

int n;
ll a[222222];

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

   ll ans = 1e16;
   ll rui = 0;
   for (int i = 0; i < n-1; i++) {
      rui += a[i];
      ll b = sum - rui;
      ans = min(ans, abs(rui - b));
   }

   cout << ans << endl;

   return 0;
}

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

int main(){
    string s;
    cin >> s;
    long long k;
    cin >> k;

    for(long long i = 0; i < k; i++){
        if(s[i] != '1'){
            printf("%c\n", s[i]);
            return 0;
        }
    }

    printf("1\n");

    return 0;
}

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



int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<char> C(N);
    for(int i=0;i<N;i++){
        C[i]=S.at(i)
    ;}
    int counter=0;
    for(int i=0;i<N-2;i++){
        if(C[i]=='A'&&C[i+1]=='B'&&C[i+2]=='C')counter++
    ;}
    cout<<counter<<endl;

return 0;


}  



Measured memory_bytes: 256
a = []
for i in range(5):
    a.append(int(input()))
b = []
for i in a:
    if i%10:
        b.append(i)
c = min(b,key = lambda x:x%10) if len(b) else 0
ans = 0
for i in a:
    if i%10:
        ans += i+(10-i%10)
    else:
        ans += i
print(ans-(10-c%10) if len(b) else ans)

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

const int N = 2e3+100, M = 4e6+10;

bitset<M> bt;

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n;cin >> n;
	bt[0] = 1;
	for(int i=0 ; i<n ; i++){
		int d;cin >> d;
		bt |= (bt << d);
	}
	vector<int> v;
	for(int i=1 ; i<M ; i++)
		if(bt[i])
			v.push_back(i);
	int md = v.size()%2 == 0 ? v.size()/2-1 : v.size()/2;
	cout << v[md] << "\n";
 	return 0;
}
















Measured memory_bytes: 11756
import collections
import heapq

def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

class Dijkstra():
    
    def __init__(self):  self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed = False):
        self.e[u].append([v, d])
        self.e[v].append([u, d]) # 有向グラフの場合、コメントアウト

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):

        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while q:
        
            k, u = heapq.heappop(q)
            if v[u]:  continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:  continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

graph = Dijkstra()
N = cin()
for i in range(N - 1): 
    in_ = cin()
    graph.add(in_[0] - 1, in_[1] - 1, in_[2])
min_w, prev = graph.Dijkstra_search(0)
ans = [0 for _ in range(N)]
for i in range(N):  print(min_w[i] % 2)

Measured memory_bytes: 152604
#include<bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
using Graph = vector<vector<int>>;



int main(){
    int N,K,X,Y;
    cin >> N >> K >> X >> Y;
    if(N<=K) cout << N*X << endl;
    else cout << K*X+(N-K)*Y << endl;
}

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

int main()
{
    int L, R, A, B, C, D;
    cin >> A >> B >> C >> D;

    L = A + B;
    R = C + D;
    
    if (L > R) {
        cout << "Left" << endl;
    }
    else if (L == R) {
        cout << "Balanced" << endl;
    }
    else {
        cout << "Right" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n;
int read() {
	char ch = getchar();
	int x = 0, f = 1;
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9') x = x*10 + ch - 48, ch = getchar();
	return x * f;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	int t=n%10;
	if(t==3) cout<<"bon";
	else if(t==0||t==1||t==6||t==8) cout<<"pon";
	else cout<<"hon";
	return 0;
}

Measured memory_bytes: 3656
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int a,b,n;
	while(cin>>a>>b>>n){
		int res=0;
		a%=b;
		int i;
		for(i=0;i<n;i++){
			a*=10;
			res+=a/b;
			a-=a/b*b;
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d,e,time=0,t=0;
	cin>>a>>b>>c>>d>>e;
	if(a<0)///
		for(int i=a;i<0;i++){
			t=t+c;}
		time=t+d+(b*e);
	if(a==0)///
		time=d+(b*e);
	if(a>0)///
		time=(b-a)*e;	
	cout<<time<<endl;	
	
	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define rep3(i, s, n) for (int i = s; i > (int)(n); i--)
#define all(obj) obj.begin(), obj.end()
#define db(x) cerr << #x << ":" << x << " "
#define dbl(x) cerr << #x << ":" << x << "\n"
#define dbv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << "\n"; }
#define YN(f) cout << (f ? "YES" : "NO") << "\n"
#define Yn(f) cout << (f ? "Yes" : "No") << "\n"
#define yn(f) cout << (f ? "yes" : "no") << "\n"
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

int main() {
	ll N; cin >> N;
	cout << N * (N - 1) / 2 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);

		int[] ans = new int['z' - 'a' + 1];
		while (scan.hasNextLine()) {
			String ins = scan.nextLine();
			for (int i = 0; i < ins.length(); i++) {
				if (ins.charAt(i) >= 'a' && ins.charAt(i) <= 'z')
					ans[ins.charAt(i) - 'a'] += 1;
				else if (ins.charAt(i) >= 'A' && ins.charAt(i) <= 'Z')
					ans[ins.charAt(i) - 'A'] += 1;
			}
		}
		for (int i = 0; i < 'z' - 'a' + 1; i++) {
			System.out.println((char)('a' + i) + " : " + ans[i]);
		}

		System.exit(0);
	}

}

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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int N;
    Scd(N);
    double a;
    vector< vector<double> > dp(N+1,vector<double>(N+1,0.0));
    // 確率のDP
    // dp[ni][ci] = ni回まででci回表が出る確率

    double tmp = 0.0;
    double ans = 0.0;
    dp[0][0] = 1.0;
    Rep(ni,N){
        cin >> a;
        Rep(ci,ni+1){
            dp[ni+1][ci] += dp[ni][ci] * (1.0-a);
            dp[ni+1][ci+1] += dp[ni][ci] * a;
        }
    }

    Repe(i,N+1,N/2+1){
        ans += dp[N][i];
    }
    printf ("%1.12lf\n", ans);


    return 0;
}



Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int k,n; cin>>n>>k;
	vector<int>a(n); for(int i=0;i<=n-1;i++) cin>>a[i];
	sort(a.begin(),a.end());
	int res=0; for(int i=0;i<=k-1;i++) res+=a[i];
	cout<<res<<"\n";
	return 0;
}


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

int max(int a,int b){
  if(a>b) return a;
  else return b;
}
double min(double a,double b){
  if(a<b) return a;
  else return b;
}
int absolute(int a,int b){
  if(a-b<0) return -(a-b);
  else return a-b;
}
int translate(char c){
  if(c == '1') return 1;
  if(c == '2') return 2;
  if(c == '3') return 3;
  if(c == '4') return 4;
  if(c == '5') return 5;
  if(c == '6') return 6;
  if(c == '7') return 7;
  if(c == '8') return 8;
  if(c == '9') return 9;
  
}
void Yes(){
  cout << "Yes" << endl;
}
void YES(){
  cout << "YES" << endl;
}
void No(){
  cout << "No" << endl;
}
void NO(){
  cout << "NO" << endl;
}
int main(){
  int N,i; cin >> N;
  
  for(i = N; i <= 999; i++){
  	if(i==111) break;
    if(i==222) break;
    if(i==333) break;
    if(i==444) break;
    if(i==555) break;
    if(i==666) break;
    if(i==777) break;
    if(i==888) break;
    if(i==999) break;
  }
  cout << i << endl;
}

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

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

if((a+b)%2==0){
  cout<< (a+b)/2 <<endl;
}else{
    cout<< "IMPOSSIBLE"<<endl;
}
  return 0;
}
  


Measured memory_bytes: 256
#include<bits/stdc++.h>
/*
g++ -std=c++11 -Wall -g -fsanitize=undefined -D_GLIBCXX_DEBUG agc/agc022/a.cpp
*/
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);//おまじないでcin, cout早くする
    string s;
    cin >> s;
    if(s == "zyxwvutsrqponmlkjihgfedcba"){
        cout << -1 << "\n";
        return 0;
    }
    string alp = "abcdefghijklmnopqrstuvwxyz";
    int used[26];
    rep(i, 26){
        used[i] = 0;
    }
    int n = s.length();
    rep(i, n){
        used[s[i] - 'a'] = 1;
    }

    if(n != 26){
        rep(i, 26){
            if(used[i] == 0){
                cout << s << alp[i] << "\n";
                return 0;
            }
        }
    }

    // n == 26の処理を書く
    for(int i = n - 1; i >= 1; i--){
        used[s[i] - 'a'] = 0;
        rep(j, 26){
            if(used[j] == 0){
                if(alp[j] > s[i - 1]){
                    cout << s.substr(0, i - 1) << alp[j] << "\n";
                    return 0;
                }
            }
        }
    }

    return 0;
}

Measured memory_bytes: 256