akhauriyash/Code-Regression huggingface dataset:
function Main(input){
    input = input.split(" ");

    input[0] = parseInt(input[0], 10);
    input[1] = parseInt(input[1], 10);
    input[2] = parseInt(input[2], 10);
    input[3] = parseInt(input[3], 10);

    if(input[2] >= input[1]){
        console.log(0);
    }else if(input[3] <= input[0]){
        console.log(0);
    }else{
        if(input[0] < input[2]){
            var start = input[2]
        }else{
            var start = input[0]
        }

        if(input[1] < input[3]){
            var end = input[1]
        }else{
            var end = input[3]
        }

        console.log('%d', end - start);
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const ll MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll all(ll n){
  if(n == 1) return 1;
  ll res = 1;
  res += (n / 2) * (n / 2 + 1);
  if(n % 2 == 0){
    res -= n / 2;
  }
  return res;
}
typedef vector<ll> Array;
typedef vector<Array> Matrix;
Matrix mul(const Matrix &a,const Matrix &b){
  Matrix res(a.size(),Array(b[0].size()));
  REP(i,a.size())REP(j,b[0].size())REP(k,a[0].size()){
    res[i][j]=(res[i][j]+a[i][k]*b[k][j])%MOD;
  }
  return res;
}
Matrix pow(const Matrix &a,ll b){
  if(b==0){
    Matrix res(a.size(),Array(a.size()));
    REP(i,a.size())res[i][i]=1;
    return res;
  }
  Matrix res=pow(mul(a,a),b/2);
  if(b&1)res=mul(res,a);
  return res;
}
ll f(ll x){
  if(x == 0) return 1;
  if(x == 1) return 1;
  Matrix m(2, Array(2));
  m[0][0] = 1; m[0][1] = 1;
  m[1][0] = 1; m[1][1] = 0;
  m = pow(m, x);
  return m[0][0];
}

ll solve(ll K){
  if(K == 1) return 1;
  ll lb = 0, ub = 2000000010LL;
  while(ub - lb > 1){
    ll mid = (ub + lb) / 2;
    if(all(mid) < K){
      lb = mid;
    }else{
      ub = mid;
    }
  }
  K -= all(lb);
  ll x = lb + 1;
  //printf("%lldth of %lld\n", K, x);
  for(ll y = 3; y + y <= x; y += 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  for(ll y = (x/2 % 2 == 0) ? (x/2) : (x/2 - 1); y >= 2; y -= 2){
    if(K == 1) return f(y) * f(x - y) % MOD;
    else K--;
  }
  return f(x);
}

int main(){
  ll K;
  while(cin>>K && K){
    cout<<solve(K)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
using namespace std;
int main()
{
 	int n,l;
	cin>>n>>l;
  	vector<string> vect(n+1);
  	for(int i=0; i<=n; i++)
     		getline(cin,vect[i]);
     sort(vect.begin(),vect.end());
     for(int i=0; i<=n; i++)
      cout<<vect[i];
  
}

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

int n,m;
const int N = 2e5+10;
vector<int>adj[N];

bitset<N>v;
int cnt=0;
void dfs(int i) {
    v[i] = 1;
    cnt++;
    for(int j:adj[i])
        if(!v[j])
            dfs(j);
}


void solve(){
    cin >> n >> m;  
    for(int i=0;i<m;++i) {
        int l,r;
        cin >> l >> r;
        adj[l].push_back(r) , adj[r].push_back(l);
    }
    int ans=0;
    for(int i=1;i<=n;++i) {
        if(!v[i]) {
            dfs(i);
            ans=max(ans,cnt) , cnt=0;
        }
    }
    cout << ans << '\n';
}

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


Measured memory_bytes: 23980
#include <bits/stdc++.h>
#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 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 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;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
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; }

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

    ll N, M;
    cin >> N >> M;
    vec2 G(N);
    rep(i, M){
        ll a, b;
        cin >> a >> b;
        --a, --b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    rep(i, N) print(len(G[i]));

    return 0;
}

Measured memory_bytes: 256
n = int(input())
if n == 0:
  print(0)
  exit()
a = [1]
p = [1]
m = [0]
hi = [1]
lo = [1]
i = 0
while(True):
  if n >= lo[i] and n<= hi[i]:
    break
  i += 1
  a.append(a[i-1]*-2)
  if i%2==0:
    p.append(p[i-1]+a[i])
    m.append(m[i-1])
  else:
    p.append(p[i-1])
    m.append(m[i-1]+a[i])
  hi.append(a[i]+p[i-1])
  lo.append(a[i]+m[i-1])
ans = []
for j in range(i+1)[::-1]:
  if n >= lo[j] and n<= hi[j]:
    ans.append(1)
    n-=a[j]
  else:
    ans.append(0)
print(*ans,sep="")

Measured memory_bytes: 9288
import sys

stdin = sys.stdin

mod = 1000000007
inf = 1 << 60

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, k = na()
h = na()
h.sort()
h.reverse()

ans = 0

j = 0
for i in range(n):
    if h[i] > 0:
        if j < k:
            h[i] = 0
            j += 1
        else:
            ans += h[i]
            h[i] = 0

print(ans)

Measured memory_bytes: 79416
/**
**	author : Raghav
**	codechef:raghav_456
**	codeforces:raghavramola7
**/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long int
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void Raghav()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int e1, e2, e3;
	e1 = 0;
	e2 = 0;
	e3 = 0;
	e3 = e1 + e2;
}
int32_t main()
{
	Raghav();
	int a, b, c;
	cin >> a >> b >> c;
	cout << (c / a)*b;
	return 0;
}

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

int n;
bool *isO;

void assign(char **ans, char a0, char a1) {
    char a[n+2];
    a[0] = a0;
    a[1] = a1;
    for (int i = 2; i < n + 2; i++) {
        if ((a[i-1] == 'S') == isO[i-1]) {
            a[i] = a[i-2];
        } else {
            if (a[i-2] == 'S') {
                a[i] = 'W';
            } else {
                a[i] = 'S';
            }
        }
    }

    if (a[0] == a[n] && a[1] == a[n+1]) {
        strncpy(*ans, a, n);
    }
    return;
}

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

    char s[n];
    scanf("%s", s);
    
    char *ans = new char[n];

    isO = new bool[n+2];
    for (int i = 0; i < n; i++) {
        isO[i] = (s[i] == 'o');
    }
    isO[n] = isO[0];
    isO[n+1] = isO[1];

    char sw[] = "SW";

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (*ans == 0) {
                assign(&ans, sw[i], sw[j]);
            }
        }
    }

    if (*ans == 0) { strcpy(ans, "-1"); }

    printf("%s\n", ans);

    return 0;
}

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

