akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int input(int num,char c,int* flg){
	switch (c) {
		case '0':
			num=num*10;
			break;
		case '1':
			num=num*10+1;
			break;
		case '2':
			num=num*10+2;
			break;
		case '3':
			num=num*10+3;
			break;
		case '4':
			num=num*10+4;
			break;
		case '5':
			num=num*10+5;
			break;
		case '6':
			num=num*10+6;
			break;
		case '7':
			num=num*10+7;
			break;
		case '8':
			num=num*10+8;
			break;
		case '9':
			num=num*10+9;
			break;
		default:
			*flg=1;
			break;
	}	
	return num;
}
int main(){
	int i,j,k,n,w,a,b,flg=0,num[30];
	char str[6];
	for (j=0; j<30; j++) {
		num[j]=j+1;
	}
	scanf("%d",&w);
	scanf("%d",&n);
	for (k=0; k<n; k++) {
		scanf("%s",str);
		while(str[i]!=0){
			if (flg==0) {
				a=input(a,str[i],&flg);
			}else{
				b=input(b,str[i],&flg);
			}
			i++;
		}
		i=num[a-1];
		num[a-1]=num[b-1];
		num[b-1]=i;
		for (j=0;j<=6;j++) {
			str[j]=0;
		}
		i=0;a=0;b=0;flg=0;
	}
	for (j=0; j<w; j++) {
		printf("%d\n",num[j]);
	}
	return 0;
}

Measured memory_bytes: 0
# !/usr/bin/env python
# -*- coding: utf-8 -*-
import math


def generate_prime(p_max):
    prime = [2]
    for i in range(3, p_max + 1):
        for p in prime:
            if i % p == 0:
                break
            if p > math.sqrt(i):
                prime.append(i)
                break
    return prime


def main():
    prime = generate_prime(10**5)
    prime = set(prime)
    prime2 = set()
    for p in prime:
        if p == 2:
            continue
        if (p + 1) / 2 in prime:
            prime2.add(p)
    ans = [0] * (10**5 + 1)
    for i in range(1, 10**5 + 1):
        if i in prime2:
            ans[i] = ans[i - 1] + 1
        else:
            ans[i] = ans[i - 1]

    q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(q)]
    for query in queries:
        print(ans[query[1]] - ans[query[0] - 1])


if __name__ == '__main__':
    main()


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

