akhauriyash/Code-Regression huggingface dataset:
<?php
[$N, $K] = ints();
$dp[0] = array_merge([0],ints());
for($i = 1; $i < 64; $i++){
  $dpi = &$dp[$i];
  $dpim = $dp[$i-1];
  for($j = 1; $j <= $N; $j++){
    $dpi[$j] = $dpim[$dpim[$j]];
  }
}
$c = 1;
$i = 0;
while($K >> $i){
  if($K >> $i & 1)$c=$dp[$i][$c];
  $i++;
}
echo $c;

function str(){return trim(fgets(STDIN));}
function ints($n = false){
  if($n===false){
    return array_map('intval',explode(' ',trim(fgets(STDIN))));
  }else{$ret = [];for($i = 0; $i < $n; $i++)foreach(array_map('intval',explode(' ',trim(fgets(STDIN)))) as $j => $v)$ret[$j][] = $v;return $ret;}
}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$M = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      $G[$a][] = $b;
      if($both)$G[$b][] = $a;
    }else{
      list($a, $b, $d) = $values;
      $G[$a][] = [$b, $d];
      if($both)$G[$b][] = [$a, $d];
    }
  }
  return $G;
}

Measured memory_bytes: 423572
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(n):
    l[i]=l[i]-i
l.sort()
#print(l)
if n%2==1:
    a=l[n//2]
    for i in range(n):
        s+=abs(l[i]-a)
else:
    a=(l[n//2]+l[n//2-1])//2
    for i in range(n):
        s+=abs(l[i]-a)
print(s)

Measured memory_bytes: 26180
def mp2(k):
    kk=k
    mp=0
    while kk>=1:
        kr=kk%2
        if kr==0:
            kk=kk//2
            mp=mp+1
#            print(kk,kr,mp)
        else:
#            print(kk,kr,mp)
            return mp
    return mp
        

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

cnt0=0
cnt1=0
cnt2=0
for i in range(n):
    m=min(2,mp2(a[i]))
    if m==0:
        cnt0=cnt0+1
    elif m==1:
        cnt1=cnt1+1
    elif m==2:
        cnt2=cnt2+1

#print(cnt0,cnt1,cnt2)

if cnt1==0:
    if cnt2>=cnt0-1:
        print("Yes")
    else:
        print("No")
else:
    if cnt2>=cnt0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 14480
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
	int a, b;
	char c1;

	while(true){
		scanf("%d %c %d", &a, &c1, &b);
		if(c1 == '?') break;

		switch(c1){
			case '+' : printf("%d\n", a+b); break;
			case '-' : printf("%d\n", a-b); break;
			case '*' : printf("%d\n", a*b); break;
			case '/' : printf("%d\n", a/b); break;
		}
	}
	return 0;
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;
  if(m1 != m2) cout << 1 << endl;
  else cout << 0 << endl;
}

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	vector< pair<int, int>> st;
	vector< pair<int, int>> ck;
	for(int i=0; i<n; i++){
		int a, b;
		cin >> a >> b;
		st.pb(make_pair(a, b));
	}
	for(int i=0; i<m; i++){
		int c, d;
		cin >> c >> d;
		ck.pb(make_pair(c, d));
	}

	for(int i=0; i<n; i++){
		ll mi = INF;
		ll ans;
		for(int j=0; j<m; j++){
			ll dist = abs(st[i].first - ck[j].first) + abs(st[i].second - ck[j].second);
			//cout << "dist:" << dist << endl;
			if(dist < mi){
				mi = dist;
				ans = j+1;
			}
		}
		cout << ans << endl;
	}

	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <cstdio>
#include <string>
#define MAX 1001

using namespace std;

int times[MAX];
int exist[MAX];
int last[MAX];

int main()
{
	int month, day, hour, minute, id, t;
	char op;
	while (cin >> t, t)
	{
		memset(times, 0, sizeof(times));
		memset(last, 0, sizeof(last));
		memset(exist, 0, sizeof(exist));
		int maxtime = 0;
		while (t--)
		{
			scanf("%d/%d %d:%d %c %d", &month, &day, &hour, &minute, &op, &id);
			int nowtime = hour * 60 + minute;
			//cout << month << day << hour << minute << op << id << endl;
			if (op == 'I')
			{
				exist[id] = 1;
			}
			else
			{
				if (id == 0)
				{
					for (int i = 1; i <= 1000; i++)
					{
						if (exist[i])
						{
							times[i] += nowtime - ((last[0] > last[i]) ? last[0] : last[i]);
						}
					}
				}
				else
				{
					if (exist[0])
					{
						times[id] += nowtime - ((last[0] > last[id]) ? last[0] : last[id]);
					}
				}
				exist[id] = 0;
			}
			last[id] = nowtime;
		}
		for (int i = 1; i <= 1000; i++)
		{
			if (times[i] >= maxtime)
			{
				maxtime = times[i];
			}
		}
		cout << maxtime << endl;
	}
	return 0;
}

Measured memory_bytes: 1256
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#define stop(x) {cout<<x<<endl;exit(0);}
#define all(x) x.begin(),x.end()
#define szz(s) int(s.size())
#define endl '\n'
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
typedef long long ll;
using namespace std;

void file() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    if (freopen("input.txt", "r", stdin));
    if (freopen("output.txt", "w", stdout));
#endif
}


ll n;
ll mem[100004][4];
vector < vector < int > > v;

ll solve(int idx , int last) {
    if (idx == n)return 0;

    ll& ret = mem[idx][last];
    if (~ret)return ret;
    ret = 0;
    if (last != 0)ret = max(ret, solve(idx + 1, 0) + v[idx][0]);
    if (last != 1)ret = max(ret, solve(idx + 1, 1) + v[idx][1]);
    if (last != 2)ret = max(ret, solve(idx + 1, 2) + v[idx][2]);
    return ret;
}

int main() {
    //file();

    memset(mem, -1, sizeof mem);
    cin >> n;
    v = vector < vector < int > >(n, vector < int >(3));
    for (auto& e : v)
        for (auto& f : e)
            cin >> f;

    cout << solve(0,3) << endl;

}

Measured memory_bytes: 15104
#include "bits/stdc++.h"
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
using ll = long long;
using namespace std;

void comb(vector<vector <long long int > > &v) {
	ll mod = 1000000007;
	for (int i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (int k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%mod;
			
		}
	}
}

int main() {
	ll n, k;
	cin >> n >> k;

	vector<vector<long long int> > v(n + 1, vector<long long int>(n + 1, 0));
	comb(v);

	ll ans[2200];
	ll mod = 1000000007;
	ans[1] = (n - k + 1) % mod;

	rep(i, 2, k + 1) ans[i] = (v[n - k+1][i] * v[k - 1][i - 1])%mod;
	rep(i, 1, k + 1) cout << ans[i] << endl;

}

Measured memory_bytes: 31616
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d,e,k;
	cin>>a>>b>>c>>d>>e>>k;
	if(b-a<=k&&c-a<=k&&d-a<=k&&e-a<=k&&c-b<=k&&d-b<=k&&e-b<=k&&d-c<=k&&e-c<=k&&e-d<=k){
		cout<<"Yay!";
	}
	else cout<<":(";
	return 0;
} 

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cmp::*;
use std::collections::*;