#define lint long long
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;

int main() {
    int n;
    scanf("%d", &n);
    int ans = n / 3;
    printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
N=str(input())
L=len(N)
dp=[[0]*2 for _ in range(L)]
dp[0][0]=int(N[0])
dp[0][1]=int(N[0])-1
for i in range(1,L):
  dp[i][1]=max(dp[i-1][0]+max(0,int(N[i])-1),dp[i-1][1]+9)
  dp[i][0]+=(dp[i-1][0]+int(N[i]))
print(max(dp[L-1][0],dp[L-1][1]))

Measured memory_bytes: 3064
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	char lc1Buf[1024];

	// X, Y - 取得
	long long llX, llY;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%lld%lld", &llX, &llY);

	// 判定
	if (llabs(llX - llY) > 1) {
		return 0;
	}
	else {
		return -1;
	}
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	if (liRet == 0) {
		sprintf(lc1Buf, "Alice\n");
	}
	else {
		sprintf(lc1Buf, "Brown\n");
	}
	fOut(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 128
#include <functional>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <climits>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <deque>
#include <list>
#include <map>
#include <set>
using namespace std;

/*** typedef ***/
typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ULL;
typedef pair < int , int > ii;
typedef pair < LL  , LL  > ll;
typedef vector <int>  vint;
typedef vector <bool> vbool;
typedef vector <long> vlong;

/*** define ***/
#define sz(x)			((int)x.size())
#define tin(x)			scanf("%d",&x)
#define all(x)			x.begin(),x.end()
#define Set(b,a)		memset(b,a,sizeof b)
#define print1(x)		printf("Case %d:",x++)
#define tin2(x,y)		scanf("%d%d",&x,&y)
#define tin3(x,y,z)		scanf("%d%d%d",&x,&y,&z)
#define loop(i,i0,in)	for(int i=i0 ; i<in ; i++)
#define rep(i,n)		for(int i=0 ; i<(n) ; i++)
#define _rep(i,n)		for(int i=n-1 ; i>=0 ; i--)
#define _loop(i,in,i0)	for(int i=in-1 ; i>=i0 ; i--)
#define Fore(it, x)		for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
     
int main()  
{  
#ifdef Online_Judge
	freopen("a.in","r",stdin);
#endif
	LL a,b,c;
	cin >> a >> b >> c;
	printf("%s\n",a<b && b<c ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 1116
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(unused_variables)]
#![allow(dead_code)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};

#[allow(unused_macros)]
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

use std::cmp::*;
use std::collections::*;
use std::ops::{Add, Div, Mul, Sub};

#[allow(dead_code)]
static INF_I64: i64 = 92233720368547758;
#[allow(dead_code)]
static INF_I32: i32 = 21474836;
#[allow(dead_code)]
static INF_USIZE: usize = 18446744073709551;
#[allow(dead_code)]
static M_O_D: usize = 1000000007;
#[allow(dead_code)]
static PAI: f64 = 3.1415926535897932;

trait IteratorExt: Iterator {
    fn toVec(self) -> Vec<Self::Item>;
}

impl<T: Iterator> IteratorExt for T {
    fn toVec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

trait CharExt {
    fn toNum(&self) -> usize;
    fn toAlphabetIndex(&self) -> usize;
    fn toNumIndex(&self) -> usize;
}
impl CharExt for char {
    fn toNum(&self) -> usize {
        return *self as usize;
    }
    fn toAlphabetIndex(&self) -> usize {
        return self.toNum() - 'a' as usize;
    }
    fn toNumIndex(&self) -> usize {
        return self.toNum() - '0' as usize;
    }
}

trait VectorExt {
    fn joinToString(&self, s: &str) -> String;
}
impl<T: ToString> VectorExt for Vec<T> {
    fn joinToString(&self, s: &str) -> String {
        return self
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(s);
    }
}

trait StringExt {
    fn get_reverse(&self) -> String;
}
impl StringExt for String {
    fn get_reverse(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

trait UsizeExt {
    fn pow(&self, n: usize) -> usize;
}
impl UsizeExt for usize {
    fn pow(&self, n: usize) -> usize {
        return ((*self as u64).pow(n as u32)) as usize;
    }
}

fn main() {
    input! {
       N: usize,
       K:usize,
       a:[Usize1;N],
    }

    let mut ans: usize = 0;
    let mut used = vec![false; N + 1];
    used[0] = true;
    let mut path = vec![0];
    let mut cur = 0;
    let mut m = 0;
    let mut e = 0;
    loop {
        let b = a[cur];
        if used[b] {
            m = b;
            break;
        } else {
            used[b] = true;
            cur = b;
            path.push(b);
        }
    }
    m = path.iter().position(|&x| x == m).unwrap();
    e = path.len();
    mydbg!(m, e, path);
    if e > K {
        echo!(path[K] + 1);
    } else {
        let mut d = m;
        let mut f = (K - d) % (e - m);
        echo!(path[d + f] + 1);
    }
}


Measured memory_bytes: 6564
n, k = map(int, input().split())
A = list(map(int, input().split()))

# 最大公約数
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

MAX = max(A)
GCD = 0
for i in range(n):
	GCD = gcd(GCD, A[i])

if k % GCD == 0 and k <= MAX:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

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

s = ['a']*(n)
#print(''.join(s))

def dfs(x,alp):
    if x == n:
        print(''.join(s))
        return
    
    for i in range(alp+1):
        #print(x,alp,i)
        s[x] = chr(i+ord("a"))
        dfs(x+1,max(i+1,alp))
        #print(alp)


dfs(0,0)

Measured memory_bytes: 57304
N, M = map(int, input().split())
A = [int(i) for i in input().split()]

D = {}
for i in range(M):
    b,c = map(int, input().split())
    if c in D:
        D[c] += b
    else:
        D[c] = b
        
for a in A:
    if a in D:
        D[a] += 1
    else:
        D[a] = 1
        
D_sort = sorted(D.items(), reverse=True)
check = 0
ans = 0
for d in D_sort:
    check += d[1]
    if check <= N:
        ans += d[0] * d[1]
    else:
        ans += d[0] * (d[1] - (check - N))
        break
print(ans)

Measured memory_bytes: 40736
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 998244353;
typedef pair<ll,ll> P;

ll N;
ll D[100100];
ll cnt[100100];

ll mod_pow(ll x, ll n){
  ll res = 1;
  while(n > 0){
    if(n % 2 == 1) res = (res * x )% MOD;
    x = (x * x) % MOD;
    n /= 2;
  }
  return res;
}

int main() {
  cin >> N;
  rep(i,N){
    cin >> D[i];
    cnt[D[i]]++;
  }
  if (D[0] != 0) {
    cout << "0" << endl;
    return 0;
  }
  
  ll sum = 0;
  ll ans = 1;
  rep(i,N){
    if(sum < N && cnt[i] == 0) {
      cout << "0" << endl;
      return 0;
    }
    if(i == 0 && cnt[i] != 1) {
      cout << "0" << endl;
      return 0;
    }
    
    sum += cnt[i];
    if (i != 0) {
      ans = (ans * mod_pow(cnt[i-1], cnt[i])) %MOD;
    }
    
    
    if (sum == N) break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(long long N, vector<string> s){
	rep(i, N) {
		rep(j, 10) {
			for (ll k = 0; k < 9; k++) {
				char a = s[i][k];
				if (a > s[i][k+1]) {
					s[i][k] = s[i][k+1];
					s[i][k+1] = a;
				}
			}
		}
	}
	SORT(s);
	// rep(i, N) {
	// 	cout << s[i] << endl;
	// }
	ll res = 0, cnt = 0;
	rep(i, N-1) {
		if (s[i] == s[i+1]) ++cnt; else {
			res += cnt*(cnt+1)/2;
			cnt = 0;
		}
		// cout << cnt << " " << res << endl;
	}
	res += cnt*(cnt+1)/2;
	cout << res << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<string> s(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		cin >> s[i];
	}
	solve(N, s);
	return 0;
}



Measured memory_bytes: 14592
#include<cstdio>
using namespace std;
int main()
{
	int mx,n,i,p[10000],sum;
	scanf("%d",&n);
	sum=0;
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
		sum+=p[i];
	}
	mx=0;
	for(i=0;i<n;i++){
		if(mx<p[i]){
			if(p[i]!=n){
				mx=p[i];
			}
		}
	}
	sum=(sum-mx)+mx/2;
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int N;
    cin >> N;
    
    double A;

    double sum = 0;
    
    for(int i = 0; i < N;i++){
        cin >> A;
        sum += 1/A;
    }
    cout <<setprecision(12)<< 1/sum <<endl;

}


Measured memory_bytes: 256
#include <iostream>
#define rep(i, n) for(int i=0; i<n; i++)

int H, W;
using namespace std;

int hy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int wx[] = {1, 1, 0, -1, -1, -1, 0, 1};

//(x, y)がH*Wに収まっているかどうかを算判定
bool closed(int y, int x){
  bool flag = true;
  if(y<0 || H<=y)
    flag = false;
  if(x<0 || W<=x)
    flag = false;
  return flag;
}

int main(void){
  cin >> H >> W;
  string S[H];
  rep(i, H)
    cin >> S[i];
  //入力終了

  rep(i, H){
    rep(j, W){
      //爆弾マスは飛ばす
      if(S[i][j] == '#')
	continue;
      
      //周囲の#の数を数える
      int count = 0;

      rep(k, 8){
	//周囲の座標を計算
	int y = i+hy[k], x = j+wx[k];

	if(closed(y, x) ){
	  //爆弾マスを数える
	  if(S[y][x] == '#')
	    count++;
	}
      }// k roop
      //数値を数字に変換して代入
      S[i][j] = (char)(count+'0');

    }// j roop
  }// i roop

  //解答
  rep(i, H){
    rep(j, W)
      cout << S[i][j];
    cout << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3564
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
int nxt[200001][26];
int dp[200001];
int main() {
	string A;
	cin >> A;
	int N = A.size();
	memset(nxt, -1, sizeof(nxt));
	for (int i = N; i > 0; i--) {
		for (int j = 0; j < 26; j++) {
			nxt[i - 1][j] = nxt[i][j];
		}
		nxt[i - 1][A[i - 1] - 'a'] = i;
	}
	for (int i = N; i > 0; i--) {
		bool all = 1;
		int len = 1 << 30;
		for (int j = 0; j < 26; j++) {
			if (nxt[i][j] == -1) {
				all = 0;
				break;
			}
			else {
				len = min(len, dp[nxt[i][j]]);
			}
		}
		if (all) dp[i] = len + 1;
		else dp[i] = 2;
	}
	string ans = "";
	int now = 0;
	while (1) {
		int to = -1;
		for (int i = 0; i < 26; i++) {
			if (nxt[now][i] == -1) {
				ans += string(1, 'a' + i);
				cout << ans << endl;
				return 0;
			}
			if (to == -1 || dp[nxt[now][to]] > dp[nxt[now][i]]) to = i;
		}
		ans += string(1, 'a' + to);
		now = nxt[now][to];
	}
 }

Measured memory_bytes: 21636
//Bismillahir Rahmanir Rahim
//In the name of Allah the Most Merciful
//Astagfirullahil laji Rabbi Minkulli Jamio
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
int i,j,k;
main()
{
   int n,k;cin>>n>>k;int a[n];
   int b[n],c[n]={0};
   for(i=1;i<=n;i++)
   {
       cin>>a[i];
       b[i]=a[i];
       c[i]=i;
   }
   sort(b+1,b+n+1);
   vector<int> ans;
   for(i=1;i<n;i++)
   {
       if(a[i]+a[i+1]>=k)
       {
           for(j=1;j<i;j++)
           {
               ans.push_back(j);
           }
           for(j=n-1;j>i;j--)
           {
               ans.push_back(j);
           }
     ans.push_back(i);
           break;
       }

   }
  // cout<<b[n]<<endl;
   if(ans.size()==0) cout<<"Impossible"<<endl;
   else
   {
       cout<<"Possible"<<endl;
       for(i=0;i<ans.size();i++)
       {
           cout<<ans[i]<<endl;
       }
   }
}


Measured memory_bytes: 6592
#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(){
    ll n;
    cin >> n;

    string str = "zabcdefghijklmnopqrstuvwxy";
    string ans;
    int a;
    int i=0;
    while(n>0){
        a = n % 26;
        ans.insert(ans.begin(), str[a]);
        n /= 26;
        if(a==0) n--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <string.h>

int main()
{
    long n = 0, k = 0, q = 0;
    long *p = NULL;
    long a = 0, i = 0, min = 0;
    scanf("%ld %ld %ld", &n, &k, &q);
    p = (long *)calloc(n, sizeof(long));
    min = k - q;
    for (i = 0; i < n; i++)
    {
        p[i] = min;
    }
    while (q > 0)
    {
        q--;
        scanf("%ld", &a);
        p[a-1]++;
    }
    for (i = 0; i < n; i++)
    {
        if (p[i] > 0) printf("Yes\n");
        else printf("No\n");
    }
    free(p);
    return 0;
}

Measured memory_bytes: 1280
# coding: utf-8
# Your code here!
N=input()
K=int(input())
num=0
count=0
flag=0
for i in N:
  count+=1
  if int(i)!=1:
    num=int(i)
    flag=1
    break
if count>K or flag==0:
  print(1)
else:
  print(num)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n,m,ans;
ll x[99][99];
int main(){
	scanf("%lld%lld",&n,&m);
	rep(i,0,n)rep(j,0,m)scanf("%lld",&x[i][j]);
	rep(i,0,n)rep(j,i+1,n){
		ll t=0;
		rep(k,0,m)t+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
		ll k=sqrt(t)+1e-10;
		if(k*k==t)ans++;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
//typedef long double ld;
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; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
int main(){
  ll H,N;  cin>>H>>N;
  vector<int> A(N), B(N);
  rep(i,0,N) cin>>A[i]>>B[i];
  ll dp[H+1];
  rep(i,0,H+1) dp[i] = INF;
  dp[0] = 0;
  rep(i,0,N){
    rep(j,0,H+1){
      chmin(dp[min(H, j+A[i])], dp[j] + B[i]);
    }
  }
  cout<< dp[H] << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  ll n;
  cin >> n;

  vector<ll> a(n), l(n), r(n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
  }

  for (ll i = 0; i < n; i++) {
    ll idx = a[i] + i;
    if (idx < n) {
      l[idx]++;
    }
  }

  for (ll i = n - 1; i >= 0; i--) {
    ll idx = i - a[i];
    if (idx >= 0) {
      r[idx]++;
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += l[i] * r[i];
  }

  cout << ans << ln;

  return 0;
}

Measured memory_bytes: 7952
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    string s;
    ll k;
    cin >> s >> k;
    if (k == 1) cout << s[0] << endl;
    else if (s.size() == 1) cout << s[0] << endl;
    else {
        for (int i = 0; i < s.size(); i++) {
            if (i + 1 == k || s[i] != '1') {
                cout << s[i] << endl;
                break;
            }
        }
    }
}

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

using namespace std;

int main(){
    int N;
    cin >> N;
    long long a[100010];
    int c=0;
    for(int i=0;i<N;i++) {
        scanf("%lld",a+i);
        if(a[i]%2) c++;
    }
    cout << (!(c%2)?"YES":"NO")<<endl;
}

Measured memory_bytes: 1024
while 1:
   m,f,r=map(int,input().split())
   if m==f==r==-1:break
   point=m+f
   if m==-1 or f==-1:print("F");continue
   else:
      if 65<=point:print("A" if point>=80 else "B")
      elif 30<=point<80:print("C" if 50<=point<65 or (30<=point<50 and r>=50) else "D")
      else:print("F")


Measured memory_bytes: 5596
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]


n = int(input())
a = list(map(int, input().split()))

a.sort()

print(max(a)-min(a))


Measured memory_bytes: 9040
import itertools
ans = 0
N, K = [int(i) for i in input().split()]
x = 0
y = 0
for i in range(1, N+1):
    if i % K == 0:
        x += 1
    if K % 2 == 0 and i % K == (K//2):
        y += 1
print(x**3 + y**3)


Measured memory_bytes: 9040
from sys import stdin
S = stdin.readline().rstrip()
flag = 0 
if 'AA' in S:
    flag = 1
if 'KA' in S:
    flag = 1
if 'IA' in S:
    flag = 1
if S.replace('A', '') != 'KIHBR':
    flag = 1
if flag:
    print('NO')
else:
    print('YES')

Measured memory_bytes: 3060
import java.util.*;class Main{public static void main(String[]g){Set<Integer> T=new TreeSet<Integer>();int a[]=new int[101],I=0,M=0;for(Scanner S=new Scanner(System.in);S.hasNext();a[S.nextInt()]++);for(;I++<100;)if(a[I]>M){M=a[I];T.clear();T.add(I);}else if(M==a[I])T.add(I);for(int r:T)System.out.println(r);}}


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

long long int n,i;
string s;

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>s;n=s.size();
	for (i=1;i<n+1;i++) cout<<"x";
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var k, a, b int
	fmt.Scan(&k)
	fmt.Scan(&a, &b)
	for i := a; i <= b; i++ {
		if i%k == 0 {
			fmt.Println("OK")
			return
		}
	}
	fmt.Println("NG")
}


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

using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
map<string, int> mp;

int main() {
    ll ans = 0;
    ll n, m;
    cin >> n >> m;
    if (m == 0) {
        cout << n * n << endl;
        return 0;
    }

    for (int j = 1, i = m + 1; i <= n; i++, j++) {
        ans += n / i * j;
        ll tmp = 0;
        tmp = max(0ll, n % i - m + 1);
        ans += tmp;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
	int d, g;
	cin >> d >> g;
	vector<int> p(d), c(d);
	for(int i=0; i < d; i++) {
		cin >> p.at(i) >> c.at(i);
	}

	int ans = 1 << 29;
	for(int i=0; i < (1 << d); i++) {
		int sum = 0, count = 0, last = -1;
		for(int j=0; j < d; j++) {
			if(i & (1 << j)) {
				sum += 100 * (j+1) * p.at(j) + c.at(j);
				count += p.at(j);
			}else{
				last = j;
			}
		}
		if(sum < g) {
			int point = 100 * (last + 1);
			int need =  (g - sum + (point-1)) / point;
			if(need >= p[last]) continue;
			count += need;
		}
		ans = min(ans, count);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007
constexpr int mod = 1000000007;
class mint {
 public:
  long long x;
  constexpr mint(long long x = 0) : x((x % mod + mod) % mod) {}
  constexpr mint operator-() const { return mint(-x); }
  constexpr mint& operator+=(const mint& a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  constexpr mint& operator-=(const mint& a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  constexpr mint& operator*=(const mint& a) {
    (x *= a.x) %= mod;
    return *this;
  }
  constexpr mint operator+(const mint& a) const {
    mint res(*this);
    return res += a;
  }
  constexpr mint operator-(const mint& a) const {
    mint res(*this);
    return res -= a;
  }
  constexpr mint operator*(const mint& a) const {
    mint res(*this);
    return res *= a;
  }
  constexpr mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime mod
  constexpr mint inv() const { return pow(mod - 2); }
  constexpr mint& operator/=(const mint& a) { return (*this) *= a.inv(); }
  constexpr mint operator/(const mint& a) const {
    mint res(*this);
    return res /= a;
  }
};

istream& operator>>(istream& is, const mint& m) {
  is >> m.x;
  return is;
}

ostream& operator<<(ostream& os, const mint& m) {
  os << m.x;
  return os;
}

mint choose(long long n, long long a) {
  mint x, y;
  x.x = 1;
  y.x = 1;
  for (long long i = (0); i < (a); ++i) {
    x *= n - i;
    y *= i + 1;
  }
  return x / y;
}

int main(){
    int n;
    vector<ll> data;
    cin >> n;
    mint sum;
    sum.x = 0;
    REP(i,n){
        ll x;
        cin >> x;
        data.push_back(x);
        sum += x;
    }
    mint ans;
    ans.x = 0;
    REP(i,n-1){
        sum -= data[i];
        mint tmp;
        tmp.x = data[i];
        tmp *= sum;
        ans += tmp;
        
    }
    cout << ans << endl;
}

Measured memory_bytes: 5364
#include <iostream>
#include <cstdio>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>

#include <numeric>
#include <algorithm>
#include <functional>

#include <cctype>

#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(unsigned int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                             it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))

typedef long long ll;
typedef complex<double> P;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;
const int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

const int H = 1000;
int main(){
    while(true){
        int n,m,a;
        cin >> n >> m >> a;
        a--;
        if(n==0) break;
        vector<vector<int> > V(H,vector<int>(n,-1));
        rep(i1,m){
            int h,p,q;
            cin >> h >> p >> q;
            h--;p--;q--;
            V[h][p] = q;
            V[h][q] = p;
        }
        int now = a;
        for(int i=H-1;i>=0;i--){
            if(V[i][now] == -1) continue;
            now = V[i][now];
        }
        cout << (now+1) << endl;
    }
    return 0;

}

Measured memory_bytes: 1600
#![allow(unused_imports)]
// use itertools::Itertools;
use proconio::{input, marker::*};

fn main() {
    input! {
        n: String
    };
    let x: usize = n.parse().unwrap();
    let fx: usize = n
        .chars()
        .into_iter()
        .map(|c| c.to_digit(10).unwrap() as usize)
        .sum();
    println!("{}", ["No", "Yes"][(x % fx == 0) as usize]);
}


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

#define Set(a, b) memset(a, b, sizeof (a))
#define For(i, j, k) for (int i = j; i <= k; ++ i)
#define Forr(i, j, k) for (int i = j; i >= k; -- i)

using namespace std;

typedef long long ll;

inline void File() {
	freopen("f.in", "r", stdin);
	freopen("f.out", "w", stdout);
}

const int N = 2.5e5 + 10;
int n; char s[N];
ll st[N], p[N];

const ll mod = 1000000000000000031ll;
const ll gkk = 1000000000000000003ll;
const ll hany01 = 821428571428571454ll;

ll mul(ll a, ll b) { return (__int128) a * b % mod; }
ll add(ll a, ll b) { return (a += b) >= mod ? a - mod : a; }

unordered_map<ll, int> mp;

int main() {

	cin >> n, scanf("%s", s + 1);

	p[0] = 1;
	For(i, 1, n) {
		st[i] = st[i - 1], p[i] = p[i - 1];
		if (s[i] == '+') st[i] = add(st[i], p[i]);
		if (s[i] == '-') st[i] = add(st[i], mod - p[i]);
		if (s[i] == '>') p[i] = mul(p[i], gkk);
		if (s[i] == '<') p[i] = mul(p[i], hany01);
	}

	ll ans = 0;
	Forr(i, n, 1) {
		++ mp[st[i]];
		ans += mp[add(mul(st[n], p[i - 1]), st[i - 1])];
	}

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


Measured memory_bytes: 24052
A,B,C,D=map(int, input().split())
if A<=C and B<=D and B>C:
 print(B-C)
elif A<C and B>D:
 print(D-C)
elif A>C and B<D:
 print(B-A)
elif A>=C and B>=D and D>A:
 print(D-A)
else:
 print(0)


Measured memory_bytes: 2940
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int n,k;
  int a[100001];
  while(cin>>n>>k){
    if(n==0) break;
    REP(i,n)cin>>a[i];
    int sum = 0;
    int mx;
    REP(i,k){
      sum+=a[i];
    }
    mx = sum;
    for(int i=k;i<n;i++){
      sum-=a[i-k];
      sum+=a[i];
      mx = max(sum,mx);
    }
    cout<<mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 1220
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    #dp[i][j]...i番目までの品物から重さがjを超えないよう選んだ時の勝ちの総和の最大値
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 123784
from sys import stdin
#stdin = open("input.txt")

if __name__ == "__main__":
    N = int(stdin.readline())
    a = [int(item) for item in stdin.readline().split()]

    a.sort(reverse=True)
    total = 0
    for i in range(N):
        index = 1 + i*2
        total += a[index]
    print(total)
        
        

Measured memory_bytes: 106720
import sys

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)


Measured memory_bytes: 31424
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 998244353LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}

template<int N, typename T, T M>
struct ModFact {
    T fact[N+1];
    T ifact[N+1];
    constexpr ModFact() : fact(), ifact() {
        fact[0] = 1;
        for (int i=0; i<N; ++i)
            fact[i+1] = (fact[i]*(i+1))%M;
        ifact[N] = power(fact[N], M-2);
        for (int i=N-1; i >= 0; --i)
            ifact[i] = (ifact[i+1]*(i+1))%M;
    }
    constexpr T power(T a, T b) {
        T r = 1;
        while (b>0) {
            if((b&1)!=0) r = (r*a)%M;
            a = (a*a)%M;
            b >>= 1;
        }
        return r;
    }
    constexpr T comb(T n, T r) {
        return (((fact[n]*ifact[r])%M)*ifact[n-r])%M;
    }
};
 
ModFact<300000, ll, MOD> fact;

int main() {
    fastio();
    ll N, A, B, K, ans = 0;
	cin >> N >> A >> B >> K;
    ll g = gcd(A, B);
    if(K%g==0) {
        ll s, ca=B/g, cb=A/g;
        ll oa=min(N, K/A), ob=min(N, K/B);
        int i=0, j=ob;
        while(i<=oa) {
            while ((s=i*A+j*B)>K) j--;
            if (s==K) break;
            i++;
        }
        while(i<=N && j>=0) {
            ans += fact.comb(N,i)*fact.comb(N,j);
            if(ans > MOD) ans %= MOD;
            i += ca; j -= cb;
        }
    }
    cout << ans << "\n";
	return 0;
}


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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;
const double PI=3.1415926535897932;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll gcd(ll a, ll b){
    ll tmp;
    if(a%b == 0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
}


const ll SIZE = 20;
ll n;
double x[SIZE],y[SIZE];
double ans;


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

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            ans += sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
        }
    }
    double mem = 1;
    for(int i = 2; i < n; i++){
        mem += 0.5;
    }
    
    cout <<  fixed << setprecision(10) << ans /mem << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef map<char,int> mci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vii;
typedef vector<char> vc;
typedef vector<vc> vcc;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define F first
#define S second
#define in insert
#define mina(a,b) (a)=min((a),(b));
#define maxa(a,b) (a)=max((a),(b));
const ll INF = 1e16 + 7;

void solve(){
    ll n,mi=INF;
    cin>>n;
    for(int i = 0; i < 5; i++){
        ll t; cin>>t;
        mina(mi,t);
    }
    ll v=n/mi;
    if(n%mi>0) v++;
    cout<<4+v;
}
int main(){
    int T=1;
    //cin>>T;
    for(int i = 0; i < T; i++) solve(); 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> P;
#define MOD 1000000007
#define INF 1000000000
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
int modpow(int a,int b){
    if(!b)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int fac(int a){
    int Ans=1;
    for(int i=1;i<=a;i++){
        Ans*=i;
        Ans%=MOD;
    }
    return Ans;
}//kaijo
int comb(int a,int b){
    return fac(a)*modpow(fac(a-b),MOD-2)%MOD*modpow(fac(b),MOD-2)%MOD;
}
int main(){
	int n,i;
	cin>>n>>i;
cout<<n-i+1<<endl;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

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

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int H, W;
  cin >> H >> W;
  vector<vector<int>> as(H, vector<int>(W)), bs(H, vector<int>(W)), cs(H, vector<int>(W));
  F0R(r, H) {
    F0R(c, W) {
      cin >> as[r][c];
    }
  }
  int cmax = 0;
  F0R(r, H) {
    F0R(c, W) {
      cin >> bs[r][c];
      cs[r][c] = abs(as[r][c] - bs[r][c]);
      chmax(cmax, cs[r][c]);
    }
  }

  int bc = cmax * (H+W) + 1;
  vector<vector<vector<bool>>> ns(H, vector<vector<bool>>(W, vector<bool>(bc, false)));
  ns[0][0][cs[0][0]] = true;

  FOR(i, 1, H + W + 1) {
    int r = i, c = 0;
    if (r > H - 1) {
      c += r - (H - 1);
      r = H - 1;
    }
    for (; r >= 0 && c < W; r--, c++) {
      //cout << r << ',' << c << newl;
      int n = cs[r][c];

      if (r > 0) {
        F0R(j, bc){
          if (j + n < bc) ns[r][c][j + n] = ns[r][c][j + n] | ns[r - 1][c][j];
          ns[r][c][abs(j - n)] = ns[r][c][abs(j - n)] | ns[r - 1][c][j];
        }
      }
      if (c > 0) {
        F0R(j, bc) {
          if (j + n < bc) ns[r][c][j + n] = ns[r][c][j + n] | ns[r][c - 1][j];
          ns[r][c][abs(j - n)] = ns[r][c][abs(j - n)] | ns[r][c - 1][j];
        }
      }
      /*
      F0R(j, bc) {
        if (ns[r][c][j]) {
          cout << j << ' ';
        }
      }
      cout << newl;
      //*/
    }
  }

  F0R(i, bc) {
    if (ns[H - 1][W - 1][i]) {
      cout << i;
      break;
    }
  }
}
#endif


Measured memory_bytes: 10880