int main(){
  int n, k;
  
  cin >> n >> k;
  
  vector<int> vec(n);
  
  for(auto &v : vec) cin >> v;
  
  sort(vec.begin(), vec.end());
  
  int ans = 1e9;
  
  for(int i=0;i+k-1<n;i++){
    ans = min(ans, vec[i+k-1] - vec[i]);
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>
#include <array>

using namespace std;

template<typename M, typename N>
istream& operator>>(istream&is, pair<M,N> & p){is >> p.first >> p.second; return is;}
template<typename M>
istream& operator>>(istream&is, vector<M> & v){for(auto &it:v) is >> it; return is; }
template<typename M>
istream& operator>>(istream&is, vector<vector<M>> & v){for(auto &it:v) is >> it; return is; }
template<typename M, typename N>
ostream& operator<<(ostream&os, const pair<M,N> &p){os << p.fi << ' ' << p.se << '\n';return os;}
template<typename M>
ostream& operator<<(ostream&os, const vector<M> &v){for(auto it: v)os << it << ' ';cout << '\n';return os;}
template<typename M>
ostream& operator<<(ostream&os, const vector<vector<M>> &v){for(auto it: v)os << it;return os;}

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mn(x) *min_element((x).begin(),(x).end())
#define mx(x) *max_element((x).begin(),(x).end())
#define acc(x) accumulate((x).begin(),(x).end(),0ll)
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef  unsigned long long  ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<string> vs;

const ld pi=acos(-1);
const ll inf=(ll)1e9+10;
//const int mod=1000000007;
const int mod=998244353;

int n,m,k;
const int N=3e5+10;




int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n, m, x;
    cin >> n >> x >> m;
    if(n<2*m){
        ll st=x;
        n--;
        while(n--){
            st+=(x*x%m);
            (x*=x)%=m;
        }
        cout << st << el;
        return 0;
    }
    vb vis(m);
    vis[x]=true;
    ll last=x;
    vll tt;
    tt.pb(0);
    tt.pb(x);
    while(!vis[last*last%m]){
        (last*=last)%=m;
        tt.pb(last);
        vis[last]=true;
    }
    (last*=last)%=m;
    ll ans=0;
    for(int i=1; i<tt.size(); i++, n--){
        if(tt[i]==last){
            if(i==1)break;
            tt.erase(tt.begin()+1,tt.begin()+i);
            break;
        }
        ans+=tt[i];
    }
    for(int i=1; i<tt.size(); i++){
        tt[i]+=tt[i-1];
    }
    cout << ans+n/(tt.size()-1)*tt.back()+tt[n%(tt.size()-1)] << el;
    
    return 0;
}








Measured memory_bytes: 3820
def resolve():
    H, W, M = map(int, input().split())
    pos = []
    for _ in range(M):
        pos.append(list(map(int, input().split())))

    h_totals = [0] * (H+1)
    w_totals = [0] * (W+1)
    overlap = [set() for _ in range(H+1)]

    for ph, pw in pos:
        h_totals[ph] += 1
        w_totals[pw] += 1
        overlap[ph].add(pw)

    max_h = -1
    max_w = -1
    h_list = []
    w_list = []
    for i in range(1, H+1):
        if h_totals[i] > max_h:
            max_h = h_totals[i]
            h_list = [i]
        elif h_totals[i] == max_h:
            h_list.append(i)
    for j in range(1, W+1):
        if w_totals[j] > max_w:
            max_w = w_totals[j]
            w_list = [j]
        elif w_totals[j] == max_w:
            w_list.append(j)

    for i in h_list:
        for j in w_list:
            if j not in overlap[i]:
                print(max_h + max_w)
                return
    print(max_h + max_w - 1)

if __name__ == "__main__":
    resolve()

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 1000000000 + 7;

ll D,G;
vector<ll>p;
vector<ll>c;
map<string, ll> m;

void solve(string S){
  // S: i番目の数字が1なら、問題iを全て解く
  //    そのときのG点とるのに必要な問題数を、m[Sに書き込む
  if(S.size() < D){
    solve(S+"0");
    solve(S+"1");
    return;
  }

  ll ans = 0;
  ll score = 0;
  vector<pair<ll,ll>> tmp;
  for(int i = 0; i < S.size(); i++){
    if(S[i] == '1'){
      score += p.at(i) * 100 * (i+1) + c.at(i);
      ans += p.at(i);
    } else { 
      tmp.push_back(make_pair(i, p.at(i)));
    }
  }


  if(score >= G){
    m[S] = ans;
  } else { 
    for(int i = tmp.size()-1; i >= 0; i--){
      ll point = (tmp.at(i).first + 1) * 100;
      ll num = tmp.at(i).second;
      if(score + point*num < G){
        score += point * num;
        ans += num;
      } else { 
        while(score < G){
          score += point;
          ans += 1;
        }
        break;
      }
    }
  }


  if(score >= G){
    m[S] = ans;
  } else { 
    m[S] = 10000000000000000;
  }
}


int main(){
  cout << setprecision(10);
  cin >> D >> G;
  p.assign(D, 0);
  c.assign(D, 0);

  for(int i = 0; i < D; i++){
    ll x,y;
    cin >> x >> y;
    p.at(i) = x;
    c.at(i) = y;
  }
  solve("");
  
  ll ans = 1000000000000000000;
  for(auto x: m){
    if(x.second < ans) ans = x.second;
  }
  cout << ans << endl;

  
}


Measured memory_bytes: 384
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
map<ll, ll> mp;
ll n, k, a, b, num;
int main(void){
    // Your code here!
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        mp[a] += b;
    }
    for (int i = 1;; i++) {
        num += mp[i];
        if (num >= k) {
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 6528
def main():
    num = int(input())
    data_a = list(map(int, input().split()))
    data_a.sort()
    data_b = list(map(int, input().split()))
    data_b.sort()
    data_c = list(map(int, input().split()))
    data_c.sort()

    shita_b = [0 for i in range(num)]

    ind = 0
    for i in range(num):
        now_b = data_b[i]
        while data_c[ind] <= now_b:
            ind += 1
            if ind >= num:
                ind = num
                break
        if ind == num:
            break
        shita_b[i] = num - ind


    ans = 0
    tasu_now = sum(shita_b)
    ind = 0
    for i in range(num):
        now_a = data_a[i]
        while now_a >= data_b[ind]:
            tasu_now -= shita_b[ind]
            ind += 1
            if ind >= num:
                ind = num
                break
        if ind == num:
            break
        ans += tasu_now

    print(ans)



if __name__ == '__main__':
    main()


Measured memory_bytes: 108388
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int binpow(int a, int b) 
{
	int res=1;
	while(b)
	{
		if(b&1)	res=res*a%mod;
		a=a*a%mod;
		b/=2;	
	}
    return res;
}
signed main() {
    int n;
    cin>>n;
    // run l from 1 to 1e7
    int l=1;
    int r=1;
    int cur=1;
    int ans=0;
    while(l<1e7) {
        if(cur==n) {
            //cout<<l<<" "<<r<<endl;
            ans=(ans+1)%mod;
        }
        if(cur<=n) {
            r++;
            cur+=(int)log10(r)+1; // digit of r
        }
        if(cur>n) {
            l++;
            cur-=((int)log10(l-1)+1);
        }
    }
    //cout<<"ans = "<<ans<<endl;
    for(int dig=8 ; dig<=n ; dig++) {
        if(n%dig==0) {
            // can use all dig-digit numbers
            int cnt=n/dig;
            int up=binpow(10,dig);
            int down=binpow(10,dig-1);
            int add=(up-cnt+1)-down;
            //cout<<"digit = "<<dig<<endl;
            //cout<<"add = "<<add<<endl;
            ans=(ans+add+mod)%mod;
        }
        // dig*a+(dig+1)*b=n
        // => (dig)(a+b)=n-b
        // b%(dig)==(n)%(dig)
        int rem=(n%dig);
        if(!rem) rem=dig;
        int low=rem*(dig+1);
        int hi=dig*(dig+1); // n>dig*a because b must >0
        if(low<n) ans=(ans+(n-low-1)/hi+1)%mod;
    }
    cout<<ans;
}


Measured memory_bytes: 3976
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[202020];
long long sum[202020];
long long jud(int x,int y,int z)
{
	return abs((sum[y]-sum[x])-(sum[z]-sum[y]));
}
int main()
{
	int n,p1,p2,p3;
	long long mx,mi,ans=(long long)1e18;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sum[0]=0;
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];
	p1=1;
	p2=2;
	p3=3;
	while(p2<=n-2)
	{
		while(p1<p2-1&&jud(0,p1,p2)>jud(0,p1+1,p2))
			p1++;
		while(p3<n-1&&jud(p2,p3,n)>jud(p2,p3+1,n))
			p3++;
		mx=max(max(sum[p1],sum[p2]-sum[p1]),max(sum[p3]-sum[p2],sum[n]-sum[p3]));
		mi=min(min(sum[p1],sum[p2]-sum[p1]),min(sum[p3]-sum[p2],sum[n]-sum[p3]));
		ans=min(ans,mx-mi);
		p2++;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 2560
using System;
class ProgramA
    {
        static void Main(string[] args)
        {
            //日付を入力する
            string[] input = Console.ReadLine().Split(' ');
            int h = int.Parse(input[0]);
            int a = int.Parse(input[1]);

            //hとwの大小を比較して、おおきい方で塗っていく。割り切れるときと割り切れないときで回数が違うので場合分け
            
                if(h % a == 0)
                    Console.WriteLine(h / a);
                else
                    Console.WriteLine(h / a + 1);
            
            
        }
    }

Measured memory_bytes: 13140
macro_rules! read_line_to_tuple {
    ( $( $t:ty ),* ) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let mut iter = input.split_whitespace();
        ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* )
    }};
}

struct Dsu {
    n: usize,
    parent_or_size: Vec<usize>,
}

impl Dsu {
    fn new(n: usize) -> Dsu {
        Dsu { n, parent_or_size: vec![!1; n] }
    }

    fn merge(&mut self, a: usize, b: usize) -> usize {
        let (mut x, mut y) = (self.leader(a), self.leader(b));
        if x == y { return x; }
        if !self.parent_or_size[x] < !self.parent_or_size[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.parent_or_size[x] -= !self.parent_or_size[y];
        self.parent_or_size[y] = x;
        x
    }

    fn leader(&mut self, a: usize) -> usize {
        if self.parent_or_size[a] >= self.n { return a; }
        self.parent_or_size[a] = self.leader(self.parent_or_size[a]);
        self.parent_or_size[a]
    }

    fn size(&mut self, a: usize) -> usize {
        let x = self.leader(a);
        !self.parent_or_size[x]
    }
}

use std::collections::BTreeSet;

fn main() {
    let n = read_line_to_tuple!(usize);

    let mut v = Vec::with_capacity(n);
    for i in 0..n {
        let (x, y) = read_line_to_tuple!(usize, usize);
        v.push((x, y, i));
    }

    let mut dsu = Dsu::new(n);

    v.sort();
    let mut set = BTreeSet::new();
    for i in 0..n {
        if let Some(&(_, j)) = set.range(..(v[i].1, n)).next() {
            dsu.merge(i, j);
        }
        set.insert((v[i].1, i));
    }
    
    let mut set = BTreeSet::new();
    for i in (0..n).rev() {
        if let Some(&(_, j)) = set.range((v[i].1, 0)..).next() {
            dsu.merge(i, j);
        }
        set.insert((v[i].1, i));
    }

    let mut ans = vec![0; n];
    for i in 0..n {
        ans[v[i].2] = i;
    }

    println!(
        "{}",
        ans.iter()
            .map(|&i| dsu.size(i).to_string())
            .collect::<Vec<_>>()
            .join("\n")
    );
}

Measured memory_bytes: 34784
#include<stdio.h>
int main()
{
	int i,k,n,m,a,b;
	scanf("%d%d",&a,&b); 
	if((a*b)%2==0)
	{
		printf("Even");
	}
	else if((a*b)%2!=0)
	{
		printf("Odd");
	}
	return 0;
 }

Measured memory_bytes: 128
#!/usr/bin/env python3

N,A,B= [int(x) for x in input().split(" ")]
S = input()

p = 0
p_b = 0
for i, x in enumerate(S):
    if x == 'a':
        if p < A + B:
            p += 1
            print("Yes")
        else:
            print("No")
    elif x == 'b':
        p_b += 1
        if p < A + B and p_b <= B:
            p += 1
            print("Yes")
        else:
            print("No")
    else:
        print("No")
    


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
typedef double DOUBLE;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll LL_INF = 1e17 + 10;
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

string s[MAXN];
int t[MAXN];

void solve(){
	int n;
	cin >> n;
	REP(i, 0, n) {
		cin >> s[i] >> t[i];
	}
	string x;
	cin >> x;
	REP(i, 0, n) {
		if (s[i] == x) {
			int ans = 0;
			REP(j, i + 1, n) {
				ans += t[j];
			}
			cout << ans << endl;
		}
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rip(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main()
{ ios_base::sync_with_stdio(0);
cin.tie(0);
 int w ,s;
 cin >> s >> w;
  if(w>=s)
  {cout << "unsafe" <<endl;}
 else
 {cout << "safe" << endl;}
   return 0;
 }

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n;
	int a[200];
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	int i;
	for (i = 0;; ++i)
	{
		bool ok = 1;
		for (int j = 0; j < n; ++j)
		{
			ok *= !(a[j] % 2);
		}
		if (ok)
		{
			for (int j = 0; j < n; ++j)
			{
				a[j] /= 2;
			}
			continue;
		}
		break;
	}
	cout << i << endl;
	return 0;
}

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

Measured memory_bytes: 256
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  elsif(lc > 0)
    inputs << l.chomp.to_i
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

inputs.sort!.reverse!

# body
if $debugFlag
  p inputs
end

inputs[0] = inputs[0]/2

puts inputs.inject(:+)


Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<30)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  ll ans;
  ll A,B,C;
  cin >> A >> B >> C;
  cout << min(C,B/A) << endl;
  return 0;
}

Measured memory_bytes: 256
program synthetic_kadomatsu
  implicit none
  integer :: n, a, b, c, l(8), i, cst
  integer, parameter :: infty = 2000000000
  l = 0
  read(*,*) n, a, b, c
  do i = 1, n
    read(*,*) l(i)
  end do
  cst = 0
  call dfs(0,0,0,cst,n,a,b,c,l,1)
  write(*,'(i0)') cst
  stop
contains
  recursive subroutine dfs(x,y,z,cst,n,a,b,c,l,i)
    implicit none
    integer, intent(in) :: x, y, z, n, a, b, c, l(8), i
    integer, intent(inout) :: cst
    integer :: r1, r2, r3, r4
    if (i.gt.n) then
      cst = infty
      if (min(x,y,z).gt.0) cst = abs(x-a)+abs(y-b)+abs(z-c)-30
      return
    end if
    call dfs(x,y,z,r1,n,a,b,c,l,i+1)
    call dfs(x+l(i),y,z,r2,n,a,b,c,l,i+1)
    call dfs(x,y+l(i),z,r3,n,a,b,c,l,i+1)
    call dfs(x,y,z+l(i),r4,n,a,b,c,l,i+1)
    cst = min(r1,r2+10,r3+10,r4+10)
    return
  end subroutine dfs
end program synthetic_kadomatsu

Measured memory_bytes: 256
#include <iostream>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

bool IsPrime(int n) {
  int i;
  if (n < 2) return false;
  else if (n == 2) return true;

  if(n%2 == 0) return false;

  for (i = 3; i <= n/i; i += 2) {
    if (n % i == 0) return false;
  }
  return true;
}

int main () {
  int n, m, i, count = 0;
  cin >> n;
  rep(i,n) {
    cin >> m;
    if (IsPrime(m)) count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 1160
from heapq import heappop, heappush, heapify

class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        prev = [None for _ in range(self.n)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    prev[adj] = node
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

import sys
input = sys.stdin.readline

N, M, S, T = map(int, input().split())

E1 = []
E2 = []

for _ in range(M):
    u, v, a, b = map(int, input().split())
    E1.append((u, v, a))
    E2.append((u, v, b))
    
g1 = Graph(N, E1)
g2 = Graph(N, E2)
dist_from_s = g1.dijkstra(S - 1)
dist_from_t = g2.dijkstra(T - 1)

res = list()
tmp = 0

for i in range(N)[::-1]:
    tmp = max(tmp, 10**15 - dist_from_t[i] - dist_from_s[i])
    res.append(tmp)
    
print('\n'.join(map(str, res[::-1])))

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

int main(){
    long long A,B,N,i,max;
    cin >> A >> B >> N;
        i = N;
        if(N >= B-1) i = B-1;
        max = ((A*i)/B)-(A*(i/B));
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<iostream>
#include<list>
#include<map>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iomanip>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << x << endl;
using namespace std;

int main(){
    int time[200];
    int N, M, inp;
    int h, m;

    while(cin >> N){
        rep(i, N){
            cin >> h >> m;
            time[i] = h * 60 + m;
        }
        cin >> M;
        rep(i, M){
            cin >> h >> m;
            time[N + i] = h * 60 + m;
        }
        sort(time, time + N + M);
        rep(i, N+M){
            if(time[i] == time[i + 1]) i++;
            if(i == N + M - 1){
                cout << setfill('0');
                cout << time[i] / 60 << ":" << setw(2) << time[i] % 60;
            }else{
                cout << setfill('0');
                cout << time[i] / 60 << ":" << setw(2) << time[i] % 60 << " ";
            }
        }cout << endl;
    }
}

Measured memory_bytes: 1188
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s, ans;
    int n, i;

    cin >> s;

    n = s.size();

    for(i=0; i<n; i++){
        if(s[i] != 'B'){
            ans += s[i];
        }

        else{
            if(ans.size() >= 1){
                ans.erase(ans.size()-1, 1);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[2*n];
  for(int i=0;i<(2*n);i++)
  {
    cin>>arr[i];
  }
  sort(arr,arr+(2*n));
  long sum=0;
  for(int i=0;i<(2*n);i+=2)
  {
    sum+=arr[i];
  }
  cout<<sum<<endl;
  
}

Measured memory_bytes: 256
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,K=pin()
    X=tupin()
    Y=[]
    temp=X[0]
    ans=10000000000
    for i in range(N-K+1):
        temp=abs(X[i+K-1]-X[i])+min(abs(X[i+K-1]),abs(X[i]))
        #print((X[i+K-1],X[i]))
        ans=min(ans,temp)
    print(ans)    
#%%submit!
resolve()

Measured memory_bytes: 62576
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int INF = 1 << 30;
const int MOD = 1000000007;
const int MAX = 100000;

int main() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < s.size()/2; i++) {
		if (s[i] != s[s.size()-i-1]) {
			ans++;
		}
	}
	cout << ans << endl;
}


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

int main(){
    int L, R; cin >> L >> R;
    int l, r; l = L%2019; r= R%2019;
    if(L/2019 < R/2019){
        cout << 0 << endl;
        return 0;
    }
    //処理
    int ans=2019;
    for(int i=l; i<=r; i++){
        for(int j=i+1; j<=r; j++){
            ans = min(ans, i*j%2019);
        }
    }
    cout << ans << endl;
}

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

int main() {
  int n; cin >>n;
  int ans = 0, cnt = 0, height = 0;
  int h;
  for (int i=0; i<n; i++){
    cin >>h;
    if (h <= height){
      cnt++;
    }else{
      ans = max(ans, cnt);
      cnt = 0;
    }
    height = h;
  }
  ans = max(ans, cnt);
  
  cout <<ans;
  cout <<endl;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef vector<LL> VLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define MT(a,b,c) MP(a, MP(b, c))
#define T1 first
#define T2 second.first
#define T3 second.second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef TIII state;
int INF;
int distS[222][222];
int distL[222][222];
int z[1111];
int DP[2][222];

int main(){
	INF = 500000000;
	while(1){
		int n,m,r;
		cin>>n>>m;
		if(n==0)return 0;
		REP(i,222)REP(j,222)distS[i][j] = INF;
		REP(i,222)REP(j,222)distL[i][j] = INF;
		REP(i,m){
			int x,y,t;
			char sl;
			cin>>x>>y>>t>>sl;
			x--, y--;
			if(sl=='L')distL[y][x] = distL[x][y] = min(distL[x][y], t);
			else distS[y][x] = distS[x][y] = min(distS[x][y], t);
		}
		REP(i,n)distL[i][i] = 0;
		REP(i,n)distS[i][i] = 0;
		REP(k,n){
			REP(i,n){
				REP(j,i){
					distL[i][j] = distL[j][i] = min(distL[i][j], distL[i][k] + distL[k][j]);
					distS[i][j] = distS[j][i] = min(distS[i][j], distS[i][k] + distS[k][j]);
				}
			}
		}
		cin>>r;
		REP(i,r){
			scanf("%d", &z[i]);
			z[i]--;
		}
		REP(i,222)DP[0][i] = INF;
		DP[0][z[0]]=0;
		FOR(i,1,r){
			REP(j,222)DP[i%2][j]=INF;
			REP(j,n){
				REP(k,n){
					if(j==k)DP[i%2][k] = min(DP[i%2][k], DP[(i+1)%2][j]+distL[z[i-1]][z[i]]);
					else DP[i%2][k] = min(DP[i%2][k], DP[(i+1)%2][j]+distL[z[i-1]][j]+distS[j][k]+distL[k][z[i]]);
				}
			}
		}
		int ret=INF;
		REP(i,n)ret = min(ret, DP[(r+1)%2][i]);
		cout << ret << endl;
	}
}

Measured memory_bytes: 1636
#include <bits/stdc++.h>
        using namespace std;
		typedef long long int ll;
			int main(){
                	ll N, M;
                	cin>> N >> M;
                	priority_queue<pair<ll,ll>> pq;  
               		for(int i=0; i<N; i++){
                  		ll A, B;
                  		cin>> A >> B;
                  		pq.push(make_pair(-A,B)); 
                	}
              
              		ll counter=0;
              		ll value =0; 
              		while(counter<M){
                      ll A, B;
                      tie(A,B)= pq.top(); 
                      A=-A; 
                      pq.pop();
                      value = value + min( M-counter, B )*A;
                      counter = min(counter + B, M);
                      
                    }
              cout<< value << endl;
        	}

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

#define MAX 100005
#define NIL -1

struct Node { int p, l, r; };

Node T[MAX];
int n, D[MAX];

void print(int u) {
	int i, c;
	cout << "node " << u << ": ";
	cout << "parent = " << T[u].p << ", ";
	cout << "depth = " << D[u] << ", ";

	if (T[u].p == NIL) cout << "root, ";
	else if(T[u].l ==NIL) cout << "leaf, ";
	else cout << "internal node, ";

	cout << "[";

	for (i = 0, c = T[u].l; c != NIL; ++i, c = T[c].r) {
		if(i)cout << ", ";
		cout << c;
	}
	cout << "]" << endl;
}

void rec(int u, int p) {
	D[u] = p;
	if (T[u].r != NIL) rec(T[u].r, p);
	if (T[u].l != NIL) rec(T[u].l, p + 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) T[i].p = T[i].l = T[i].r = NIL;

	int d, v, c, l, r;
	for (int i = 0; i < n; ++i) {
		cin >> v >> d;
		for (int j = 0; j < d; ++j) {
			cin >> c;
			if (j == 0) T[v].l = c;
			else T[l].r = c;
			l = c;
			T[c].p = v;
		}
	}

	for (int i = 0; i < n; ++i) {
		if (T[i].p == NIL) r = i;
	}

	rec(r, 0);

	for (int i = 0; i < n; ++i) print(i);
	

	return 0;
}


Measured memory_bytes: 7736
N,x = map(int,input().split())
a = list(map(int,input().split()))

a.sort()


for i in range(N):
    if x<a[i]:
        print(i)
        exit()
    elif x == a[i]:
        print(i+1)
        exit()
    else:
        x = x - a[i]
    
print(N-1)
    

Measured memory_bytes: 3060
import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNext()) {
      int n = scanner.nextInt();
      if (n == 0) {
        break;
      }
      int p = 0;
      for (int ii = 0; ii < n; ii++) {
        int xyh = scanner.nextInt() + scanner.nextInt() + scanner.nextInt();
        int w = scanner.nextInt();
        if (xyh <= 60 && w <= 2) {
          p += 6;
        } else if (xyh <= 80 && w <= 5) {
          p += 8;
        } else if (xyh <= 100 && w <= 10) {
          p += 10;
        } else if (xyh <= 120 && w <= 15) {
          p += 12;
        } else if (xyh <= 140 && w <= 20) {
          p += 14;
        } else if (xyh <= 160 && w <= 25) {
          p += 16;
        }
      }
      System.out.println(p * 100);
    }
  }
}

Measured memory_bytes: 56644
#include <bits/stdc++.h>
using namespace std;
#define N 100005
char s[N];
int A[N],B[N],sum[N],Ans[N];
int main() {
	scanf("%s",s+1);
	int l = strlen(s+1);
	for(int i=1; i<=l; i++) {
		A[i] = A[i-1];
		if(s[i] == 'R') A[i] = i;
	}
	for(int i=l; i>=1; i--) {
		B[i] = B[i+1];
		if(s[i] == 'L') B[i] = i;
	}
	for(int i=1; i<=l; i++) {
		if(s[i] == 'R') {
			int x = B[i]-i;
			if(x&1) Ans[i] = B[i]-1;
			else Ans[i] = B[i];
		} else {
			int x = i-A[i]-1;
			if(x&1) Ans[i] = A[i];
			else Ans[i] = A[i]+1;
		}
	}
//	for(int i=1; i<=l; i++) cout<<Ans[i]<<" ";
//	cout<<endl;
	for(int i=1; i<=l; i++) sum[Ans[i]] ++;
	for(int i=1; i<=l; i++) printf("%d ",sum[i]);
	return 0;
}

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

const int maxn = 1e5 + 5;
char s[maxn];
int arr[maxn];
int cge[maxn];
int ans[maxn];
int tot = 0;
int n;
int even = 0, odd = 0;

int main(){
	scanf("%s",s+1);
	n = strlen(s+1);
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++) arr[i] = 1;
	for(int i=2;i<=n;i++){
		if(s[i] == 'L' && s[i-1] == 'R') cge[++ tot] = i;
	}
	cge[++ tot] = 100000005;
	for(int i=1;i<=n;i++){
		if(s[i] == 'R'){
			int t = upper_bound(cge+1,cge+tot+1,i) - cge;
			int pl = cge[t];
			if((pl-i) % 2 == 0) ans[pl] ++;
			else ans[pl-1] ++;
		}
		if(s[i] == 'L'){
			int t = upper_bound(cge+1,cge+tot+1,i) - cge;
			int pl = cge[t-1];
			if((i-pl) % 2 == 0) ans[pl] ++;
			else ans[pl-1] ++;
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}



Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	cout<<n*n<<'\n';
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <queue>


using namespace std;


static const  int N =  100;
static const  int no =  -1;

int graph[N][N] = {{}};
int d[N] = {};
int n;

void bfs(int v){
  queue<int> Q; 
  Q.push(v);

  int u;
    for(int i = 1;i <= n; i++){
      d[i] = no;
    
}
  d[v] = 0;

  while(!Q.empty()){
    u = Q.front();
    Q.pop();

    for(int i = 1;i <= n; i++){
      if(graph[u][i] == 0) continue;
      if(d[i] != no) continue;
      d[i] = d[u] +1;
      Q.push(i);
    }
  }
}


int main(){
  int u,v,k;
  //graph
  cin >> n ;

  for(int i = 0; i < n; i++){
    cin >> u >> k ;
    for(int j = 0; j < k ; j++){
      cin >> v;
      graph[u][v] = 1;
    }
  }


  bfs(1);

  for(int i = 1;i <= n; i++){
    cout << i << ' ' << d[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 50;


int main(void) {
	int N, M, P;
	cin >> N >> M >> P;

	const int NMAX = 2500;
	const int MMAX = 5000;
	int a[MMAX], b[MMAX];
	ll c[MMAX];

	for (int i = 0; i < M; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		c[i] = -c[i] + P;
	}

	ll dist[NMAX];

	for (int i = 0; i < N; ++i) {
		dist[i] = INF;
	}

	dist[0] = 0;


	for (int loop = 0; loop < N - 1; ++ loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i] - 1] == INF) continue;

			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];
			}
		}
	}

	ll ans = dist[N - 1];


	bool negative[NMAX];

	for (int i = 0; i < N; ++i) {
		negative[i] = false;
	}

	for (int loop = 0; loop < N ; ++ loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i] - 1] == INF) continue;

			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];
				negative[b[i] - 1] = true;
			}

			if (negative[a[i] - 1] == true) {
				negative[b[i] - 1] = true;
			}
		}
	}


	if (negative[N - 1])
		cout << -1 << endl;
	else
		cout << max(0LL, -ans) << endl;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