const NOTHING: usize = std::usize::MAX;

fn main() {
    let (n, m): (usize, usize) = readln();
    let mut gr: Vec<Vec<(usize, usize)>> = vec![vec![];n];
    let mut src: Vec<usize> = vec![NOTHING;m];
    let mut dst: Vec<usize> = vec![NOTHING;m];
    let mut used: Vec<bool> = vec![false;m];
    for i in 0..m {
        let (a, b): (usize, usize) = readln();
        let a = a - 1;
        let b = b - 1;
        src[i] = a;
        dst[i] = b;
        gr[a].push((b, i));
        gr[b].push((a, i));
    }

    fn dfs(gr: &Vec<Vec<(usize, usize)>>, used: &mut Vec<bool>, cur: usize, goal: usize) -> bool {
        if cur == goal {
            return true;
        } else {
            for &(v, i) in &gr[cur] {
                if used[i] {
                    continue;
                } else {
                    used[i] = true;
                    return dfs(gr, used, v, goal);
                }
            }
            return false;
        }
    }

    for i in 0..m {
        if used[i] {
            continue;
        }
        used[i] = true;
        if dfs(&gr, &mut used, src[i], dst[i]) {
            continue;
        } else {
            println!("NO");
            return;
        }
    }
    println!("YES");

}


fn get_line() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_string()
}

fn get_chars() -> Vec<char> {
    get_line().chars().collect()
}

fn readln<T: Read>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

trait Read {
    fn read(s: &str) -> Self;
}

