akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <string>
#define SIZE 200005
#define INF 100000000000000000LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <ll,int> P;

struct edge
{
	int to,cost;
	edge(int to=0,int cost=0):to(to),cost(cost){}
};
vector <edge> vec[SIZE];
ll dist[SIZE];
ll ds[SIZE],dt[SIZE];
ll ws[SIZE],wt[SIZE];
ll way[SIZE];
int U[SIZE],V[SIZE];
ll L[SIZE];
int n,m;

void dijkstra(int v)
{
	for(int i=0;i<n;i++) dist[i]=INF;
	dist[v]=0;
	way[v]=1;
	priority_queue <P,vector <P>,greater <P> > que;
	que.push(P(0,v));
	while(!que.empty())
	{
		P p=que.top();que.pop();
		int u=p.second;
		if(dist[u]<p.first) continue;
		for(int i=0;i<vec[u].size();i++)
		{
			edge e=vec[u][i];
			if(dist[e.to]>dist[u]+e.cost)
			{
				dist[e.to]=dist[u]+e.cost;
				que.push(P(dist[e.to],e.to));
				way[e.to]=way[u];
			}
			else if(dist[e.to]==dist[u]+e.cost)
			{
				way[e.to]+=way[u];
				if(way[e.to]>=MOD) way[e.to]-=MOD;
			}
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	int s,t;
	scanf("%d %d",&s,&t);s--,t--;
	for(int i=0;i<m;i++)
	{
		int u,v,d;
		scanf("%d %d %d",&u,&v,&d);u--,v--;
		vec[u].push_back(edge(v,d));
		vec[v].push_back(edge(u,d));
		U[i]=u,V[i]=v;
		L[i]=d;
	}
	dijkstra(s);
	for(int i=0;i<n;i++) ds[i]=dist[i];
	for(int i=0;i<n;i++) ws[i]=way[i];
	dijkstra(t);
	for(int i=0;i<n;i++) dt[i]=dist[i];
	for(int i=0;i<n;i++) wt[i]=way[i];
	ll ret=ws[t]*ws[t]%MOD;
	ll mn=ds[t];
	for(int i=0;i<n;i++)
	{
		if(mn==ds[i]+dt[i]&&ds[i]==dt[i])
		{
			ret-=(ws[i]*ws[i]%MOD)*(wt[i]*wt[i]%MOD)%MOD;
			if(ret<0) ret+=MOD;
		}
	}
	//printf("%lld : %lld\n",mn,ret);
	for(int i=0;i<m;i++)
	{
		int u=U[i],v=V[i];
		if(ds[u]>ds[v]) swap(u,v);//ds[u]<ds[v]
		if(ds[u]+L[i]+dt[v]==mn)
		{
			ll a=ds[u],b=ds[u]+L[i];
			ll c=dt[v],d=dt[v]+L[i];
			if(max(a,c)<min(b,d))
			{
				ret-=(ws[u]*ws[u]%MOD)*(wt[v]*wt[v]%MOD)%MOD;
				if(ret<0) ret+=MOD;
			}
		}
	}
	printf("%lld\n",ret);
	return 0;
}


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

int main(){
  int n; cin >> n;
  vector<int> s(n);
  for(int i=0; i<n; i++) cin >> s[i];
  sort(s.begin(),s.end());
  int sum = accumulate(s.begin(),s.end(),0);
  if(sum%10==0) {
    for(int i=0; i<n; i++) {
      if(s[i]%10!=0) {
        sum -= s[i];
        break;      
      }
    }
    if(sum%10==0) sum=0;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
using namespace std;
int main()
{
	int N,f=0;
	vector<int> NN;
	cin >> N;

	for(int i=0;i<N;i++){
		int t;
		cin >> t;
		NN.push_back(t);
	}
	
	for(int i=0;i<N;i++){
		if(NN[i]!=i+1){
			f++;
		}
	}

	if(f<=2){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}

}

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


int main() {
  string s;
  cin >> s;
  if(s[0] == s[2]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

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

const int N = (int)2e5 + 9;
const int MOD = 998244353;

int tree[N * 2 + 512];

int lim;

void upd(int idx, int v){
  idx += lim;
  tree[idx] = max(tree[idx],v);
  idx /= 2;
  while(idx > 0){
    tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
    idx /= 2;
  }
}

int qry(int l, int r){
  l += lim;
  r += lim;
  int res = 0;
  while(l <= r){
    if(l % 2 == 1) res = max(res, tree[l ++ ]);
    if(r % 2 == 0) res = max(res, tree[r -- ]);
    l /= 2;
    r /= 2;
  }
  return res;
}

int nx[N];
int dp[N];

int main(){
  fastIO;
  int n;
  cin >> n;
  lim = n;
  vector<pii> dd(n);
  for(int i = 0 ; i < n; i ++ ){
    cin >> dd[i].fi >> dd[i].se;
  }
  sort(dd.begin(), dd.end());
  int id;
  for(int i = n - 1; i >= 0 ; i -- ){
    upd(i, i);
    id = lower_bound(dd.begin(), dd.end(), mp(dd[i].fi + dd[i].se, -1)) - dd.begin();
    id--;
    if(i + 1 <= id)
      upd(i, qry(i + 1, id));
  }
  dp[0]=1;
  int nx;
  for(int i = 0 ; i < n; i ++ ){
    dp[i + 1] = (dp[i] + dp[i + 1]) % MOD;
    nx = qry(i, i) + 1;
    dp[nx] = (dp[nx] + dp[i]) % MOD; 
  }
  cout << dp[n] << "\n";
  return 0;
}

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

using namespace std;

template<int MOD>
struct Modular {
  int value;
  Modular(const Modular& k) : value(k.value) {}
 
  template<typename V>
  Modular(const V& v) : value(v % MOD) {
    if (value < 0) {
      value += MOD;
    }
  }
  
  Modular() : Modular(0) {}
 
  Modular& operator+=(Modular const& b) { value += b.value; if (value >= MOD) value -= MOD; return *this; } 
  Modular& operator-=(Modular const& b) { value -= b.value; if (value < 0) value += MOD; return *this; }
  Modular& operator*=(Modular const& b) { value = (long long)value * b.value % MOD; return *this; }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { return *this += 1; }
  Modular operator--(int) { return *this -= 1; }

  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }
  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) { return os << a.value; }
  friend bool operator==(Modular const& a, Modular const& b) { return a.value == b.value; }
  friend bool operator!=(Modular const& a, Modular const& b) { return a.value != b.value; }
};
 
template <int T, typename V>
Modular<T> mexp(Modular<T> a, V e) {
  if (a == 0) return e == 0 ? 1 : 0; 
  Modular<T> res = 1; 
  while (e) { 
    if (e & 1) 
      res *= a; 
    a *= a; 
    e >>= 1; 
  }
  return res;
}

using Mint = Modular<1'000'000'007>;

void Run() {
  int k;
  string s;
  cin >> k >> s;
  int n = s.size();
  int len = n + k;
  vector<Mint> fact(len + 1);
  vector<Mint> pw(len + 1);
  vector<Mint> pw2(len + 1);
  fact[0] = pw[0] = pw2[0] = 1;
  for (int i = 1; i <= len; ++i) {
    pw[i] = 25 * pw[i - 1];
    pw2[i] = 26 * pw2[i - 1];
  }
  for (int i = 1; i <= len; ++i)
    fact[i] = i * fact[i - 1];
  auto&& Bino = [&](int a, int b) {
    return fact[a] / (fact[b] * fact[a - b]);
  };
  Mint res = 0;
  for (int i = 0; i <= len - n; ++i) {
    res += pw2[i] * Bino(len - i - 1, n - 1) * pw[len - n - i];
  }
  cout << res << '\n';
}

int main() {
  srand(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Run();
  return 0;
}

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

#define ll long long
#define ld long double
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long

using namespace std;
const int INF = 2e16;
const int MB = 20;
const int MOD = 2019;

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	vector<int> pw(n + 1);
	pw[0] = 1;
	for (int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * 10 % MOD;
	}

	vector<int> suff(n + 1);
	for (int i = n - 1; i >= 0; i--) {
		suff[i] = (suff[i + 1] + pw[n - i] * (s[i] - '0')) % MOD;
	}

	
	vector<int> a(MOD);
	int ans = 0;
	for (int i = n; i >= 0; i--) {
		ans += a[suff[i]];
		a[suff[i]]++;
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	//srand(time(0));
	int t = 1;
	//int t;
	//cin >> t;
	while (t--) solve();
}


Measured memory_bytes: 6728
//--- pB ---//
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Reader reader;
	PrintWriter out;
	public Solution() {
		reader = new Reader();
		out = new PrintWriter(System.out);
		// int t = reader.ni();
		while (reader.hasNext()) {
			run_case();
		}
		out.flush();
	}

	private void run_case() {
		int n = reader.ni();
		long res = 0;
		for (int i=1; i<=n; i++) {
			if (i % 3 == 0 || i % 5 == 0) continue;
			res += i;
		}
		System.out.println(res);
		return;
	}
}


class Reader {
	BufferedReader br;
	StringTokenizer st;
	public Reader(){
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	public String next() {
		if (st.hasMoreTokens()) return st.nextToken();
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return st.nextToken();
	}
	public boolean hasNext() {
		try {
			if (!st.hasMoreTokens() && !br.ready()) return false;
			else return true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}
	public int ni() {return Integer.parseInt(this.next());}
	public long nl() {return Long.parseLong(this.next());}
	public String ns() {return this.next();}
}


Measured memory_bytes: 32876
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;

int main(){
	IOS;
	ll n, A, B;
	cin >> n >> A >> B;
	ll x = abs(A - B);
	if (x % 2 == 1) cout << "Borys";
	else cout << "Alice";
	
	
	
	
	
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, ans = -1;
    map<int, int> mp;
    rep(i, 0, 3){
        cin >> a;
        mp[a]++;
    }
    for(auto it = mp.begin(); it != mp.end(); it++){
        if(it -> second == 1) ans = it -> first;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<bitset>
#include<unordered_map> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include "boost/algorithm/string.hpp"
#define fio ios_base::sync_with_stdio(false)
#define mod 1000000007
#define mod1 mod
#define mod2 100000009
#define li long long int
#define ll li
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define readi(x) scanf("%d",&x)
#define  reads(x)  scanf("%s", x)
#define readl(x) scanf("%I64d",&x)
#define rep(i,n) for(i=0;i<n;i++)
#define revp(i,n) for(i=(n-1);i>=0;i--)
#define myrep1(i,a,b) for(i=a;i<=b;i++)
#define myrep2(i,a,b) for(i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define MAXN 1000000000000000000
#define MINN -1000000000000000000
#define INTMAX 1000001000
#define pii pair<ll,ll> 
#define pdd pair<double,double>
#define pic pair<int,char>
#define N 200050
#define lgn 20
#define ddouble long double
#define minus minu
#define PI 3.1415926535
#define lgn 20
 
 
// #define INTMAX 200000000 
 
// using namespace boost;
// #define si short int
 
using namespace std;
using namespace __gnu_pbds;             
typedef priority_queue<pii, vector<pii> ,greater < pii > > min_pq;
// typedef priority_queue<pii, vector<pii> , greater<pii >  > min_pq;
ll toint(const string &s) {stringstream ss; ss << s; ll x; ss >> x; return x;}
string tostring ( ll number ){stringstream ss; ss<< number; return ss.str();}
 
// using namespace __gnu_pbds;         
// typedef priority_queue<pair<ll,char> , vector<pair<ll , char> > > max_pq;
// typedef priority_queue<pii , vector<pii > ,greater<pii > > min_pq;
typedef tree<pii , null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
// typedef priority_queue<pair < ll , pair < pii , ll > >  , vector<pair < ll , pair < pii , ll > >  > ,greater<pair < ll , pair < pii , ll > >  > > min_pq;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << std::endl;
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif
#define nn 2000005
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll ans = INT_MAX;
    ll n,t;
    cin >> n >> t;
    for ( ll i = 1; i <= n; i ++)
    {
        ll c,ti;
        cin >> c >> ti;
        if ( ti <= t )
            ans = min(ans,c);
    }
    if ( ans == INT_MAX )
        cout <<"TLE";
    else
        cout << ans;



}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int max = scan.nextInt();
        int range = scan.nextInt();
        int dif = 0, count = 0, sum = 0;
        
	while((sum <= range) && (count < max)){
	    count++;
	    dif = scan.nextInt();
	    sum += dif;
	}
	if(sum <= range){
	    count++;
	}
	System.out.print(count);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef long long ull;
typedef long double ld;
#define inp_arr(name,size) for(int i = 0;i<size;i++)\
cin >> name[i];
#define cepat cin.tie(0);


int main(){
    cepat

  int AC, TLE, WA, RE;
  AC = TLE = WA = RE = 0;
  int a;
  cin >> a;
  while(a--){
    string a;
    cin >> a;
    cin.ignore();
    if(a=="AC")
        AC++;
    else if(a=="TLE")
        TLE++;
    else if(a=="WA")
        WA++;
    else
        RE++;
  }
  cout << "AC x " << AC << endl << "WA x " << WA << endl << "TLE x " << TLE << endl << "RE x " << RE;


    return 0;
}








Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//STANDARD DATA TYPES
#define ll long long
#define llu unsigned long long
#define ld long double
//ADV DATA TYPES
#define pii pair < int , int >
#define pll pair < ll, ll >
#define mp make_pair
#define ff first
#define ss second
//C ++ DS
#define vi vector < int >
#define vll vector < ll >
#define pb push_back
#define pf push_front
#define iter :: iterator
#define all(x) x.begin(),x.end()

//priority_queue < pii, vector < pii >, greater < pii > > pq;
//lower_bound(v.begin(),v.end(),20);//for any sorted container
//CONSTANTS
#define MOD (1e9+7)
#define INF 0x3f3f3f3f
#define MAXN (int)(1e5+1)
//MOD OPERATIONS
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
inline ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
inline ll addmod(ll a, ll val, ll p = MOD) {{if ((a = (a + val)) >= p) a -= p;} return a;}
inline ll submod(ll a, ll val, ll p = MOD) {{if ((a = (a - val)) < 0) a += p;}return a;}
inline ll mult(ll a, ll b, ll p = MOD) {return (ll) a * b % p;}
//DEBUG
#define shout()  {cout << "I'm Here...!!!" << endl;}
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }

int main()
{
	fastio;
	ll n,k;cin>>n>>k;
	vll a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	vll dp(k+1,0),pref(k+1,1);
	dp[0]=1;
	for(int i=0;i<n;i++){
		for(int j=k;j>=0;j--){
			ll x=max(0ll,j-a[i]);
			dp[j]=submod(pref[j],x?pref[x-1]:0);
		}
		for(int j=1;j<=k;j++){
			pref[j]=addmod(dp[j],pref[j-1]);
		}
	}
	cout<<dp[k]<<endl;
		
}


Measured memory_bytes: 1792
using System;
using System.Linq;

class Program {
    static int N;
    static int[] x;
    static long[,,] dp;

    static void Main(string[] args) {
        var st = Console.ReadLine().Split().Select(int.Parse).ToArray();
        N = st[0];
        int A = st[1];
        var p = Console.ReadLine().Split().Select(int.Parse).ToArray();
        x = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = p[i];
        }

        dp = new long[N, N + 1, A * N + 1];

        //dpテーブルの全ての値を-1にしておく
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N + 1; k++) {
                for (int s = 0; s <= A * N; s++) {
                    dp[j, k, s] = -1;
                }
            }
        }

        //あらかじめ分かっている値は入力していく
        dp[0, 0, 0] = 1;
        for (int s = 0; s <= A * N; s++) {
            if (s == x[0]) {
                dp[0, 1, s] = 1;
            } else {
                dp[0, 1, s] = 0;
            }
        }

        //dpテーブルの全ての値を計算
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N + 1; k++) {
                for (int s = 0; s <= A * N; s++) {
                    dp[j, k, s] = CalculateDP(j, k, s);
                }
            }
        }

        //答えを得る
        long ans = 0;
        for (int i = 0; i <= N; i++) {
            ans += dp[N - 1, i, i * A];
        }

        Console.WriteLine(ans - 1);
    }

    static long CalculateDP(int j, int k, int s) {
        //すでにテーブルが埋まっていれば、値を返す
        if (dp[j, k, s] != -1) {
            return dp[j, k, s];
        }

        //パターン[3]
        if (j == 0 && k == 0 && s == 0) {
            dp[j, k, s] = 1;
            return dp[j, k, s];
        }

        //パターン[2]
        if (j >= 1 && k >= 1 && x[j] <= s) {
            dp[j - 1, k, s] = CalculateDP(j - 1, k, s);
            dp[j - 1, k - 1, s - x[j]] = CalculateDP(j - 1, k - 1, s - x[j]);
            dp[j, k, s] = dp[j - 1, k, s] + dp[j - 1, k - 1, s - x[j]];
            return dp[j, k, s];
        }

        //パターン[1]
        if (j >= 1) {
            dp[j, k, s] = dp[j - 1, k, s];
            return dp[j, k, s];
        }

        //パターン[4](その他)
        dp[j, k, s] = 0;
        return dp[j, k, s];
    }
}

Measured memory_bytes: 61140
def main():
    D = int(input())
    fuman = list(map(int, input().split()))
    manzoku = [[0]*26 for _ in range(D)]
    for i in range(D): manzoku[i] = list(map(int, input().split()))
    # できるだけ点数が下がらないように、満足度の高いものを選んでいく
    # d日目にテストiを受けた時、score += manzoku[d][i]-sigma[i以外25個](fuman[k]*それを受けてない日数)
    # >テストiをd日目に受ける
    # manzoku[d][i]-sigma[i以外25個](fuman[k]*それを受けてない日数)が一番大きいもの(i)を受けるそれだけ
    timepass = [0]*26
    # 最初の1日のみ指定
    x,t = 0,0
    for j in range(26):
        tmp = manzoku[i][j]
        for k in range(26):
            if not j==k: tmp -= fuman[k]*1
        if tmp>x:
            x = tmp
            t = j
    for j in range(26):
        if not j==t: timepass[j] += 1
        else: timepass[j] = 0
    print(t+1)
    for i in range(1,D):
        # greedy
        x1 = 0
        t1 = 0
        for j in range(26):
            tmp = manzoku[i][j]
            for k in range(26):
                if not j==k: tmp -= fuman[k]*timepass[k]
            if tmp>x1:
                x1 = tmp
                t1 = j

        # update timepass
        for j in range(26):
            if not j==t1: timepass[j] += 1
            else: timepass[j] = 0
        print(t1+1)



main()


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

int main() {
  char c;
  cin >> c;
  if(c == 'a'||c == 'i'||c == 'u'||c == 'e'||c == 'o')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}

Measured memory_bytes: 256
from collections import deque, Counter, defaultdict
from functools import lru_cache
from itertools import permutations
from heapq import (
    heappush,
    heappop,
    heapreplace,
    heappushpop,
    heapify,
    merge,
    nlargest,
    nsmallest,
)
from statistics import mean, median, mode


def lcm(a, b):
    p = a * b
    while b:
        a %= b
        a, b = b, a
    return p // a


n = int(input())
a = list(map(int, input().split(" ")))
alcm = a[0]
for i in a:
    alcm = lcm(alcm, i)

tot = 0
for num in a:
    tot += alcm // num

print(tot % 1000000007)


Measured memory_bytes: 6084
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
ll n,m;
ll x[300000],y[300000];
ll mod(ll x) {
	ll mod = 1e9+7;
	x %= mod;
	if(x < 0) {
		x = mod + x;
	}
	return x;
}
int main(){
	cin >> n >> m;

	REP(i,n) 
		cin >> x[i];
	REP(i,m) 
		cin >> y[i];

	ll X = 0;

	REP(i,n) {
		X += mod((-(n - (2 * i + 1))) * x[i]);
		X = mod(X);
	}

	ll Y = 0;

	REP(i,m) {
		Y += mod((-(m - (2 * i + 1))) * y[i]);
		Y = mod(Y);
	}

	cout << mod(X * Y) << endl;
	
	return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define mod (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<(x)<<endl
#define ps(x) cout<<(x);
#define pk(x) cout<<(x)<<" ";
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
#define p2d(v,n,m) rep(i,n){rep(j,m){pk(v[i][j]);}p("");}
#define fi first
#define se second
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll a[100001],b[100001],c[100001],d,n,m,x,y,z,h,w,k,sum,mi=inf,ma=-inf,ans,s,t,l,r,res,tmp,itr,p,q;
bool flag;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dx8[8]={1,1,0,-1,-1,-1,0,1},dy8[8]={0,1,1,1,0,-1,-1,-1};
char cha;
string st;
typedef map<ll, ll> imap;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<pair<ll,ll> > VP;
P pa;


ll mpow(ll x, ll y){
    //d(x)
    if(y==0) return 1;
    if(y%2==0){
        return mpow(x*x%mod,y/2)%mod;
    }
    else{
        return x*mpow(x,y-1)%mod;
    }
}

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


int main(){
    cin>>n;
    map<ll,int> L;
    rep(i,n){
        cin>>a[i];
        auto mp=prime_factor(a[i]);
        for(auto&e:mp)L[e.fi]=max(L[e.fi],e.se);
    }
    // 各Aiを素因数分解したときの素因数の数の上限の積がAi*Bi
    // vecとmapで保持
    // O(素因数*配列長)
    // Aiの素因数の数をそれぞれXの素因数の数から引く。Biをmodで直接求め、足す。累乗を高速に行う。
    ll A=1;
    for(auto&e:L)(A*=mpow(e.fi,e.se))%=mod;
    rep(i,n)(sum+=A*mpow(a[i],mod-2))%=mod;
    p(sum);
     return 0;
}


Measured memory_bytes: 896
def solve():
    H,W,K = [int(i) for i in input().split()]
    grids = []
    for i in range(H):
        row = input()
        grids.append(row)

    import itertools
    rows = list(range(H))
    row_combis = set([])
    for i in range(H+1):
        tmp = itertools.combinations(rows, i)
        row_combis |= set(tmp)
    columns = list(range(W))
    column_combis = set([])
    for i in range(W+1):
        tmp = itertools.combinations(columns, i)
        column_combis |= set(tmp)

    ans = 0
    for row_combi in row_combis:
        for column_combi in column_combis:
            num_black = 0
            for i in range(H):
                for j in range(W):
                    if i in row_combi:
                        continue
                    if j in column_combi:
                        continue
                    if grids[i][j] == '#':
                        num_black += 1
            if num_black == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    solve()

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

typedef vector<int> veci;
typedef pair<int,int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9+7)
#define fi first
#define se second
#define endl '\n'

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST    
    int tcs;
    cin >> tcs;
    while (tcs-->0)
#endif        
{
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    int best_tot=0, best_sugar=0;
    double best_ratio = -1.0;

    int na = f / a;
    int nb = f / b;
    for (int i=0; i<=na; ++i) {
        for (int j=0; j<=nb; ++j) {
            int tot_water = (i*a + j*b)*100;
            if (tot_water==0 || tot_water > f)
                continue;

            int possible_sugar = f - tot_water;
            int nc = possible_sugar / c;
            int nd = possible_sugar / d;
            for (int p=0; p<=nc; ++p) {
                for (int q=0; q<=nd; ++q) {
                    int tot_sugar = p*c + q*d;
                    if (tot_sugar>possible_sugar)
                        continue;

                    double ratio = double(tot_sugar)/tot_water;
                    if (ratio>best_ratio && ratio<=double(e)/100.0) {
                        best_ratio = ratio;
                        best_tot = tot_water+tot_sugar;
                        best_sugar = tot_sugar;
                    }
                }
            }
        }
    }

    cout << best_tot << " " << best_sugar << endl;
}}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
ll a,b,c,d,n;
bool can=false;
int main(){
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	int i,j;
	for(i=0;i<n;++i){
		if(c*(n-1-i)-d*i<=b-a && (n-1-i)*d-c*i>=b-a){
			can=true;break ;
		}
	}
	if(can)  printf("YES\n");
	else  printf("NO\n");
	return 0;
}

Measured memory_bytes: 256
fun main(args:Array<String>):Unit {
    while(true){
        val n = readLine()!!.trim().toInt()
        if (n == 0) return
        val matrix = Array(n){readLine()!!.trim().split(' ').map(String::toInt).toIntArray()}
        val min = matrix.mapIndexed { index, ints ->
            val m = ints.min()!!
            ints.indices.filter{ints[it] == m}.map{Point(it, index)}
        }.flatten()
        val max = (0 until n).flatMap{x ->
            val m = (0 until n).map{matrix[it][x]}.max()!!
            (0 until n).filter{matrix[it][x] == m}.map{Point(x, it)}
        }
        println(min.filter{max.contains(it)}.map{matrix[it.y][it.x]}.max() ?: 0)
    }
}
data class Point(val x:Int, val y:Int)


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

int stricmp(char* ch1,char* ch2){
	int ch1_length = 0,ch2_length = 0,div;
	for(int i = 0; ch1[i] != '\0';i++) ch1_length++;
	for(int i = 0; ch2[i] != '\0';i++) ch2_length++;
	if(ch1_length != ch2_length) return -1;
	for(int i = 0; ch1[i] != '\0';i++)
	{
		div = ch1[i] -ch2[i];
		if(div != 0 && div != 32 && div != -32)
			return -1;
	}
	return 0;
}

int main(){
	char W[11],T[1001];
	int count = 0;
	scanf("%s",W);
	while(true){
		scanf("%s",T);
		if(strcmp("END_OF_TEXT",T) == 0) break;
		if(stricmp(T, W) == 0) count++;
	}
	printf("%d\n",count);
}






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

int Judge(int i,int j,int a[3],int b[3]){
    int arr[4] = {0,0,0,0};
    arr[a[i]-1]++;
    arr[a[j]-1]++;
    arr[b[i]-1]++;
    arr[b[j]-1]++;
    int result = 1;
    for (int s=0;s<4;s++){
        result *= arr[s];
    }
    return result;
}

int main() {
    int a[3],b[3];
    for (int i=0;i<3;i++){
        cin >> a[i] >> b[i];
    }
    if(Judge(0,1,a,b)+Judge(0,2,a,b)+Judge(1,2,a,b) > 0){
        cout << "YES" << endl;
    }else{
        cout << "NO"<< endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
  int n,i;
  long int a=0;
  
  scanf("%d",&n);
  
  for(i=1;i<=n;i++){
    if(i%3==0){}
    else if(i%5==0){}
    else 
      a+=i;
  }
  
  printf("%ld\n",a);
  
  return 0;
}

Measured memory_bytes: 1728
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  if (N == 1) {
    cout << 1 << endl;
    return 0;
  }
  vector<vector<char>> S(N, vector<char>(N));
  rep(i, N) rep(j, N) cin >> S[i][j];

  int answer = 0;
  rep(i, N) {
    vector<vector<char>> T(N, vector<char>(N));
    const int A = 0;
    const int B = i;
    rep(y, N) {
      rep(x, N) { T[y][x] = S[(y + A) % N][(x + B) % N]; }
    }
    bool ok = true;
    rep(y, N) {
      rep(x, N) {
        if (T[y][x] != T[x][y]) {
          ok = false;
          break;
        }
      }
      if (!ok) break;
    }
    if (ok) answer++;
  }
  cout << answer * N << endl;
  return 0;
}

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

void solve(long long N, vector<long long> A){
	ll now = 0;
	map<ll, ll> m;
	rep(i, N) {
		now += A[i];
		m[now]++;
	}
	ll res = 0;
	for (auto x : m) {
		if (x.first == 0) res += x.second+x.second*(x.second-1)/2; else res += x.second*(x.second-1)/2;
	}
	cout << res << endl;
}

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



Measured memory_bytes: 15872
#include<stdio.h>
int main(void)
{
	int a[5],s[5],d,f,g,i,j;
	while(scanf("%d %d %d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&s[1],&s[2],&s[3],&s[4])!=EOF){
	d=0;
	f=0;
	for(i=1;i<=4;i++){
		if(a[i]==s[i]){
			d++;
		}
		if(a[i]!=s[i]){
			j=1;
			while(j<5){
				if(a[i]==s[j]){
					f++;
				}
				j++;
			}
		}
	}
	printf("%d %d\n",d,f);
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
        
using namespace std;
        
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
        
#define print(a) {for(auto xxxxx : (a)) cout << xxxxx << ' '; cout << '\n';}
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
        
ll next(){ll x; cin >> x; return x;}
const int maxn = 1e3 + 5, intf = 2e9;
const ll inf = 1e18, mod = 998244353;
const ld eps = 1e-6;

const int C = 60;

void solve(){
	int n; cin >> n;
	ll k; cin >> k;
	vector < vector <int> > to(C , vector <int> (n));
	for (int i = 0; i < n; i ++){
		cin >> to[0][i];
		to[0][i]--;
	}

	for (int j = 1; j < C; j ++){
		for (int i = 0; i < n; i ++){
			to[j][i] = to[j - 1][to[j - 1][i]];
		}
	}

	int i = 0;
	for (int j = C - 1; j >= 0; j --){
		if (k >= (1LL << j)){
			k -= (1LL << j);
			i = to[j][i];
		}
	}

	cout << i + 1 << '\n';
}
    
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
            
    for (int t = 1; t--;) {
        solve();
    }
        
    return 0;
}
/*
        
        
*/

Measured memory_bytes: 50960
#include<cstdio>
#include<cstring>
using namespace std;
int a,b,a1,b1;
bool ok;
char s[55],ss[55];
int main(){
	scanf("%s%s",&s,&ss);
	a=strlen(s);b=strlen(ss);
	for(int i=0;i<a+b;++i){
		if(ok){
			printf("%c",ss[b1]);
			b1++;
			ok=0;
		}
		else{
			printf("%c",s[a1]);
			a1++;
			ok=1;
		}
	}
	return 0;
}

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

int main() {
    int N; cin >> N;
    vector<int> A(N + 1);
    vector<int> B(N);
    REP(i, 0, N + 1) cin >> A[i];
    REP(i, 0, N) cin >> B[i];

    ll ans = 0;
    REP(i, 0, N) {
        if (A[i] > B[i]) {
            ans += B[i];
        } else {
            ans += A[i];
            if (A[i + 1] + A[i] - B[i] > 0) {
                ans += (B[i] - A[i]);
                A[i + 1] -= (B[i] - A[i]);
            } else {
                ans += A[i + 1];
                A[i + 1] = 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
 
int main(void){
  int n = 0;
  int a = 0;
  int amin = 0;
  long int count = 0;
  
  scanf("%d",&n);
  while(n--){
    scanf("%d",&a);
    if(a > amin || a == 0) amin = a;
    else count += amin - a;
  }
  printf("%ld\n",count);
  return 0;
}

Measured memory_bytes: 2148
#include <iostream>

using namespace std;

int main() {
    int n;
    int x, k;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        x = i;

        if( x % 3 == 0) {
            cout << ' ' << i;
            continue;
        }    
        else if ( x % 10 == 3) {
            cout << ' ' << i; 
            continue;
        }
        for (int j = 0; j < 5; j++) {
            x /= 10;
            if ( x % 10 == 3) {
                cout << ' ' << i;
                break;
            }

        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


int main(){FIN
    ll n,k;cin>>n>>k;
    vll a(n); REP(i,n) cin>>a[i];
    vll num;
    map<ll,ll> mp;
    REP(i,n){
        mp[a[i]]++;
    }
    ll cnt=0;
    for(auto p:mp){
        cnt++;
        num.push_back(p.second);
    }
    VSORT(num);
    ll ans=0;
    REP(i, cnt - k){
        ans += num[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 19296
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep2(i, a, b) for(int i = (a); i < (b); i++)
typedef long long ll;

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

    if ((n[0] == n[1] && n[1] == n[2]) || (n[1] == n[2] && n[2] == n[3])) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
def do(level,x):
    if x<=0:
        return 0
    if level==0:
        return 1
    res=0
    x-=1
    if x>j[level-1]:
        x-=j[level-1]+1
        res+=k[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
j=[1]+[0]*50
k=[1]+[0]*50
for i in range(1,n+1):
    j[i]=j[i-1]*2+3
    k[i]=k[i-1]*2+1
res=0
print(do(n,x))

Measured memory_bytes: 38256
#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,m,c,f,pre,ans;
	map<ll,ll>mp;
	cin>>n>>pre>>m;ans=pre;
	i=f=1;mp[pre]=1;vc v;v.push_back(0);v.push_back(pre);
	while((pre*pre)%m>0&&i<n)
	{
	    //ans+=(pre*pre)%m;
	    pre=(pre*pre)%m;
	    if(mp[pre]){f=0;break;}
	    ans+=pre;
	    i++;
	    mp[pre]=i;
	    v.push_back(v[i-1]+pre);

	}
	if(!f)
	{
	    ll ind=mp[pre];
	    ll len=i-mp[pre]+1;
	    ans+=((n-i)/len)*(v[i]-v[ind-1]);
	    ll rem=(n-i)%len;
	    for(i=ind;i-ind<rem;i++)ans+=v[i]-v[i-1];
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 6748
import java.util.*

data class Data(
  val x: Long,
  val n: Long // 必要な攻撃回数
) : Comparable<Data> {
  override fun compareTo(other: Data): Int {
    if (other.x == this.x) return this.n.compareTo(other.n)
    return this.x.compareTo(other.x)
  }
}

fun main(args: Array<String>) {
  val (N, D, A) = readInts()
  val XH = (1..N).map { readLongs() }

  val queue: Queue<Data> = PriorityQueue<Data>(N)
  XH.forEach {
    queue.add(Data(x = it[0], n = (it[1] + A - 1) / A))
  }

  var cnt = 0L
  var d = 0L
  while (!queue.isEmpty()) {
    val e = queue.remove()
//    println(e)
    if (e.n < 0) {
      d += e.n
      continue
    }
    val tmp = Math.max(e.n - d, 0)
    if (tmp == 0L) continue
    cnt += tmp
    d += tmp
    queue.add(Data(x = e.x + D * 2 + 1, n = -tmp))
  }

  println(cnt)
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }
fun readLong() = readString().toLong()
fun readLongs() = readStrings().map { it.toLong() }


Measured memory_bytes: 113456
N, K = [int(elem) for elem in input().split()]

num_omotes_list = []
for i in range(1, N + 1):
    num_omotes = 0
    current_score = i
    while current_score < K:
        num_omotes += 1
        current_score *= 2
    num_omotes_list.append(num_omotes)

max_num_omotes = max(num_omotes_list)
denominator = 1 << max_num_omotes
numerator = sum(1 << (max_num_omotes - num_omotes) for num_omotes in num_omotes_list)
print(numerator / denominator / N)

Measured memory_bytes: 45680
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <deque>
using namespace std;
#define LL long long
#define ri register int
deque<int>num;
template<typename T>inline void read(T& x) {
	x = 0;
	int f = 0;
	char ch = getchar();
	for (;!isdigit(ch);ch = getchar())
		f |= (ch == '-');
	for (;isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + (ch ^ 48);
	x = f ? -x : x;
}
const int N = 100010;
LL sum,ans;
int a[N],b[N];
int n;
int main(){
	read(n);
	for(ri i = 1;i <= n;++i)
		read(a[i]);
	sort(a + 1,a + n+ 1);
	num.push_back(a[1]);
	int l = 2,r = n,tot = 0;
	while(l <= r) {
		if(r - l < 4){
			num.push_back(a[r--]);
			if(r < l) break;
			num.push_front(a[r--]);
			if(r < l) break;
			num.push_back(a[l++]);
			if(r < l) break;
			num.push_front(a[l++]);
		}
		else {
			num.push_back(a[r--]);
			num.push_front(a[r--]);
			num.push_back(a[l++]);
			num.push_front(a[l++]);
		}
	}
//	printf("%d\n",num.size());
//	for(auto it : num)
//		printf("%d ",it);
	for(int i = 0;i < num.size() - 1;++i)
		sum += abs(num[i + 1] - num[i]);
	ans = max(ans,sum);
	num.clear();
	num.push_back(a[n]);
	l = 1,r = n - 1;
	sum = 0;
	while(l <= r) {
		if(r - l < 4){
			num.push_back(a[l++]);
			if(r < l) break;
			num.push_front(a[l++]);
			if(r < l) break;
			num.push_back(a[r--]);
			if(r < l) break;
			num.push_front(a[r--]);
		}
		else {
			num.push_back(a[l++]);
			num.push_front(a[l++]);
			num.push_back(a[r--]);
			num.push_front(a[r--]);
		}
	}
	for(int i = 0;i < num.size() - 1;++i)
		sum += abs(num[i + 1] - num[i]);
	ans = max(ans,sum);
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>

using namespace std;

char s[300001];
long long b[300001];
int c[300001];
long long dp[2][3];

bool can(int x, int c) {
    return (s[x] == '?') || (s[x] == '0' + c);
}

int main() {
    int n, m = 1000000007, i, j, k, l;
    long long ans = 0;
    
    scanf("%s", s);
    
    n = strlen(s);
    
    b[0] = 1;
    for (i = 1; i <= n; i++) b[i] = b[i - 1] * 2 % m;
    
    for (i = n - 1; i >= 0; i--) {
        c[i] = c[i + 1];
        if (s[i] == '?') c[i]++;
    }
    
    for (i = 0; i < 2; i++) {
        if (can(0, i)) dp[0][i]++;
    }
    
    for (i = 1; i < n; i += 2) {
        for (j = 0; j < 2; j++) {
            for (k = 0; k < 2; k++) {
                if (!can(i, j) || !can(i + 1, k)) continue;
                
                for (l = 0; l < 3; l++) {
                    long long x = dp[0][l];
                    
                    if (x == 0) continue;
                    
                    if (l == 0) {
                        if (j == 1 && k == 1) {
                            dp[1][1] += x;
                            if (dp[1][1] >= m) dp[1][1] -= m;
                        } else {
                            dp[1][0] += x;
                            if (dp[1][0] >= m) dp[1][0] -= m;
                        }
                    } else if (l == 1) {
                        if (j == 1) {
                            ans += x * b[c[i + 2]] % m;
                            if (ans >= m) ans -= m;
                        } else if (j == 0 && k == 0) {
                            dp[1][2] += x;
                            if (dp[1][2] >= m) dp[1][2] -= m;
                        } else {
                            dp[1][1] += x;
                            if (dp[1][1] >= m) dp[1][1] -= m;
                        }
                    } else {
                        if (k == 0) {
                            dp[1][2] += x;
                            if (dp[1][2] >= m) dp[1][2] -= m;
                        } else {
                            dp[1][1] += x;
                            if (dp[1][1] >= m) dp[1][1] -= m;
                        }
                    }
                }
            }
        }
        
        for (j = 0; j < 3; j++) {
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
    }
    
    printf("%lld\n", (ans + dp[0][1]) % m);
    
    return 0;
}


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

 int main (){

	 int a, b, c, d;
	 int ans;

	 std::cin >> a >> b >> c >> d;

	 ans = std::min(b,d) - std::max(a,c);

	 if (ans < 0) {
		 std::cout << 0 << std::endl;
	 }
	 else {
		 std::cout << ans << std::endl;
	 }

	 return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 105;
char s[N];
int main() {
	ll x;
	scanf("%lld", &x);
	ll t = x / 500;
	x -= 500 * t;
	ll ans = t * 1000 + 5 * (x / 5);
	printf("%lld", ans);
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data',function(chunk){

var line = chunk.toString().split('\n');
var sec = Number(line[0]);
var hour_sec = 60*60;
var minitue_sec = 60;


 var h = Math.floor(sec / hour_sec );
  var m = Math.floor((sec % hour_sec ) / minitue_sec );
  var s = sec % hour_sec % minitue_sec ;
 
console.log(h+':'+m+':'+s);
});

Measured memory_bytes: 15536
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)



Measured memory_bytes: 186352
n = gets.chomp.split('').map(&:to_i)

if n[-1] == 2 || n[-1] == 4 || n[-1] == 5 || n[-1] == 7 || n[-1] == 9 then
  puts "hon"
elsif n[-1] == 0 || n[-1] == 1 || n[-1] == 6 || n[-1] == 8 then
  puts "pon"
  #pとputsは違う。pは"出力に""がつく。putsは""がつかない。
else
  puts "bon"
end



Measured memory_bytes: 14284