//登録しよう！→ https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define gre greater //sortを降順にする
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示

void solve(long long N, long long K, std::vector<long long> h){
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if(h[i] >= K)ans++;
  }
  cout << ans << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> h(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&h[i]);
    }
    solve(N, K, std::move(h));
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include <string>
#include <math.h>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;

int main(){
  int n; cin >>n;
  string s,t; cin >>s>>t;
  for(int i=n;i>=1;i--){
    if(s.substr(n-i,i)==t.substr(0,i)){
      cout<<2*n-i<<endl;
      return 0;
    }
  }
  cout << 2*n << endl;
}

Measured memory_bytes: 256
import heapq

#dg = 10**7#ノード数より多く取る

n,m, S = map(int,input().split()) #n:頂点数　m:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列


Cs=[]
Ds=[]
amax=0
for _ in range(m):
    u, v, a, b = map(int,input().split())
    edge[u-1].append([v-1,a,b])
    edge[v-1].append([u-1,a,b])#有向グラフの場合コメント
    amax=max(a,amax)

for _ in range(n):
    c, d = map(int,input().split())
    Cs.append(c)
    Ds.append(d)

dg=(n-1)*amax

def cut(S): 
    if S>dg:
        return dg
    else: return S

S=cut(S)

def dijkstra(start):

    #dijkstra
    # d : minimum distance from s
    d = [[10**20]*(dg+1) for _ in range(n)]
    d[start][cut(S)] = 0
    edgelist = []

    heapq.heappush(edgelist,(Ds[0], 0, cut(S+Cs[0])))

    for e in edge[start]:
        if S-e[1]>=0:
            heapq.heappush(edgelist,(e[2],e[0],S-e[1]))

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        t,ce,cs = minedge[0],minedge[1],minedge[2]
        #print(t,ce,cs)
        if  d[ce][cs]== 10**20:
            d[ce][cs] = t
            ns=cut(cs+Cs[ce])
            #print(ce,ns)
            if d[ce][ns]==10**20:
                #d[ce][ns]=t+Ds[ce]
                heapq.heappush(edgelist, (t+Ds[ce],ce,ns))

            for e in edge[ce]:
                if cs>=e[1]:
                    #print(e)
                    ne=e[0]
                    ns=cs-e[1]
                    if d[ne][ns]==10**20:
                        #print(ne)
                        heapq.heappush(edgelist, (t+e[2],ne,ns))
    return d

