akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
	int N; cin >> N;
	for (int i = 0; i <= N; i++) {
		int m = (int)((double)i * 1.08);
		if (m == N) { cout << i << endl; return 0; }
	}
	cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 256
import math

n = int(input())
cnt = 0
for i in range(0, n):
	j = int(input())
	if (1 <= j <= 3):
		continue
	if j % 2 == 0:
		cnt = cnt + 1
		continue
	k = int(math.sqrt(j))
	l = 3
	while l <= k:
		if j % l == 0:
			cnt = cnt + 1
			break
		l = l +1

print(n - cnt)



Measured memory_bytes: 5676
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

map<int, int> mp;
char s[200005], t[200005];

long long gcd(long long a, long long b) {
    while(b ^= a ^= b ^= a %= b) ;
    return a;
}

int main() {
    long long n = read(), m = read();
    long long l = n * m / gcd(n, m);
    scanf("%s%s", s + 1, t + 1);
    for (int i = 1; i <= n; ++i) {
        mp[l / n * (long long)(i - 1) + 1] = s[i] - 'a' + 1;
    }
    for (int i = 1; i <= m; ++i) {
        if (!mp[l / m * (long long)(i - 1) + 1]) continue;
        if (mp[l / m * (long long)(i - 1) + 1] != t[i] - 'a' + 1) {
            puts("-1");
            return 0;
        }
    }
    printf("%lld\n", l);
    return 0;
}


Measured memory_bytes: 8192
def main():
    """
    英小文字のみからなる文字列 S, T
    文字列 Sに対して、次の操作を何度でも行うことができます。

    操作
        2つの異なる英小文字 c1, c2を選び、
        Sに含まれる全ての 
        c1 を c2に、
        c2 を c1に、置き換える

    0回以上操作を行って、S を Tに一致させられるか判定

    1 <= |S| = |T| <= 2 * 10^5
    """
    S = input()
    T = input()

    ans = f(S, T)
    print(ans)


if False:
    import pytest

    @pytest.mark.randomize(S=str, T=str,
                           min_length=10, max_length=10,
                           str_attrs=("ascii_lowercase",))
    def test_f(S, T):
        assert f(S, T)


def f(S, T):
    """
    26文字存在しないとき
    S: abc
    T: def
        a -> d にしたい
        dbc
        dはSに存在しないので好きに変えられる, でよいか

    S: abc
    T: ddf
        a -> d: dbc
        b -> d: dが存在する
        bを存在しないものに変える: dzc, 状況は変わらない
        a,b入れ替えても意味がない
        a->x, b->x and x->b: bxc, 状況は変わらない

        割当がかぶっていると無理っぽい

    仮に3文字しか種類がない
    S: abc
    T: cab
        c->a, a->c: cba
        b->a, a->b: cab
    """
    import string
    ds = {c: set() for c in string.ascii_lowercase}
    dt = {c: set() for c in string.ascii_lowercase}
    for c1, c2 in zip(S, T):
        ds[c2].add(c1)
        dt[c1].add(c2)

    for c in string.ascii_lowercase:
        if len(ds[c]) >= 2 or len(dt[c]) >= 2:
            return "No"

    return "Yes"


if __name__ == '__main__':
    main()


Measured memory_bytes: 4160
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int ans = 0;
		ans += N/500*1000;
		N -= N/500*500;
		ans += N/5*5;
		System.out.println(ans);
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int x,t;
  cin >> x >> t;

  cout << max(x-t, 0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree < pairs ,  null_type , greater<pairs>,  rb_tree_tag ,  tree_order_statistics_node_update > 
#define ll long long
#define lld long double
#define vc vector<ll>
const ll MOD=(1e9 +7);
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
    return res;}

int main() {
	// your code goes here
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	ll t,n,i,j,k,l,c,f;
	cin>>n;
	vc a(n+1);ll sum=1000,ans=1000,temp;
	for(i=1;i<=n;i++)cin>>a[i];
	ll bal=0;
	for(i=1;i<=n;i++)
	{
	    j=i;
	    while(a[j]>=a[j+1]&&(j<n-1))j++;
	    bal=sum%a[j];k=sum/a[j];
	    //j++;
	    while((a[j]<=a[j+1])&&(j<n))
	        j++;
	    sum=bal+k*a[j];
	    i=j;
	    if(i==n)break;
	}
	cout<<sum;
	return 0;
}