macro_rules! read_impl{
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl<T: Read> Read for Vec<T> {
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C) {
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

Measured memory_bytes: 14588
using System;
using System.Text;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int d = sc.NextInt();
        int n = sc.NextInt();
        long ans = n == 100 ? 101 : n;
        for (int i = 0; i < d; i++)
        {
            ans *= 100;
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

ll inf = 1e18;
int const N = 100000;
vector<pair<int, int> > ed[N + 1];

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	f(i, 0, m){
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		ed[r].emplace_back(l, c);
	}
	map<int, ll> st;
	st[1] = 0;
	f(i, 2, n + 1){
		ll an = inf;
		f(j, 0, ed[i].size()){
			int l = ed[i][j].first, c = ed[i][j].second;
			an = min(an, st.lower_bound(l)->second + c);
		}
		while (st.rbegin()->second >= an)st.erase(--st.end());
		st[i] = an;
	}
	printf("%lld\n", st.rbegin()->second >= inf ? -1 : st.rbegin()->second);
}

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

int main(){
  int r;
  cin>>r;
  if(r<1200){
    cout<<"ABC"<<endl;
  }

  else if(1200<=r && r<2800){
    cout<<"ARC"<<endl;
  }

  else{
    cout<<"AGC"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using i128 = boost::multiprecision::int128_t;
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using VVV = vector<VV>;
using VVVll = vector<VVll>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
const int MOD  = int(1e9)+7;
// const int MOD  = 998244353;


int main() {
  ll n; cin >> n;
  // --n;

  string ans = "";

  while (n) {
    ans.push_back('a' + ((n+25)%26));
    n = (n+25) / 26 - 1;
  }

  reverse(all(ans));
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 3652
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long ans = a * c;
    ans = max(ans, b * d);
    ans = max(ans, a * d);
    ans = max(ans, b * c);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int main(){
	
	int X,Y;
	cin>>X>>Y;
	
	for(int i=0;i<=X;i++){
		if(2*i + 4*(X-i) == Y){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	
	cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 3568
#include <stdio.h>
int main()
{
	int n;
	scanf("%i",&n);
	int a[n+1];
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&a[i]);
	}
	int dp[n+1];
	dp[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(a[i]<=a[i-1])
		{
			dp[i]=dp[i-1]+1;
			//prnitf("1\n");
		}
		else
		{
			dp[i]=0;
			//printf("")
		}
		//printf("%i\n",dp[i]);
	}
	int maks=0;
	for(int i=1;i<=n;i++)
	{
		if(dp[i]>maks)	maks=dp[i];
	}
	printf("%i",maks);
	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
const ll INF = 1e13;
typedef pair<ll,ll> P;
int main(){
    int n;
    cin >> n;
    int a[100001];
    rep(i,n){
        cin >> a[i];
    }
    ll color[3] = {0};
    ll ans = 1;
    ll c;
    ll check = 0;
    rep(i,n){
        if (i == 0){
            if (a[i] > 0){
                ans = 0;
                break;
            }
            color[0]++;
            ans *= 3;
            continue;
        }
        rep(j,3){
            if (a[i] == color[j]){
                check++;
                c = j;
            }
        }
        if (check == 0){
            ans = 0;
            break;
        }
        ans *= check;
        ans %= 1000000007;
        color[c]++;
        check = 0;
    }
    c = 0;
    rep(i,3){
        if (color[i] != 0) c++;
    }
    PRINT(ans);
}

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

sumA = sum(A)/2

i = 0
j = 0

while i < sumA:
    i = i+A[j]
    j += 1

ans1 = abs(sum(A[0:j]) - sum(A[j:N]))
ans2 = abs(sum(A[0:j-1]) - sum(A[j-1:N]))
ans3 = abs(sum(A[0:j+1]) - sum(A[j+1:N]))
print(min(ans1,ans2,ans3))

Measured memory_bytes: 26220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<l_l, l_l> llll;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

//const ll mod = 1000000007;
const ll INF = 1e17;
ll N;
ll R[2005], A[2005], W[2005], T[2005];
ll Prev[4005];
ll Next[4005];
ll Next2[4005];
vector<llll> v;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    v.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> v[i].second.second >> v[i].second.first >> v[i].first.second >> v[i].first.first;
        v[i].first.first += v[i].second.second;
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < N; i++) {
        v[i].first.first -= v[i].second.second;
        R[i+1] = v[i].second.second;
        A[i+1] = v[i].second.first;
        W[i+1] = v[i].first.second;
        T[i+1] = v[i].first.first;
    }
    //for(int i = 0; i <= 4000; i++) Prev[i] = -INF;
    Prev[1] = 0;
    for(int song = 1; song <= N; song++) {
        for(int j = 0; j <= 4000; j++) {
            Next[j] = -INF;
            Next2[j] = -INF;
        }
        for(int j = 1; j <= 4000; j++) {
            if(j - 2 * R[song] >= 1 && j - R[song] <= T[song]) Next[j] = Prev[j - 2 * R[song]] + W[song] + A[song];
            else Next[j] = -INF;
        }
        for(int j = 1; j <= 4000; j++) {
            if(j - R[song] >= 1 && j - R[song] <= T[song]) chmax(Next[j], Next[j - R[song]] + W[song]);
        }
        for(int j = 4000; j >= 0; j--) {
            if(j - R[song] >= 1 && j - R[song] <= T[song]) chmax(Prev[j], Prev[j - R[song]] + A[song]);
            chmax(Prev[j], Next[j]);
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 4000; i++) {
        chmax(ans, Prev[i]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3392
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  int K,N;
  cin >> K >> N;
  int A[N];
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  int B[N];
  int max=0;
  for(int i=1;i<N+1;i++){
    if(i==N){
      B[i-1]=K-A[i-1]+A[0];
    }
    else{
      B[i-1]=A[i]-A[i-1];
    }
    if(B[i-1]>max){
      max=B[i-1];
    }
  }//A0~1->B0
  
  cout << K-max;
  cout << endl;
  return 0;
}


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

using namespace std;

int n;
double probs[3000];
double memo[3000][3000];

double dp(int a, int heads)
{
    if (a == n)
    {
        if (heads * 2 > n)
            return 1;
        else
            return 0;
    }
    if (memo[a][heads] >= 0)
        return memo[a][heads];
    double x;
    x = (probs[a] * dp(a + 1, heads + 1)) + ((1 - probs[a]) * dp(a + 1, heads));
    memo[a][heads] = x;
    return x;
}

int main(void)
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    memset(memo, -1, sizeof(memo));
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        cin >> probs[i];
    }
    double res;
    res = dp(0, 0);
    cout.precision(10);
    cout << res << endl;
    
}

Measured memory_bytes: 74292
#include <stdio.h>
int connect[51][51]={0};
int visited[51]={0},n;
int dfs(int a){
    visited[a]=1;
    for(int i=1;i<=n;i++){
        if(connect[a][i]==1&&visited[i]==0){
            dfs(i);
        }
    }
}
int main()
{   int m;
    scanf("%d%d",&n,&m);
    int a[m],b[m];
    for(int i=0;i<m;i++){
        scanf("%d%d",&a[i],&b[i]);
        connect[a[i]][b[i]]++;
        connect[b[i]][a[i]]++;
    }
    int ans=0;
    for(int i=0;i<m;i++){
        for(int j=1;j<=n;j++){
            visited[j]=0;
        }
        connect[a[i]][b[i]]=0;
        connect[b[i]][a[i]]=0;
        dfs(1);
        for(int j=1;j<=n;j++){
            if(visited[j]==0){
                ans++;
                break;
            }
        }
        connect[a[i]][b[i]]=1;
        connect[b[i]][a[i]]=1;
    }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 128
N, M, C = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(N)]

ans = 0
for a_row in A:
    tmp = C
    for a, b in zip(a_row, B):
        tmp += a * b
    if tmp > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3060
N=int(input())
A=list(map(int,input().split()))
A.append(0)
m=1000
kabu=0
for i in range(N):
  if A[i]>A[i+1]:
    m+=A[i]*kabu
    kabu=0
  if A[i]<A[i+1]:
    kabu+=m//A[i]
    m-=A[i]*(m//A[i])
    
print(m)

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

int main(void) {
    string s;
    int m, h, c, n, i;
    while (1) {
        cin >> s;
        if (s == "-") break;
        cin >> m;
        n = s.size();
        c = 0;
        for (i = 0; i < m; i++) {
            cin >> h;
            c = (c + h) % n;
        }
        cout << s.substr(c) << s.substr(0, c) << endl;
    }
    return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<"="<<x
#define nl cout<<"\n"
#define frn(i,n) for(int i = 0;i < n;i++)
#define fr(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define trav(x,c) for(auto &x:c)
using namespace std;

int toint(string s) {
  int ans = 0;
  for(char x: s) ans = ans*10 + (x - '0');
  return ans;
}

int sum(int x) {
  int s = 0;
  while(x) {
    s += x%10;
    x /= 10;
  }
  return s;
} 

int main() {
  string s;
  cin>>s;
  cout<<s[0]<<s.size()-2<<s[s.size()-1];
}

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

using namespace std;

int main(){

    string x,y;
    cin >> x;
    cin >> y;

    if(x<y) cout << "<";
    if(x>y) cout << ">";
    if(x==y) cout << "=";

    return 0;
}

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

int main() {

	ll n, m; cin >> n >> m;
	vector<ll> x(m);
	for (ll i = 0; i < m; i++) {
		cin >> x[i];
	}
	sort(x.begin(), x.end());
	vector<ll> dist(m - 1);
	for (ll i = 0; i < m - 1; i++) {
		dist[i] = x[i + 1] - x[i];
	}
	sort(dist.rbegin(), dist.rend());
	ll cnt = n - 1;
	ll ans = 0;
	for (ll i = 0; i < m - 1; i++) {
		if (0 < cnt) {
			cnt--;
			continue;
		}		
		ans += dist[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4616
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    mod = 10 ** 9 + 7

    ans = pow(10,N,mod)
    ans -= 2 * pow(9,N,mod)
    ans %=mod
    ans += pow(8,N,mod)
    print(ans%mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61720
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool used[110];

bool cmp(const pair<int,int> &a,const pair<int,int> &b) {
	return a.first * a.first + a.second * a.second > b.first*b.first + b.second * b.second;
}

int main(void){
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b) {
		if (b == c) {
			cout << "Yes" << endl;
		}
		else cout << "No" << endl;
	}
	else cout << "No" << endl;
	return 0;
}

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

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

    int n = (int)s.size();
    int r = 0;
    char c = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != c) c = s[i], r++;
    }

    cout << r - 1 << endl;

    return 0;
}

Measured memory_bytes: 512
#include<iostream> 
#include<string> 
#include<vector> 
#include<algorithm> 
#include<cmath>
using namespace std; 

int square(int x)
{
	return x * x;
}
int main()
{
	int n;
	cin >> n;
	vector<int> s(n);
	int sum = 0;
	
	for (int i = 0; i < n; i++)
	{
		cin >> s.at(i);
		sum += s.at(i);
	}
	
		int h = sum / n;
	
		int k = sum / n+1;
	
	int ans = 0;
	int ans1 = 0;
	for (int i = 0; i < n; i++)
	{
		int a = abs(h-s.at(i));
		ans += square(a);
		int b = square(k - s.at(i));
		ans1 += b;
	}
	cout <<min(ans1, ans )<< endl;
}

Measured memory_bytes: 256
import heapq

if __name__ == "__main__":
    K,T = map(int, input().split())
    data = list(map(int, input().split()))
    cake = []
    for i,x in enumerate(data):
        cake.append([x, i])
    heapq._heapify_max(cake)
    while (len(cake) > 1):
        heapq._heapify_max(cake)
        p = heapq.heappop(cake)
        q = heapq.heappop(cake)
        # print (p,q)
        p[0] -= 1
        q[0] -= 1
        if p[0] > 0:
            heapq.heappush(cake, p)
        if q[0] > 0:
            heapq.heappush(cake, q)
    result = 0
    if len(cake) > 0:
        t = heapq.heappop(cake)
        result = t[0]
    print (max(0, result - 1))


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const ll MOD = 1000000007;
const double EPS = 1e-9;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;



int main(void){

    string k;
    int d;
    cin>>k>>d;
    ll dp[k.size()+10][2][d+10];
    rep(i,k.size()+10)rep(j,2)rep(k,d+10)dp[i][j][k] = 0;

    dp[0][1][0]=1;
    for(int i=0;i<k.size();i++){
        // きつい
        for(int j=0;j<d;j++){
            for(int m=0;m<=k[i]-'0'-1;m++){
                dp[i+1][0][(j+m)%d]+=dp[i][1][j];
                dp[i+1][0][(j+m)%d]%=MOD;
            }
            dp[i+1][1][(j+(k[i]-'0'))%d]+=dp[i][1][j];
            dp[i+1][1][(j+(k[i]-'0'))%d]%=MOD;
        }

        //緩い
        for(int j=0;j<d;j++){
            for(int m=0;m<=9;m++){
                dp[i+1][0][(j+m)%d]+=dp[i][0][j];
                dp[i+1][0][(j+m)%d]%=MOD;
            }
        }
    }

    ll ans=0;

    ans+=dp[k.size()][0][0];
    ans%=MOD;
    ans+=dp[k.size()][1][0];
    ans%=MOD;

    fin((ans-1+MOD)%MOD);

}


Measured memory_bytes: 17408
fun main(args: Array<String>) {
    val (N, Y) = readIntList()

    for (x in 0..N) {
        val Yyz = Y - 10000 * x
        if (Yyz < 0) break

        for (y in 0..N - x) {
            val Yz = Yyz - 5000 * y
            val z = Yz / 1000
            if (z < 0) break
            if (x + y + z == N) {
                println("$x $y $z")
                return
            }
        }
    }
    println("-1 -1 -1")
}

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

Measured memory_bytes: 37904
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	ll N = 5;
	ll A[N];
	for (ll i = 0; i < N; ++i) cin >> A[i];
 
	// 解法
	ll gap[N];
	REP(i,N) gap[i] = (1000 - A[i])%10;
	sort(gap,gap+N);
	REP(i,N) A[i] = ((A[i]-1)/10+1)*10;
	// REP(i,N)printf("%lld ", A[i]);
	// printf("\n");
	ll ans = 0;
	REP(i,N) ans+=A[i];
	ans -= gap[N-1];
	
	//出力
	cout << ans << endl;
}


Measured memory_bytes: 256
#if 0



#endif // 0

#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = (int) 4e4 + 10;
const int INF = (int) 0x3f3f3f3f;
typedef long long LL;
int M,N;
int p[MAXN];
int ans;
int arr[MAXN];

struct EDGE{
    int u,v,w;
    int id;
}edges[MAXN];

bool cmp(const EDGE& a,const EDGE& b){
    return a.w<b.w;
}

int Find(int x){
    return p[x]==x ? x : p[x]=Find(p[x]);
}

int Kruskal(int day,int& cnt){
    int tot=0;
    int ret=0;
    for(int i=1;i<=N;i++)if(arr[i]>day) tot++;
//    printf("%d day islands:\n",day);
//    for(int i=1;i<=N;i++)if(arr[i]>day){
//        printf("%d ",i);
//    }
//    printf("\n");
    for(int i=0;i<M;i++){
        int u=edges[i].u;
        int v=edges[i].v;
        int w=edges[i].w;
        if(arr[u]<=day||arr[v]<=day) continue;
        int x=Find(u);
        int y=Find(v);
//        printf("u = %d , v = %d , w = %d , x = %d , y = %d\n",u,v,w,x,y);
        if(x!=y){
            cnt++;
            ret+=w;
            p[x]=y;
        }
    }
//    printf("cnt = %d , tot = %d , ret = %d\n",cnt,tot,ret);
    if(cnt+1==tot) return ret;
    return -1;
}

void work(){
    while(~scanf("%d%d",&N,&M)){
        if(N==0&&M==0) break;
        vector<int> days;
        days.clear();
        days.push_back(0);
        for(int i=1;i<=N;i++){
            int day; scanf("%d",&day);
            arr[i]=day;
            days.push_back(day);
        }
        for(int i=0;i<M;i++){
            scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);
            edges[i].id=i;
        }
        sort(edges,edges+M,cmp);
        sort(days.begin(),days.end());
        for(int i=1;i<=N;i++) p[i]=i;
        ans=0;
        int cnt=0;
        for(int i=days.size()-1;i>=0;i--){
            if(i>0&&days[i]==days[i-1]) continue;
            int add=Kruskal(days[i],cnt);
            if(add==-1) {
                ans=0;
                cnt=0;
                for(int j=1;j<=N;j++) p[j]=j;
            }
            else ans+=add;
        }
        printf("%d\n",ans);
    }
}

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




Measured memory_bytes: 3556
def XOR_sum(n):
    m = n + 1
    if m % 4 == 0:
        return 0
    elif m % 4 == 1:
        return n
    elif m % 4 == 2:
        return 1
    else:
        return n ^ 1

A, B = map(int, input().split())

print(XOR_sum(A - 1) ^ XOR_sum(B))

Measured memory_bytes: 2940
#include"bits/stdc++.h"
//#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define print(x) cout<<x<<endl;
typedef long long ll;
const int mod = 1e9 + 7;

map<ll, ll> M;

ll solve(ll n) {
	if (M[n]) return M[n];
	return M[n] = ((solve(n / 2) + solve((n - 1) / 2)) % mod + solve((n - 2) / 2)) % mod;
}

int main() {
	ll n;
	cin >> n;
	M[0] = 1;
	M[1] = 2;
	print(solve(n));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int wei[105], val[105];
ll dp[105][100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, w;
	cin >> n >> w;
	for (int i = 1; i <= n; ++i) 
		cin >> wei[i] >> val[i];
	for (int i = 1; i <= w; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i - wei[j] < 0) {
				dp[j][i] = dp[j - 1][i];
				continue;
			}
			dp[j][i] = max(dp[j - 1][i - wei[j]] + val[j], dp[j - 1][i]);
		}
	}
	cout << dp[n][w] << '\n';
	return 0;
}

Measured memory_bytes: 79360
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;

template<class T>
vector<int> convex(vector<T> x, vector<T> y)
{
    int n = (int)x.size();
    vector<pair<pair<T,T>, int>> Pt(n);
    for (int i=0; i<n; i++)
        Pt[i] = make_pair(make_pair(x[i], y[i]), i);
    sort(Pt.begin(), Pt.end());
    vector<int> P(n);
    for (int i=0; i<n; i++)
        P[i] = Pt[i].second;

    vector<int> ans;
    ans.push_back(P[0]);
    ans.push_back(P[1]);
    for (int i=2; i<n; i++)
    {
        while ((int)ans.size()>=2)
        {
            int t = (int)ans.size();
            T p = (x[P[i]]-x[ans[t-1]])*(y[ans[t-1]]-y[ans[t-2]])
                - (x[ans[t-1]]-x[ans[t-2]])*(y[P[i]]-y[ans[t-1]]);
            if (p < 0)
                ans.pop_back();
            else
                break;
        }
        ans.push_back(P[i]);
    }
    ans.push_back(P[n-2]);
    for (int i=n-3; i>=0; i--)
    {
        while ((int)ans.size()>=2)
        {
            int t = (int)ans.size();
            T p = (x[P[i]]-x[ans[t-1]])*(y[ans[t-1]]-y[ans[t-2]])
                - (x[ans[t-1]]-x[ans[t-2]])*(y[P[i]]-y[ans[t-1]]);
            if (p < 0)
                ans.pop_back();
            else
                break;
        }
        ans.push_back(P[i]);
    }
    ans.pop_back();
    return ans;
}

int main()
{
    int N;
    cin>>N;
    vector<double> x(N), y(N);
    for (int i=0; i<N; i++)
        cin>>x[i]>>y[i];

    vector<int> C = convex(x, y);
    //for (int c: C)
    //    cout<<c<<endl;
    int cn = (int)C.size();
    vector<double> ans(N);
    double pi = acos(-1.0);
    for (int i=0; i<cn; i++)
    {
        double x0 = x[C[(i+cn-1)%cn]] - x[C[i]];
        double y0 = y[C[(i+cn-1)%cn]] - y[C[i]];
        double x1 = x[C[(i+1)%cn]] - x[C[i]];
        double y1 = y[C[(i+1)%cn]] - y[C[i]];
        double s = acos((x0*x1+y0*y1)/hypot(x0,y0)/hypot(x1,y1));
        ans[C[i]] = (pi-s)/(2*pi);
    }
    for (double a: ans)
        printf("%.20f\n", a);
}


Measured memory_bytes: 256
#include<iostream>

int main (){
    std::cin.tie(0); 
	std::ios::sync_with_stdio(false);
    int A,B,C;std::cin >> A >> B >> C;
    int K;std::cin >> K;
    std::string ans="No";

    while (K > 0) {
        if (B <= A) {
            B *= 2;
        } else if (C <= B ) {
            C *= 2;
        }
        --K;
    }
    if (C > B && B > A) {
        ans="Yes";
    }

    std::cout << ans;
    return 0 ;
}

Measured memory_bytes: 3644
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += (s >> S * K) & mmm

print(ans % P)

Measured memory_bytes: 41708
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const int INF=1000000001;
const double PI=3.141592653589;


int main(){
  int n; cin>>n;
  ll A=0;
  ll B=0;
  vector<ll> a(n);
  rep(i,n){
    cin>>a[i];
    if(i!=0)
    B+=a[i];
  }
  A=a[0];
  ll ans=abs(A-B);
  for(int i=1;i<n-1;i++){
    A+=a[i];
    B-=a[i];
    ans=min(ans,abs(A-B));
  }
  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**6)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v] != -1:
            if color[next_v] != cur:
                continue
            else:
                return False
        elif not dfs(next_v, 1-cur):
            return False
    return True
        


N, M = map(int, input().split())
AB = [[int(_) for _ in input().split()] for _ in range(M)]
Graph = [[] for _ in range(N)]
color = [-1]*N

for i in AB:
    Graph[i[0]-1].append(i[1]-1)
    Graph[i[1]-1].append(i[0]-1)

if dfs(0, 0):
    black = color.count(0)
    white = N - black
    print(black*white-M)
else:
    print(comb(N, 2)-M)

Measured memory_bytes: 49808
while(True):
        try:
            a,b,c,d,e,f=map(float,input().split(" "))
            z=a*e-b*d
            if(z!=0):
                x=(c*e-b*f)/z
                y=(a*f-c*d)/z
            print("{:.3f} {:.3f}".format(x+0,y+0))
        except:
            break

Measured memory_bytes: 7360
from math import gcd
from collections import Counter

N = int(input())
C = Counter()
for i in range(N):
    x = round(float(input()) * 10 ** 9)
    C[gcd(x, 10**18)] += 1

ans = 0
for k1, v1 in C.items():
    for k2, v2 in C.items():
        if k1 * k2 % 10 ** 18 == 0:
            if k1 == k2:
                ans += v1 * (v1 - 1) // 2
            if k1 < k2:
                ans += v1 * v2

print(ans)

Measured memory_bytes: 9168
class SkewHeap
  def initialize(rev = nil)
    @rev = rev
  end
  def push(k)
    @root = meld(@root, Node.new(k))
  end
  def top
    @root.key
  end
  def empty?
    @root.nil?
  end
  def pop
    key = @root.key
    @root = meld(@root.lchild, @root.rchild)
    key
  end
  def meld(lhs, rhs)
    return lhs unless rhs
    return rhs unless lhs
    lhs, rhs = rhs, lhs unless lhs < rhs
    lhs, rhs = rhs, lhs if @rev
    lhs.rchild = meld(lhs.rchild, rhs)
    lhs.lchild, lhs.rchild = lhs.lchild, lhs.rchild
    lhs
  end
  class Node
    include Comparable
    attr_accessor :key, :lchild, :rchild
    def initialize(k)
      @key = k
    end
    def <=>(other)
      @key <=> other.key
    end
  end
end

N=gets.to_i
V=gets.split.map(&:to_f)

q=SkewHeap.new
V.each do |v| q.push(v) end

loop do
  a=q.pop
  if q.empty?
    p a
    exit
  end
  b=q.pop
  q.push((a+b)/2.0)
end


Measured memory_bytes: 14284
#include<iostream>
using namespace std;
int main(){
     int n;
     cin >> n;

     int Room[4][3][10] = {0};

     for(int i = 0; i < n; i++) {
         int a, b, c, num;
         cin >> a >> b >> c >> num;
         Room[a - 1][b - 1][c - 1] += num;
     }

     for(int a = 0; a < 4; a++) {
         for(int b = 0; b < 3; b++) {
             for(int c = 0; c < 10; c++) {
                 cout << " " << Room[a][b][c];
                 if(c == 9) cout << "\n";
             }
         }
         if(a != 3) cout << "####################\n";
     }
     return 0;
}

Measured memory_bytes: 3068
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;


public class Main {
	public static void main(String[] args){
		PrintWriter out = new PrintWriter(System.out);
		InputReader sc=new InputReader(System.in);
		long X=sc.nextLong();
		long money=100;
		int count=0;
		while (true) {
			money+=money*0.01;
			count++;
			if (money>=X) {
				break;
			}
		}
		System.out.println(count);
	}
	static class InputReader { 
		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;
		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}
 
		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}
 
		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}
 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
 
		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}
 
		public boolean hasNext() {
			skip();
			return hasNextByte();
		}
 
		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
 
		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}


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

using namespace std;
#define ll long long
const int mod=998244353;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,r;
    cin>>n>>r;
    cout<<r+100*(10-min(10,n))<<endl;
    return 0;
}


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


int gcd(int a,int b){
  if(b == 0){ return a;}
  return gcd(b,a%b);
}

int main(){
  int N,M;

  cin >> N >> M;

  int a[1000];

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

  }

  int count = 0;

  int g = (N * M) / gcd(N,M);
  g /= M;


  int y = 0;

  for(int x = 0; x < g; x++){
    int min = 100;
    int max = 0;

    for(y = 0; y < M; y++){
      if(a[(x*M+y)%N] < min) min = a[(x*M+y)%N];

      if(a[(x*M+y)%N] > max) max = a[(x*M+y)%N];
    }

    int num = max - min;
    count += num;
  }

  cout << count << endl;
  return 0;
}

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

ans = 0
for i in range(1, N + 1):
    total = 0
    buf = i
    for j in range(4, -1, -1):
        division, buf = divmod(buf, 10**j)
        total += division
    if total >= A:
        if total <= B:
            ans += i
print(ans)

Measured memory_bytes: 9192