d=dijkstra(start=0)
for x in d[1:]:
    print(min(x))
#print(d)


Measured memory_bytes: 114312
import scala.io.Source.stdin

object Main {
  def getMax(max:Int, min:Int, list:Iterator[Int]):Int = {
    if(list.hasNext) {
      val m = list.next()
      val (x:Int,y:Int) =
        if(max < m-min) {
          if(min > m) (m-min,m) else (m-min,min)
        }
        else {
          if(min>m) (max,m) else (max,min)
        }
      getMax(x, y, list)
    }
    else { max }
  }

  def main(args: Array[String]) = {
    val list = stdin.getLines().map { _.toInt }
    val n = list.next()
    val r0 = list.next()
    val r1 = list.next()
    val max = getMax(r1 - r0, if(r0 > r1) r1 else r0, list)

    println(max)
  }
}

Measured memory_bytes: 77308
#include <iostream>
#include <cmath>
#include <vector>
#include <limits>

int main(int argc, char *argv[])
{
    int n;
    std::vector<int> p;

    std::cin >> n;

    p.reserve(n);

    for (int i = 0; i < n; i++) {
        int pi;
        std::cin >> pi;
        p.push_back(-pi);
    }

    int max = std::numeric_limits<int>::min();
    int ans = 0;

    for (int i = 0; i < n; i++) {
        if (max <= p[i]) {
            ans++;
            max = p[i];
        }
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 1024
N = int(input())
h = list(map(int,input().split()))
count = 0
def island(h):
    global count
    while 0 not in h:
        for i in range(len(h)):
            h[i] -= 1
        count += 1

def devide(h):
    h2 = []
    h3 = []
    for i in h:
        if i == 0:
            h2.append(h3)
            h3 = []
        if i != 0:
            h3.append(i)
    h2.append(h3)


    for i in h2:
        if i == []:
            continue
        else:
            island(i)
            devide(i)
            
island(h)
devide(h)
print(count)

Measured memory_bytes: 39280
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

int main()
{
  static const int N = 1000000;

  vector<int> vs;
  for (int i = 1; ; i++) {
    const int x = i*(i+1)*(i+2)/6;
    if (x >= N) {
      break;
    }
    vs.push_back(x);
  }

  vector<int> dp(N, numeric_limits<int>::max()), dp_odd(N, numeric_limits<int>::max());
  dp[0] = dp_odd[0] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < vs.size(); j++) {
      if (i + vs[j] < N) {
        dp[i+vs[j]] = min(dp[i+vs[j]], dp[i]+1);
        if (vs[j] % 2 == 1) {
          dp_odd[i+vs[j]] = min(dp_odd[i+vs[j]], dp_odd[i]+1);
        }
      } else {
        break;
      }
    }
  }

  int n;
  while (cin >> n && n != 0) {
    cout << dp[n] << ' ' << dp_odd[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 8616
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 100;
#define ll long long 

int main() {

	int n;
	scanf("%d", &n);
	int cnt1 = 0; /// can  divid by 2
	int cnt2 = 0; /// can divid by 4;
	int cnt = 0;
	int x;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);

		if (x % 4 == 0) cnt2 ++;
		else if (x % 2 == 0) cnt1++;
		else cnt++;
		
	}
	int f = 0;
	//cout << cnt << "  " << cnt1 << "  " << cnt2 << endl;
	if (cnt1 == 0) {
		if (cnt - 1 <= cnt2) f = 1;
		else f = 0;
	}
	else {
		if (cnt <= cnt2) f = 1;
		else f = 0;
	}

	if (f) puts("Yes");
	else puts("No");

	system("pause");
	return 0;
}

Measured memory_bytes: 504
n=int(input())
c=n%10
b=int(((n-c)%100)/10)
a=int(((n-b-c)%1000)/100)
x=a*100+a*10+a
if b < a:pass
elif b==a and c<b:pass
elif a==b and b==c:pass
else:x+=111
print(x)

Measured memory_bytes: 3060
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill (A (&array)[N], const T & val) {fill ((T*)array, (T*)(array+N), val);}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main () {
    int n; cin >> n;
    V<mint> dp(n+1, 0);//dp[i]:iを3以上の数列で作る方法の数
    dp[0] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 3; j <= i; j++) {//先頭j
            dp[i] += dp[i-j];
        }
    }
    cout << dp[n] << endl;

    return 0;
}