Measured memory_bytes: 3612
import collections
n, p = map(int, input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
l = collections.Counter(prime_factorize(p))

ans = 1
for e in l.items():
    if (e[1] // n) >= 1:
        ans *= e[0] ** (e[1]//n)
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include<string>
#include<map>
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
void solve() {

}
int main() {
    string s,t; cin >> s >> t;
    for (int i =0 ; i < s.size(); i ++) {
        if (s[i] != t[i]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes" << endl;
}



Measured memory_bytes: 3596
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力(スペース改行関係なし)
		int a = sc.nextInt();
        int b = sc.nextInt();
		int c = sc.nextInt();
        int d = sc.nextInt();

      for(int i = 0 ; a>0 && c>0; i++){
        c -= b;
        if(c <= 0){
        	System.out.println("Yes");
          	break;
        }
        a -= d;
        if(a <= 0){
        	System.out.println("No");
          break;
        }
        
      }

	}
}

Measured memory_bytes: 35788
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include<chrono>
#include<string>

using namespace std;

#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define ins insert

/*int main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		vector<ll>v;
		ll val=-1;
		while(n--)
		{
			ll temp;
			cin>>temp;
			v.pb(temp);
		}

		ll mini=10000000;

		if(v.size()==1)
		{
			cout<<val<<endl;
			continue;
		}

		else{
		for(ll i=0;i<v.size();i++)
		{
			set<ll>s;
			ll cnt=0;
			ll j;
			for(j=i;j<v.size();j++)
			{
				auto temp=s.find(v[j]);
				if(temp==s.end())
				{
					s.insert(v[j]);
					cnt++;
				}

				else
				{
					cnt++;
					break;
				}
			}
			//cout<<cnt<<endl;

			if(cnt>1)
			mini=min(mini,cnt);

			i=j-1;
		}

			cout<<mini<<endl;
		}

	}
}*/




int main() {
	

	ios_base::sync_with_stdio(false);
	cin.tie();
	double n;
	std::vector<double>x;
	std::vector<double>y;

	cin>>n;
	for(ll i=0;i<n;i++)
	{
		double t1,t2;
		cin>>t1>>t2;
		x.pb(t1);
		y.pb(t2);
	}

	double sum=0;

	for(ll i=0;i<n;i++)
	{
		for(ll j=i+1;j<n;j++)
		{
			double val1=x[i]-x[j];
			val1=val1*val1;
			double val2=y[i]-y[j];
			val2*=val2;
			double temp=sqrt(val1+val2);
			sum+=temp;
		}
	}

	//cout<<sum<<endl;

	
	double t=2*sum;
	//cout<<t<<endl;

	t/=n;
	

	cout<<fixed<<setprecision(8)<<t;

}


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

#define INF 999999999

using namespace std;

int compare_pair(auto aaaa,auto bbbbb){
    return true;
}  

// input
int n,m;
vector<pair<int,int> > demand;

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

    cin >> n >> m;
    for(int i = 0;i< m;i++){
        int f,m;
        cin >> f >> m;
        demand.push_back(make_pair(f,m));
    }

    sort(demand.begin(),demand.end(),[](const auto& a,const auto& b){
        return a.second < b.second;
    });
    
    int ans = 1;
    int cut = demand[0].second;



    for(int i = 1;i < m;i++){
        if( demand[i].first < cut) continue;
        cut = demand[i].second;
        ans++;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 1400
package main

import (
        "fmt"
)

func hasStr(S string, str string) bool {
        return len(str) <= len(S) && S[len(S)-len(str):] == str
}

func main() {
        var S string
        fmt.Scan(&S)

        list := []string{"dream", "dreamer", "erase", "eraser"}
        for {
                tmp := S
                for _, v := range list {
                        if hasStr(S, v) {
                                S = S[:len(S)-len(v)]
                        }
                }
                if tmp == S {
                        break
                }
        }
        if len(S) == 0 {
                fmt.Println("YES")
                return
        }
        fmt.Println("NO")
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define nikal ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int d,a[n+1]={0},p,i;
    for(i=0;i<k;i++)
    {
        cin>>d;
        while(d--)
        {
            cin>>p;
            a[p]=1;
        }
    }
    p=0;
    for(i=0;i<n+1;i++)
    {
        if(a[i]==0)
            p++;
    }
    cout<<p-1<<endl;
    return 0;
}


Measured memory_bytes: 3548
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
#define MOD 1000000007
#define MAX_V 100010
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}

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

ll junnretu(ll n){
    ll ans=1;
    for (ll i=1;i<=n;i++){
        ans*=i;
    }
    return ans;
}

map<ll,ll> prime_factor(ll n){
    map<ll,ll> mp;
    for(ll i=2; i*i<=n; i++){
        while(n % i == 0){
            mp[i]++;
            n /= i;
        }
    }
    if(n != 1) mp[n] = 1;
    return mp;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    bool news[4];
    fill(news,news+4,false);
    string s;
    cin >> s;
    for (ll i=0;i<s.size();i++){
        if (s[i]=='N')news[0]=true;
        if (s[i]=='E')news[1]=true;
        if (s[i]=='W')news[2]=true;
        if (s[i]=='S')news[3]=true;
    }
    bool flag=true;
    if (news[0]){
        if (!news[3]){
            flag=false;
        }
    }else{
        if(news[3]){
            flag=false;
        }
    }
    if (news[1]){
        if (!news[2]){
            flag=false;
        }
    }else{
        if(news[2]){
            flag=false;
        }
    }
    if (flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}




Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n,i,x;
	scanf("%d",&n);
	for (i=1; i<=n; i++) {
		x = i;
		if(x%3 == 0) {
			printf(" %d",i);
		} else {
			while(x) {
				if(x%10 == 3) {
					printf(" %d",i);
					break;
				}
				x /= 10;
			}
		}
	}
	printf("\n");
	return 0;
}

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

int main(){
string A, B, C;
cin >> A >> B >> C;
if (A.at(A.size() - 1) == B.at(0) && B.at(B.size() - 1) == C.at(0)){
    cout << "YES" << endl;
}
else {
    cout << "NO" << endl;
}
}

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

if 0 in A:
    print(0)
    exit()

ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        break

if ans <= 10**18:
    print(ans)

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

#define ll long long
#define sz(x) (int)x.size();
#define go ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

int main(){
	go;
	ll n;
	cin>>n;
	string s="";
	char c[26];
	c[0]='z';
	for(int i=1;i<26;i++)c[i]=char(i-1+'a');

	while(n){
		s+=c[n%26];
		if(n%26==0)n--;
		n/=26;
	}



	reverse(s.begin(), s.end());
	cout<<s;
	
	
	
}

Measured memory_bytes: 3624
# include <cctype>
# include <cstdio>
 
int cnt [50] ;
 
int main ( )  {
		int n, m ;
		scanf ( "%d%d", & n, & m ) ;
		int sum1 = ( ( n & 1 ) & ( m & 1 ) ) ;
		int sum2 = ( m * ( n & 1 ) ) + ( n * ( m & 1 ) ) - ( sum1 << 1 ) ;
		scanf ( "%d%d", & n, & m ) ;
		for ( int i = 0 ; i < 26 ; ++ i )	cnt [i] = 0 ;
		for ( int i = 1 ; i <= n ; ++ i )
			for ( int j = 1 ; j <= m ; ++ j )  {
				int c ;
				while ( ! isalpha ( c = getchar ( ) ) ) ;
				++ cnt [c - 'a'] ;
			}
		bool ans ( 1 ) ;
		for ( int i = 0 ; i < 26 ; ++ i )  {
			if ( cnt [i] & 1 )  -- sum1 ;
			if ( cnt [i] % 4 >= 2 )  sum2 -= 2 ;
			if ( sum1 < 0 || sum2 < 0 )  {
				ans = 0 ;
				break ;
			}
		}
		puts ( ans ? "Yes" : "No" ) ;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

vector<VI> g;
int solve(int now) {
    VI a;
    each(to, g[now])a.push_back(solve(to));
    rSORT(a, greater<int>());
    int ret = 0;
    FOR(i, 0, a.size())chmax(ret, a[i] + i + 1);
    return ret;
}
int main() {
    init();

    int n; cin >> n;
    g = vec<VI>(n);
    FOR(i, 1, n) {
        int a; cin >> a;
        --a;
        g[a].push_back(i);
    }
    cout << solve(0) << "\n";
}


Measured memory_bytes: 13568
package main

import "fmt"

type i64 int64

const MOD i64 = 1000000007

var fact, invf [202020]i64

func modPow(b, n, mod i64) i64 {
	if n == 1 {
		return b
	}
	ret := modPow(b*b%mod, n/2, mod)
	if n&1 == 1 {
		ret = ret * b % mod
	}
	return ret
}

func inverce(n i64) i64 {
	return modPow(n, MOD-2, MOD)
}

func comb(n, k i64) i64 {
	if k < 0 || n < k {
		return 0
	}
	return fact[n] * invf[k] % MOD * invf[n-k] % MOD
}

func main() {
	var h, w, a, b, ans i64
	fmt.Scan(&h, &w, &a, &b)

	fact[0] = 1
	invf[0] = 1

	for i := i64(1); i <= 200020; i++ {
		fact[i] = (fact[i-1] * i) % MOD
		invf[i] = inverce(fact[i])
	}

	for i := i64(1); i <= h-a; i++ {
		ans += comb(b-1+i-1, b-1) * comb(w-b-1+h-i, h-i) % MOD
        ans %= MOD
	}
    
    fmt.Println(ans)
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll w,h,n;cin>>w>>h>>n;
    ll l=0,r=w,u=h,d=0;
    rep(i,n){
        ll x,y,a;cin>>x>>y>>a;
        if(a==1){
            l = max(l,x);
        }
        else if(a==2){
            r = min(r,x);
        }
        else if(a==3){
            d = max(d,y);
        }
        else {
            u = min(u,y);
        }
    }
    if(l >= r || d >= u)out(0);
    else out((r-l)*(u-d));
}


Measured memory_bytes: 256
n,c,k = map(int,input().split())
t = []
for i in range(n):
    x = int(input())
    t.append(x)
t.sort()

p = 0 #t[i]を処理し終えた時点で、待機してる人数
w = t[0] #t[i]を処理し終えた時点で、待機してる人の中で一番最初から待ってる人の時間

res = 0 #t[i]を処理し終えた時点で、用いたバスの数
for i in range(n):
    p += 1
    if t[i]-w > k:
        p = 1
        res += 1
        w = t[i]
        if i == n-1:
            res += 1
    elif c == p:
        p = 0
        res += 1
        if i != n-1:
            w = t[i+1]
    
    else:
        if i == n-1:
            res += 1

print(res)

Measured memory_bytes: 7488
#include<bits/stdc++.h>
using namespace std;
#define ma 3000

int dp[ma + 1][ma + 1];

string getLCS(string& x, string& y, int len)
{
	string lcss = "";
	int i = x.length();
	int j = y.length();
	while (len > 0)
	{
		if (x[i - 1] == y[j - 1])
		{
			lcss = x[i - 1] + lcss;
			i--;
			j--;
			len--;
		}
		else
		{
			if (dp[i][j - 1] > dp[i - 1][j])
			{
				j--;
			}
			else
			{
				i--;
			}
		}
	}
	return lcss;
}


int lcsTopDown(int i, int j, string& x, string& y)
{
	if (i == 0 || j == 0)
	{
		return 0;
	}
	if (dp[i][j] != -1)
	{
		return dp[i][j];
	}
	if (x[i - 1] == y[j - 1])
	{
		dp[i][j] = 1 + lcsTopDown(i - 1, j - 1, x, y);
		return dp[i][j];
	}
	else return dp[i][j] = max(lcsTopDown(i - 1, j, x, y), lcsTopDown(i, j - 1, x, y));
}

int main()
{
	memset(dp, -1, sizeof(dp));
	string a, b;
	cin >> a >> b;
	int length = lcsTopDown(a.length(), b.length(), a, b);
	cout << getLCS(a, b, length);
}


Measured memory_bytes: 39272
if isfile("mystdin.txt");mystdin=open("mystdin.txt","r");redirect_stdin(mystdin);end
pI(x)=parse(Int,x)
pM(x::Array{SubString{String},1})=map(pI,x)
function main()
  n,l=pM(split(readline()))
  s=sort([chomp(readline()) for i=1:n])
  println(*(s...))
end
main()
if isdefined(Base, :mystdin);close(mystdin);end


Measured memory_bytes: 165620
n=input()
intn=int(n)
ln=len(n)

if intn<10:
  print(n)
  quit()

def count(i,j):
  res=0
  if i==j:
    res+=1
  if ln==2:
    if 10*i+j<=intn:
      res+=1
  else:
    res+=(10**(ln-2)-1)//9
    if i<int(n[0]):
      res+=10**(ln-2)
    elif i==int(n[0]):
      tn=int(n[1:-1])
      if j<=intn%10:
        res+=tn+1
      else:
        res+=tn
  return res

res=0
for i in range(1,10):
  for j in range(1,10):
    res+=count(i,j)*count(j,i)
print(res)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	int N;
	string S;
	cin >> N;
	cin >> S;
	int sum = 0;
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		if (S[i] == 'I') {
			sum += 1;
		}
		else {
			sum -= 1;
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
ks = [list(map(int, input().split()))for i in range(M)]
p = list(map(int, input().split()))
cnt = 0
all_on = 1
ans = 0
for i in range(2**N):
    all_on = 1
    bits = "0" + str(N) + "b" 
    sw_line = str(format(i,bits))
    for j in range(M):
        for k in range(1,ks[j][0]+1):
            sw = sw_line[ks[j][k]-1]
            if(sw== "1"):
                cnt += 1
        if(cnt % 2 != p[j]):
            all_on = 0
        cnt = 0
    if(all_on == 1):
        ans += 1
print(ans)

Measured memory_bytes: 3188
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        #[allow(unused_mut)]
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i32,
        b: i32,
    };

    if a * b % 2 == 0 {
        println!("Even")
    } else {
        println!("Odd")
    }
}


Measured memory_bytes: 2092
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  string s;
  cin >> s;
  int a[3] = {0};
  a[s[0]-'a']++;
  a[s[1]-'a']++;
  a[s[2]-'a']++;

  if(a[0]==a[1] && a[1]==a[2]) print("Yes");
  else print("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()



int main() {
    ll n, a[MAX_N], b[MAX_N], as=0,bs=0;
    cin >> n;
    REP(i,n){
        cin >> a[i];
        as += a[i];
    }
    REP(i,n){
        cin >> b[i];
        bs += b[i];
    }
    if(as < bs){
        cout << -1 << endl;
    }
    else{
        ll cnt=0;
        vector<ll> v;
        REP(i,n){
            if(a[i]<b[i]){
                cnt++;
            }
            else{
                v.push_back(a[i]-b[i]);
            }
        }
        as -= bs;
        SORT(v);
        for(auto x : v){
            //cout << x << " " << as << endl;
            if(x <= as){
                as -= x;
            }
            else {
                cnt++;
            }
        }
        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 2936
#include<stdio.h>
#include<string.h>
int main() {
    char s[27],i,keep;
    int g;
    for (g = 0; g < 26; g++)
        s[g] = '\0';
    scanf("%s", s);
    int k = strlen(s),j,flag,t,u;
    if (k!=26) {
        for (i = 'a'; i <= 'z'; i++) {
            flag = 0;
            for (j = 0; j < k; j++) {
                if (s[j] == i)
                    flag = -1;
            }
            if (flag == 0) {
                s[k] = i;
                printf("%s", s);
                return 0;
            }
        }
    }
    else {
        for (j = k - 2; j >= 0; j--) {
            for (i = 'a'; i <= 'z'; i++) {
                if (i > s[j]) {
                    for (t = j + 1; t < k; t++) {
                        if (s[t] == i) {
                            s[j]=i;
                            for (t = j + 1; t < k; t++)
                                s[t] = '\0';
                            printf("%s", s);
                            return 0;
                        }
                    }
                }
            }
        }
    }
    printf("-1");
    return 0;
}

Measured memory_bytes: 128
import Control.Monad
import Control.Applicative
import Data.List
import qualified Data.Map as M
--import qualified Data.Vector as V
--import qualified Data.Vector.Mutable as VM

getBysplit = map read . words <$> getLine

main :: IO()
main = do
  n <- readLn :: IO Int
  v <- getBysplit :: IO [Int]
  c <- getBysplit :: IO [Int]
  let lst = (map (\(x, y) -> if x - y > 0 then x - y else 0) . zip v) c
  let ans = sum lst
  print $ ans


Measured memory_bytes: 636
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
	int n, k;
  	cin >> n >> k;
 	vi x(n);	
  	rep(i,n) cin >> x[i];
	int ans = 0;
  	rep(i,n) ans += 2*min(x[i], abs(k-x[i]));
	cout << ans << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using tiii = tuple<int,int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const ll DIV =1e9+7;
//const double PI = M_PI;
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
#define chmax(a,b) a=max(a,b)

/*Coding Space*/
int main(){
  int m1,d1,m2,d2; cin >> m1 >> d1 >> m2 >> d2;
  cout << int(m1 != m2) << endl;
}


Measured memory_bytes: 256
n=int(input())
a=[0]*4
b=["AC","WA","TLE","RE"]
for i in range(n):
    s=input()
    for j in range(4):
        if s == b[j]:
            a[j]+=1
for i in range(4):
    print(b[i]+" x "+str(a[i]))

Measured memory_bytes: 9116
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
using ll = long long; using ld = long double; const char nl = '\n';
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */

#include <bits/extc++.h>
namespace pbds =  __gnu_pbds;
template <typename key, typename val=pbds::null_type, typename comp=less<key>>
using ostree=pbds::tree<key,val,comp,pbds::rb_tree_tag,pbds::tree_order_statistics_node_update>;
using vi = vector< int >; using vll = vector< ll >;
#define all(x) std::begin(x), std::end(x)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&);
string to_string(string const&s){return '"'+s+'"';}
string to_string(char const &c) {return to_string(string(1,c));}
string to_string(char const *c) {return to_string(string(c));}
string to_string(bool const &b) {return (b ? "1" : "0");}
template<typename... Args> string to_string(pair<Args...> const&p)
{return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&S)
{string s = "{"; for(auto const& e: S)s+=" "+to_string(e);s+=" }"; return s;}
template<typename Tail> void debug_out(Tail t) {cerr<<" "<<to_string(t)<<" ]"<<endl;}
template<typename Head, typename... Tail> void debug_out(Head h, Tail... t)
{cerr << " " << to_string(h) << ","; debug_out(t...);}
#define pr(...) cerr<<"["<<(#__VA_ARGS__)<<"] : [", debug_out(__VA_ARGS__)
template <typename T> void dbr(T lb, T ub)
{cerr<<'{';for(auto it=lb; it!=ub; it++)cerr<<' '<<to_string(*it); cerr<<" }"<<endl;}
template<typename T, typename Comp=less<T>> bool smin(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(v, mem) ? mem = v, true : false;}
template<typename T, typename Comp=less<T>> bool smax(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(mem, v) ? mem = v, true : false;}
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */



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

  ll a, b, c, d, cd;
  cin >> a >> b >> c >> d;
  cd = c*d / __gcd(c,d);

  ll C = (b / c) - ((a-1) / c);
  ll D = (b / d) - ((a-1) / d);

  ll CD = (b / cd) - ((a-1) / cd);

  ll tot = (b-a+1);
  cout << (tot - (C+D-CD)) << endl;

}
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
vector<ll> adj[N];
ll val[N];
ll res[N];

void dfs(ll curr, ll prev1 = -1, ll sum1 = 0) {
  res[curr] = sum1 + val[curr];
  for (ll x : adj[curr]) {
    if (x != prev1) {
      dfs(x, curr, sum1 + val[curr]);
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s, t;
  cin >> s >> t;

  ll n = s.length();
  ll nxt[n + 5][30];
  memset(nxt, -1, sizeof(nxt));
  for (ll i = 0; i < 26; i++) {
    ll indx = -1;
    for (ll j = 0; j < n; j++) {
      if ((s[j] - 'a') == i) {
        indx = j;
        break;
      }
    }
    if (indx == -1) {
      continue;
    }

    nxt[n][i] = indx;
    for (ll j = n - 1; j >= 0; j--) {
      if ((s[j] - 'a') == i)
        nxt[j][i] = j;
      else
        nxt[j][i] = nxt[j + 1][i];
    }
  }

  ll indx = 0;
  ll noMod = 0;

  ll n1 = t.length();
  for (ll i = 0; i < n1; i++) {
    ll curr = t[i] - 'a';

    if (nxt[indx][curr] == -1) {
      cout << -1 << en;
      return 0;
    }

    if (nxt[indx][curr] >= indx) {
      noMod += nxt[indx][curr] - indx;
    } else {
      noMod += n - (indx - nxt[indx][curr]);
    }

    indx = nxt[indx][curr];
    // cout << i << " " << indx << " " << noMod << en;
    if (i == (n1 - 1))
      break;

    indx = (indx + 1) % n;
    noMod++;
  }

  cout << noMod + 1 << en;

  return 0;
}

Measured memory_bytes: 29776
# 最後に残るのは奇数回登場したやつ
n = int(input())
hash = dict()
for _ in range(n):
    x = int(input())
    if x in hash:
        hash[x] += 1
    else:
        hash[x] = 1

ans = 0
for _, v in hash.items():
    if v % 2 == 1:
        ans += 1
print(ans)


Measured memory_bytes: 53848
#include <bits/stdc++.h>
typedef long long int lli;
using namespace std;
#define MOD 1000000007
#define MAX 500005
lli p[MAX];
lli arr[MAX];
bool square[100000];
lli n;
lli a,b;
bool check(lli a,lli b, lli c){
    if((a-b+c)%2 == 0 && (c+b-a)%2 == 0 && (a+b-c)%2 == 0){
        if((a-b+c)/2 >= 1 && (c+b-a)/2 >=1 && (a+b-c)/2 >= 1)
            return true;
    }
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n;
    cin>>n;
    for(lli i = 1; i<=n; i++){
        if(i*i < 1e5)
            square[i*i] = true;
        else{
            break;
        }
    }
    lli ans = 0;
    for(lli N = 1; N<=n; N++){
        ans = 0;
        for(int i = 1; (i*i)<=(2*N); i++){
            for(int j = 1; (j*j) <=(2*N); j++){
                if(((2*N -i*i - j*j) >= 0) && square[2*N-i*i-j*j]){
                    if(check(i,j,(long long)sqrt(2*N-i*i-j*j)))
                    ans++;
                }  
            }
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#include<unistd.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    string A;cin>>A;
    ll N=A.size();
    ll ans=N*(N-1)/2+1;
    ll i=0,j=0;
    map<char,ll> mp;
    // while(i<N){
    //     while(j<N && A[j]==A[i]){
    //         ++j;
    //     }
    //     ll n=j-i;
    //     if(i>0&&j<N-1&&A[i-1]==A[j+1]){
    //         ans -= n;
    //     }
    //     i=j;
    // }
    REP(i,N) mp[A[i]]++;
    for(auto e:mp){
        ans-=e.second*(e.second-1)/2;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(){
	int n,i,m,d[8];
	for(;scanf("%d",&n)&&n;){
		for(i=0;i<7;i++)d[i]=0;
		for(;n>0;n--){
			scanf("%d",&m);
			if(m<10)d[0]++;
			else if(m<20)d[1]++;
			else if(m<30)d[2]++;
			else if(m<40)d[3]++;
			else if(m<50)d[4]++;
			else if(m<60)d[5]++;
			else d[6]++;
		}
		for(i=0;i<7;i++)printf("%d\n",d[i]);
	}return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

template<int MAX_V>
class graph{
    struct edge{
        int to, cap;
        int rev;
    };
    vector<edge> edges[MAX_V];
    int level[MAX_V];
    int next[MAX_V];

    void set_level(int s){
        memset(level, -1, sizeof(level));
        queue<int> Q;
        level[s] = 0;
        Q.push(s);
        while(!Q.empty()){
            int v = Q.front();
            Q.pop();
            for(edge e:edges[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    Q.push(e.to);
                }
            }
        }
    }

    int blockingflow(int v, int t, int f){
        if(v == t) return f;
        for(int &i = next[v];i<edges[v].size();i++){
            edge &e = edges[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = blockingflow(e.to, t, min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    edges[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
public:
    void add_edge(int from, int to, int cap){
        edges[from].push_back({to, cap, (int)edges[to].size()});
        edges[to].push_back({from, 0, (int)edges[from].size()-1});
    }

    int max_flow(int s, int t){
        int flow = 0;
        while(true){
            set_level(s);
            if(level[t] < 0) return flow;
            memset(next, 0, sizeof(next));
            int f;
            while((f = blockingflow(s, t, INT32_MAX)) > 0) flow += f;
        }
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    graph<100> G;
    int V, E;
    cin >> V >> E;
    for(int i=0;i<E;i++){
        int u, v, c;
        cin >> u >> v >> c;
        G.add_edge(u, v, c);
    }

    cout << G.max_flow(0, V-1) << endl;
    
    return 0;
}


Measured memory_bytes: 3252
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int ans = 0;
    int sum = 0;
    for(int i = 1; i < 1000000; i++) {
      sum += i;
      if(X <= sum) {
        ans = i;
        break;
      }
    }
    System.out.println(ans);
  }
}

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

// iterator
#define REP(i,from, to) for(lli i=from;i<to;i++)
#define REPE(i,from, to) for(lli i=from;i<=to;i++)
#define REP_R(i,from, to) for(lli i=from;i>to;i--)
#define REPE_R(i,from, to) for(lli i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;

// dp[i][j] := i人目までで j 個残っているときの通り数の累積和
// dp[1][0] = min(a[1], 1)          # 0
// dp[1][1] = min(a[1], 2)          # 0
// dp[1][2] = min(a[1], 3)          # 0
// dp[1][3] = min(a[1], 4)          # 1
// dp[1][4] = min(a[1], 5)          # 2
//
// dp[2][0] = dp[1][2] - dp[1][-1]  # 0
// dp[2][1] = dp[1][3] - dp[1][0]   # 0
// dp[2][2] = dp[1][4] - dp[1][1]   # 2
// dp[2][3] = dp[1][4] - dp[1][2]   # 2
// dp[2][4] = dp[1][4] - dp[1][3]   # 1
//
// dp[3][0] = dp[2][3]              # 2
// dp[3][1] = dp[2][4] - dp[2][0]   # 1
// dp[3][2] = dp[2][4] - dp[2][1]   # 1
// dp[3][3] = dp[2][4] - dp[2][2]   # -1
// dp[3][4] = dp[2][4] - dp[2][3]   # -1
unsigned long long int dp[101][100001];
int main() {
    lli n, k;
    cin2(n, k);
    lli a[n+1] = {0};
    REP(i,0,n) {
        cin >> a[i+1];
    }

    REPE(j,0,k) {
        if (j >= k - a[1]) {
            if (j == 0)
                dp[1][j] = 1;
            else
                dp[1][j] = dp[1][j-1] + 1;
        }
        //cout1(dp[1][j]);
    }
    REPE(i,2,n) {
        REPE(j,0,k) {
            if (j == 0) {
                dp[i][j] = dp[i-1][min(j+a[i], k)];
            }
            else {
                dp[i][j] = (dp[i][j-1] + ((dp[i-1][min(j+a[i],k)]+1000000007 - dp[i-1][j-1]) % 1000000007)) % 1000000007;
            }
            //cout3(i,j,dp[i][j])
        }
    }
    cout << dp[n][0] << endl;
}


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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


int main(){
  int x1, y1, x2, y2;
  cin >> x1>> y1>> x2>> y2;

  int a = x2 - x1;
  int b = y2 - y1;

  int x3 = x2 - b;
  int y3 = y2 + a;
  int x4 = x3 - a;
  int y4 = y3 - b;
  cout << x3 << " " << y3 << " ";
  cout << x4 << " " << y4 << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
/*
	1.用NIL结点来表示特殊结点
	2.中序 ： 前 中 右
	3.前序： 中 左 右
	4.当删除元素时，若该元素还有子结点要把该子结点指向的父节点改变。
	5.
	*/
struct Tree
{
	int key;
	Tree* parent, * left, * right;
};
Tree* root, * NIL;
Tree* search(Tree* m) {
	Tree* k = m->right;
	while (k->left != NIL)
	{
		k = k->left;
	}
	return k;
}
void delete2(int key,Tree *m) {
	Tree* b = m;
	while (b != NIL)
	{
		if (b->key == key) break;
		else if (b->key > key) b = b->left;
		else
		{
			b = b->right;
		}
	}
	if (b->left == NIL && b->right == NIL) {
		if (b->parent->left == b) b->parent->left = NIL;
		else b->parent->right = NIL;
	}
	else if (b->left == NIL ) {
		if (b->parent->left == b) {
			b->parent->left = b->right;
			b->right->parent = b->parent;
		}
		else {
			b->parent->right = b->right;
			b->right->parent = b->parent;
		}
	}
	else if (b->right == NIL) {
		if (b->parent->left == b) {
			b->parent->left = b->left;
			b->left->parent = b->parent;
		}
		else {
			b->parent->right = b->left;
			b->left->parent = b->parent;
		}

	}
	else {
		Tree* t = search(b);
		delete2(t->key, t);
		b->key = t->key;
	}
}

int find(int key) {
	Tree* b = root;
	while (b != NIL)
	{
		if (b->key == key) return 1;
		else if (b->key > key) b = b->left;
		else
		{
			b = b->right;
		}
	}
	return 0;
}

void insert(Tree* k) {
	Tree* d = root;
	Tree* m = d;
	while (d != NIL)
	{
		m = d;
		if (k->key > d->key) {
			d = d->right;
		}
		else {
			d = d->left;
		}
	}
	k->parent = m;
	if (k->key > m->key) {
		m->right = k;
	}
	else {
		m->left = k;
	}
}
void midle(Tree* t) {
	if (t == NIL) return;
	midle(t->left);
	cout << " " << t->key;
	midle(t->right);
}
void pre(Tree* t) {
	if (t == NIL) return;
	cout << " " << t->key;
	pre(t->left);
	pre(t->right);
}
int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string m;
		cin >> m;
		if (m == "insert") {
			int key;
			cin >> key;
			Tree* k = new Tree();
			k->left = NIL;
			k->right = NIL;
			k->key = key;
			k->parent = NIL;
			if (root == NULL) {
				root = k;
			}
			else {
				insert(k);
			}
		}
		else if (m == "print") {
			midle(root);
			cout << endl;
			pre(root);
			cout << endl;
		}
		else if(m == "find"){
			int n;
			cin >> n;
			if (find(n))cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else {
			int n;
			cin >> n;
			delete2(n,root);
		}
	}
	return 0;
}


Measured memory_bytes: 21848
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
# visited = {}
visited = [[float("inf") for _ in range(W)] for _ in range(H)]
# visited[(cx, cy)] = 0
visited[cy][cx] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    # if (x, y) in visited and visited[(x, y)] < c:
    if visited[y][x] < c:
        # print("here1")
        continue
    # print(x, y, c, d, e)
    # for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
            if visited[ny][nx] <= c:
                # print("here2")
                continue
            # visited[(nx, ny)] = c
            visited[ny][nx] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                if visited[ny][nx] < c + 1:
                    # print("here3")
                    continue
                # visited[(nx, ny)] = c + 1
                visited[ny][nx] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))
# print(visited)
if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Measured memory_bytes: 222576
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        a = [c for c in S()]
        l = len(a)
        s = I()
        t = int(a[0])
        for i in range(len(a)//2):
            if a[i*2+1] == '+':
                t += int(a[i*2+2])
            else:
                t *= int(a[i*2+2])
        u = eval(''.join(a))
        r = 'I'
        if s == u:
            if s == t:
                r = 'U'
            else:
                r = 'M'
        elif s == t:
            r = 'L'

        rr.append(r)
        break


    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9032
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) v.begin(), v.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int a; cin >> a;
  vector<int > v(a);
  rep(i, a) cin >> v[i];
  sort(All(v));
  cout << v[a-1]-v[0] << endl;
  system("pause");
}

Measured memory_bytes: 504