Measured memory_bytes: 3536
import java.util.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = Integer.parseInt(sc.next());
      int K = Integer.parseInt(sc.next());
      int [] array = new int[N];
      Arrays.fill(array, 0);
      int count = 0;
        for(int i = 0; i < K; i++){
            int d = Integer.parseInt(sc.next());
            for(int j = 0; j < d; j++){
                int x = Integer.parseInt(sc.next())-1;
                array[x]++;
            }
        }
 
    for(int i = 0; i < N; i++){
        if(array[i] == 0){
            count++;
        }
    }
    System.out.println(count);
    }

}


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

struct data {
  long long a, b, w;
};

long long n, t, s, e;
vector<data> edges;
vector<long long> g[100005], bf;
set<long long> st;

bool solve();

int main() {
  cin >> n >> t >> s >> e;
  --s, --e;
  edges.resize(n - 1);
  for(int i = 0; i < n - 1; ++i) {
    int a, b, w;
    cin >> a >> b >> w;
    --a, --b;
    edges[i].a = a;
    edges[i].b = b;
    edges[i].w = w;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if(solve())
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}
bool solve() {
  queue<int> qu;
  bf.assign(n, -1);
  bf[s] = s;
  qu.push(s);
  while(qu.size() > 0) {
    int now = qu.front();
    qu.pop();
    for(int i = 0; i < g[now].size(); ++i) {
      int nextp = g[now][i];
      if(bf[nextp] < 0) {
        bf[nextp] = now;
        qu.push(nextp);
      }
    }
  }
  for(int v = bf[e]; v != s; v = bf[v]) st.insert(v);
  if(s != e) st.insert(s);
  for(int i = 0; i < n - 1; ++i) {
    if(st.find(edges[i].a) != st.end())
      edges[i].w -=
          t * ((long long)g[edges[i].a].size() - 1);
    else
      edges[i].w -= t * (long long)g[edges[i].a].size();
    if(edges[i].w <= 0) return 0;
  }
  return 1;
}


Measured memory_bytes: 13048
#include "bits/stdc++.h"
#include <unordered_set>

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

const int INF = 1000000000;
const double PI = 3.1415926535897932384626433832795;

// N, E, S, W
const int dx[4] = { 1, 0, -1, 0};
const int dy[4] = { 0, 1, 0, -1};

using LL = long long int;
using LD = long double;
using pii = pair<int, int>;
using pdd = pair<double, double>;
using pll = pair<LL, LL>;
using vi = vector<int>;
using vd = vector<double>;
using vll = vector<LL>;
using vs = vector<string>;
using vvi = vector<vi>;

//==============================================

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

	int n, k, x, y;
	cin >> n >> k >> x >> y;


	int ans = 0;
	if (n <= k) {
		ans += x * n;
	} else {
		int specialDate = n - k;
		ans += x * (n - specialDate);
		ans += specialDate * y;
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
//sort(a, a + d, greater<int>());

using ll = long long;
using namespace std;


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

	if (n == 1 && m == 1) cout << 1;
	else if ((n == 1 && m != 1) || (m == 1 && n != 1)) cout << max(m - 2, n - 2);
	else cout << (m - 2)*(n - 2);
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;


signed main() {
  ll N, s=0;
  cin >> N;
  for (ll i=1; i<=N; i++) {
    if (i % 3 == 0) continue;
    if (i % 5 == 0) continue;
    s += i;
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3644