akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
long double dp[3000][3000];
#define MOD 1000000007
long double probHeads(vector<double>&v,int n,int H){
  if(n==0 && H>v.size()/2)
   return 1;
  if(n==0)
   return 0;
   if(dp[n][H]!=-1) return dp[n][H];
  return dp[n][H]=(v[n-1]*probHeads(v,n-1,H+1)+(1-v[n-1])*probHeads(v,n-1,H));  
}
int main()
{  ios::sync_with_stdio(false);
   cin.tie(0);  
   int n;
   cin>>n;
   vector<double>v(n);
   for(int i=0;i<n;i++) cin>>v[i];
   for(int i=0;i<=n;i++){
     for(int j=0;j<=n;j++){
        dp[i][j]=-1;
     }
   }
   cout<<setprecision(10);
   cout<<probHeads(v,v.size(),0);
     return 0;
}


Measured memory_bytes: 144676
from sys import stdin, stdout
input = lambda: stdin.readline().rstrip()
println = stdout.write

def cnt(n):
    i = 0
    while 1:
        n, mod = divmod(n, 2)
        if mod:
            break
        i += 1
    return i

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    ans = 0
    for i in A:
        ans += cnt(i)
    print(ans)

main()


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

typedef long long ll;

const long long MOD = 1000000007;
long long modpow(long long a, long long n, long long m)
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = (ans * a) % m;
        }
        a = (a * a) % m;
        n >>= 1;
    }
    return ans;
}
long long combi(long long n, long long a)
{
    long long ans = 1, ans1 = 1;
    for (long long i = n - a + 1; i <= n; i++)
    {
        ans *= i % MOD;
        ans %= MOD;
    }

    for (long long i = 2; i <= a; i++)
        ans1 = (ans1 * i) % MOD;
    ans1 = modpow(ans1, MOD - 2, MOD);
    return ((ans % MOD) * ans1) % MOD;
}

void dfs(string s, char mx, ll N)
{
    if (s.length() == N)
    {
        cout << s.c_str() << endl;
    }
    else
    {
        for (char c = 'a'; c <= mx; c++)
        {
            dfs(s + c, ((c == mx) ? (char)(mx + 1) : mx), N);
        }
    }
}

int main()
{
    ll H, W;
    cin >> H >> W;

    if (H == 1 || W == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    if (H % 2 == 0)
    {
        cout << W * (H / 2) << endl;
    }
    else
    {
        ll tmp = (W * ((H - 1) / 2)) + ceil(W / 2.0);
        cout << (W * ((H - 1) / 2)) + (W+1)/2 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int x[] = new int[m];
    for (int i = 0; i < m; i++) {
      x[i] = sc.nextInt();
    }
    Arrays.sort(x);

    if (m == 1) {
      System.out.println(0);
      return;
    }

    int sabun[] = new int[m - 1];
    for (int i = 1; i < m; i++) {
      sabun[i - 1] = x[i] - x[i - 1];
    }

    Arrays.sort(sabun);
    int sum = 0;
    for (int i = 0; i < sabun.length; i++) {
      if (i + n - 1 < sabun.length) {
        sum += sabun[i];
      }
    }
    System.out.println(sum);
  }
}


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

int main() {
	int D;
	cin >> D;
	if (25 == D) {
		cout << "Christmas" << endl;
	}
	else if (24 ==D) {
		cout << "Christmas Eve" << endl;
	}
	else if (23 == D) {
		cout << "Christmas Eve Eve" << endl;
	}
	else {
		cout << "Christmas Eve Eve Eve" << endl;
	}
	return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    ll H,W;
    cin >> H >> W;
    ll res = 1e9;
    for(int x=1;x<=W;x++){
        ll one = H*x;
        ll two = (W-x)*(H/2);
        ll three = (W-x)*(H-H/2);
        res = min(res,max(one,max(two,three))-min(one,min(two,three)));

        two = ((W-x)/2)*H;
        three =((W-x)-(W-x)/2)*H;
        res = min(res,max(one,max(two,three))-min(one,min(two,three)));
    }

    for(int y=1;y<=H;y++){
        ll one = W*y;
        ll two = (H-y)*(W/2);
        ll three = (H-y)*(W-W/2);
        res = min(res,max(one,max(two,three))-min(one,min(two,three)));

        two = ((H-y)/2)*W;
        three =((H-y)-(H-y)/2)*W;
        res = min(res,max(one,max(two,three))-min(one,min(two,three)));
    }

    cout << res << endl;
    return 0;
}

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

int main (){
  int n,x;
  cin >> n;
  
  for(int i=1;i<=n;i++){
    x=i;
    if (x%3 == 0 ){
      cout << " " << i;
    }else {
      while(x){
	if(x%10 == 3){
	  cout << " " << i;
	  break;
	}x/=10;
      }
    }
  }cout << endl;
}


Measured memory_bytes: 3092
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  lint n,m;
  cin>>n>>m;
  vector<lint> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    n-=a[i];
  }
  if(n>=0){
    cout<<n<<endl;

  }else{
    cout<<-1<<endl;
  }


  return 0;
}




Measured memory_bytes: 3680
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  vector<P> cnt(n+2,P(0,0));
  bool flag=true;
  FOR(i,1,n+1){
    ll a;
    cin>>a;
    cnt[i].fi=a;
    if(cnt[i-1].fi<a) cnt[i].se=1;
  }
  vector<ll> b(n+1);
  rep(i,n) cin>>b[i+1];
  for(int i=n;i>=1;i--){
    ll a=b[i];
    if(cnt[i].se && cnt[i].fi>a) flag=false;
    cnt[i].fi=min(cnt[i].fi,a);
    if(cnt[i+1].fi<cnt[i].fi) cnt[i].se=1;
  }
  if(!flag) cout<<0<<endl;
  else{
    ll ans=1;
    FOR(i,1,n+1){
      if(cnt[i].se) continue;
      (ans*=(cnt[i].fi)%mod)%=mod;
    }
    cout<<ans<<endl;
  }
}

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

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n, m, k;
	cin >> n >> m >> k;
	vector<int> A(n), B(m);
	REP(i, n) cin >> A[i];
	REP(i, m) cin >> B[i];

	vector<ll> a(n + 1, 0);
	REP(i, n) a[i + 1] = a[i] + A[i];
	vector<ll> b(m + 1, 0);
	REP(i, m) b[i + 1] = b[i] + B[i];

	int res = 0;
	int j = m;
	REP(i, n + 1) {
		if (a[i] > k) break ;
		while (b[j] > k - a[i])
			j--;
		res = max(res, i + j);
	}

	cout << res << '\n';
	return 0;
}


Measured memory_bytes: 7888
#include<bits/stdc++.h>
using namespace std;
namespace io{
    const int l=1<<20;
    char buf[l],*s,*t,c;
    inline void gc(){
        if(s==t){
            t=(s=buf)+fread(buf,1,l,stdin);
            c=s==t?EOF:*s++;
        }else c=*s++;
    }
    template<class IT>inline void gi(IT &x){
        x=0;gc();while(c<'0'||c>'9')gc();
        while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}
    }
    char buf0[20];int a;
    template<class IT>inline void pi(IT x){
        if(x<0){putchar('-');x=-x;}
        do buf0[++a]=x%10+48;while(x/=10);
        while(a)putchar(buf0[a--]);
        putchar('\n');
    }
};
using io::gi;
using io::pi;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll > pil;
typedef pair<ll ,int> pli;
typedef pair<ll ,ll > pll;
typedef vector<int> vi;
typedef vector<ll > vl;
#define pque priority_queue
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const int N=200005;
const ll p=1000000007ll;
vi e[N];
ll inv[N],t[N],nn;
int dfs(int v,int f){
	int i=e[v].size(),u,sz=1;
	while(i--)if((u=e[v][i])!=f)sz+=dfs(u,v);
	if(f){
		t[1]=t[1]*sz%p;
		t[v]=t[v]*((nn-sz)*inv[sz]%p)%p;
	}
	return sz;
}
void df2(int v,int f){
	int i=e[v].size(),u;
	while(i--)if((u=e[v][i])!=f){
		t[u]=t[u]*t[v]%p;
		df2(u,v);
	}
}
inline ll expo(ll a,int b=1000000005){
	ll c=1ll;
	while(b){
		if(b&1)c=c*a%p;
		b>>=1; a=a*a%p;
	}
	return c;
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,i,v,u;ll f=1ll;
    scanf("%d",&n);nn=n;
    REP(i,1,n){
		scanf("%d%d",&v,&u);
		e[v].pb(u);
		e[u].pb(v);
	}
	inv[1]=1ll;
	rep(i,2,n)inv[i]=(p-p/i)*inv[p%i]%p;
	rep(v,1,n)t[v]=1ll;
	dfs(1,0);
	df2(1,0);
	REP(i,2,n)f=f*i%p;
	rep(v,1,n)printf("%lld\n",f*expo(t[v])%p);
    return 0;
}

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

static const int INF = 1e9+7;

int main(){
    int N;
    cin>>N;
    vector<int> dp(100000+10,INF);
    dp[0] = 0;

    for(int i=0; i<=N; i++){
        for(int j=1; j<=N; j*= 6){
            if(i-j >= 0) dp[i] = min(dp[i-j]+1,dp[i]);
        }

        for(int j=1; j<=N; j *= 9){
            if(i - j >= 0) dp[i] = min(dp[i-j]+1,dp[i]);
        }
    }

    cout<<dp[N]<<endl;
}

Measured memory_bytes: 3744
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            if(vals[0] <= 8 && vals[1] <= 8)
            {
                Console.WriteLine("Yay!");
            }
            else
            {
                Console.WriteLine(":(");
            }
        }
    }

}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ull unsigned long long
#define mp make_pair
#define F first
#define S second
#define mod 1000000007

int n;
double dp[3002];
double p;

int main()
{
    cin >> n;
    dp[0] = 1;
    for(int coin=0;coin<n;coin++)
    {
        cin >> p;
        for(int j = coin+1;j >= 0; j--)
            dp[j] = ( j == 0 ? 0 : dp[j-1]*p) + dp[j]*(1-p);
    }    
    
    double ans = 0;
    for(int i=0;i<=n;i++)
        if(i>n-i)
            ans += dp[i];
    printf("%.10lf\n", ans);
}


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

template<typename T, int MAX_N>
struct BIT {
    int N;
    T arr[MAX_N];

    BIT (int n) : N(n) {
        for (int i = 0; i <= N; ++i) {
            arr[i] = (T)0;
        }
    }

    void add (int i, T a) {
        for (int x = i; x <= N; x += x & -x) {
            arr[x] += a;
        }
    }

    T query(int i) {
        T val = 0;
        for (int x = i; x > 0; x -= x & -x) {
            val += arr[x];
        }
        return val;
    }
};

int N, Q;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> Q;
    BIT<int, 101010> bit(N);
    for (int j = 0; j < Q; ++j) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            bit.add(x, y);
        } else {
            cout << (bit.query(y) - bit.query(x-1)) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int a,b,c,d;
int gcd(int x,int y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
int lcm(int x,int y){
    int n=gcd(x,y);
    return (x/n)*y;
}
signed main(){
    cin>>a>>b>>c>>d;
    int m=lcm(c,d);
    int p=(a-1)/c,q=(a-1)/d,r=(a-1)/m;
    int s=p+q-r;
    int t=b/c,u=b/d,v=b/m;
    int w=t+u-v;
    int n=b-a+1;
    cout<<n-(w-s)<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int divisor(int n){
    int i,count=0;
    for(i=1;i<=n;i++){
        if(n%i==0) count++;
    }
    return count;
}
int main() {
    int i,n,res,count=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        if(i%2!=0){
            res=divisor(i);
            if(res==8) count++;
        }
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 128
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        a: u64,
        b: u64,
    }

    let mut v: Vec<u64> = vec![0; 60];
    for i in 1..60 {
        let c = a % 2u64.pow(i + 1);
        let d = b % 2u64.pow(i + 1);
        let mut e: u64 = 0;
        if c >= 2u64.pow(i) {
            e += 2u64.pow(i + 1) - c;
        } else {
            e += 2u64.pow(i);
        }
        if d >= 2u64.pow(i) {
            e += d - 2u64.pow(i) + 1;
        }
        if e % 2 == 1 {
            v[i as usize] += 1;
        }
    }
    if b % 2 == 1 && a % 2 == 1 && (b - a) % 4 == 0 {
        v[0] += 1;
    }
    if b % 2 == 0 && a % 2 == 0 && (b - a) % 4 == 2 {
        v[0] += 1;
    }
    if b % 2 == 1 && a % 2 == 0 && (b - a) % 4 == 1 {
        v[0] += 1;
    }
    if b % 2 == 0 && a % 2 == 1 && (b - a) % 4 == 1 {
        v[0] += 1;
    }
    let mut ans: u64 = 0;
    for i in 0..60 {
        ans += v[i as usize] * 2u64.pow(i);
    }

    println!("{}", ans);
}


Measured memory_bytes: 2180
N = int(input())

for i in range(1, 3501):
    for j in range(i, 3501):
        if (4 * i * j - N * i - N * j) <= 0:
            continue
        if N * i * j % (4 * i * j - N * i - N * j) == 0:
            print(i, j, N * i * j // (4 * i * j - N * i - N * j))
            exit()

Measured memory_bytes: 3060
N = int(input())
S = list(input())

ans = N

left_W = 0
right_E = S[1:].count("E")

for n in range(N):
  if n == 0:
    ans = min(ans,S[1:].count("E"))
        
  elif n == N-1 :
    ans = min(ans,S[:n].count("W"))
      
  else:
    if S[n] == "E":
      right_E -= 1
    if S[n-1] == "W":
      left_W += 1
    ans = min(ans,left_W + right_E)

print(ans)

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

int main() {

    int n;

    bool isTrue = true;

    cin >> n;

    for(int i = 0; i < n; ++i) {
        int num;
        cin >> num;

        if(num % 2 != 0)
            continue;

        if(num % 3 != 0 && num % 5 != 0)
            isTrue = false;

    }

    if(isTrue)
        cout << "APPROVED" << endl;
    else
        cout << "DENIED" << endl;
    
    return 0;

}

Measured memory_bytes: 256
// 物极必反

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 2e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9;
const double PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug(){
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

long long a[N], b[N], c[N], dp[N][3];

void solve(){
    long long n; cin >> n;

    for(long long i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }

    for(long long i = 1; i <= n; i++){
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i];
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]});
}

int main(){
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    long long q = 1; // cin >> q;

    while(q--){
        solve();
    }

    return 0;
}


Measured memory_bytes: 8360
// by syu
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var in = NewScanner(os.Stdin, 0)

func main() {
	D := in.Int()
	switch D {
	case 25:
		Pln("Christmas")
	case 24:
		Pln("Christmas Eve")
	case 23:
		Pln("Christmas Eve Eve")
	case 22:
		Pln("Christmas Eve Eve Eve")
	}
}

type Scanner struct {
	*bufio.Scanner
}

func NewScanner(r io.Reader, max int) *Scanner {
	s := bufio.NewScanner(r)
	s.Split(scanWords)
	if max <= 0 {
		max = 1048576
	}
	s.Buffer([]byte{}, max)
	return &Scanner{s}
}
func (s *Scanner) Int() int {
	s.Scan()
	i, e := strconv.ParseInt(s.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return int(i)
}
func isSpace(b byte) bool {
	return b == ' ' || b == '\n' || b == '\r' || b == '\t'
}
func scanWords(data []byte, atEOF bool) (advance int, token []byte, err error) {
	start := 0
	for start < len(data) && isSpace(data[start]) {
		start++
	}
	for i := start; i < len(data); i++ {
		if isSpace(data[i]) {
			return i + 1, data[start:i], nil
		}
	}
	if atEOF && len(data) > start {
		return len(data), data[start:], nil
	}
	return start, nil, nil
}
func Pln(s ...interface{}) {
	fmt.Println(s...)
}


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

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

  std::string tmp = "";
  for (const char c : s) {
    std::size_t n = tmp.size();
    if (c == 'B' && n == 0) {
      tmp = tmp;
    } else if (c == 'B' && n > 0) {
      tmp = tmp.substr(0, n - 1);
    } else if (c == '0') {
      tmp += '0';
    } else if (c == '1') {
      tmp += '1';
    }
  }
  std::cout << tmp << std::endl;
  return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define trav(x, a) for (auto& x: a)

const int MX  = 2e5+5;
const int MOD = 1e9+7;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

int N, M;
bitset<10> vis;
vi adj[10];

int solve_dp(int u) {
    if (vis.count() == N-1) return 1;
    int ans = 0; vis[u] = true;
    trav(v, adj[u]) if (!vis[v]) {
        ans += solve_dp(v);
    }
    vis[u] = false;
    return ans;
}


int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;

    F0R(i,M) {
        int u,v; cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }

    cout << solve_dp(1) << "\n";

}


Measured memory_bytes: 256
n, y = map(int, input().split())

for i in range(n + 1):
    for j in range(n + 1 - i):
        if 10000*i + 5000*j + 1000*(n - i - j) == y:
            if n - i - j >= 0:
                print(i, j, n - i - j)
                exit()

print(-1, -1, -1)

Measured memory_bytes: 3060
#include <iostream>
#include <utility>
#include <stdint.h>
#include <vector>

using namespace std;

int main()
{
  int N;
  cin >> N;

  vector<unsigned> H;
  
  for (int n=0; n<N; ++n) {
    unsigned h;
    cin >> h;
    H.push_back(h);
  }

  bool feasible = true;
  
  for (int n=1; n<N && feasible; ++n) {
    if (H[n-1] <= H[n])
      continue;
    else if (H[n-1] == H[n]+1)
      ++H[n];
    else
      feasible = false;
  }

  cout << (feasible? "Yes":"No") << endl;

  return 0;
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(2e5 + 5);

int n, k;
int p[MAX_N];

int q[MAX_N];

void hoge() {
  map<vector<int>, int> unko;
  for (int i = 0; (i + k - 1) < n; ++i) {
    for (int j = 0; j < n; ++j) {
      q[j] = p[j];
    }

    sort(q + i, q + i + k);

    vector<int> tmp;
    for (int j = 0; j < n; ++j) {
      tmp.push_back(q[j]);
      printf("%d ", q[j]);
    }
    printf(":%d %d\n", i, i + k - 1);

    unko[tmp] += 1;
  }

  cout << endl;

  for (auto &e : unko) {
    for (auto &d : e.first) {
      printf("%d ", d);
    }
    printf(": ");

    printf("%d\n", e.second);
  }
  cout << endl;
}

int counter_mono_part() {

  p[n] = -1;

  int ret = 0;

  int cnt = 1;

  for (int i = 1; i <= n; ++i) {
    // printf("i: %d, ret: %d, cnt: %d\n", i, ret, cnt);
    if (p[i - 1] < p[i]) cnt += 1;
    else {
      if (cnt >= k) ret += 1;
      cnt = 1;
    }
  }

  return ret;
}

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &k);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &(p[i]));
  }

  set<int> st;

  for (int i = 0; i < k; ++i) {
    st.insert(p[i]);
  }

  int cnt = 1;

  // hoge();

  int mono_part = counter_mono_part();

  // printf("mono: %d\n", mono_part);

  for (int i = 1; (i + k - 1) < n; ++i) {
    int last_begin_ind = i - 1;
    int last_begin = p[last_begin_ind];

    int cur_end = p[i + k - 1];

    int last_max = *(--st.end());

    st.erase(st.find(last_begin));

    int cur_min = *(st.begin());

    if (!(last_begin < cur_min && last_max < cur_end)) {
      // printf("%d %d\n", i, i + k - 1);
      cnt += 1;
    }

    st.insert(cur_end);
  }

  int ans = cnt;

  if (mono_part >= 1) {
    ans -= mono_part;
    ans += 1;
  }

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

  // printf("min: %d\n", *(st.begin()));
  // printf("max: %d\n", *(--st.end()));

  return 0;
}


Measured memory_bytes: 10368
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    string s;
    cin>>n;
    cin>>s;
    int r=0,b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='R') r++;
        else b++;
    }
    if(r>b) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()
#define MP(n, m) make_pair(n, m);
#define COUT(d) cout<<std::setprecision(10)<<d<<endl;
#define CIN(n) getline(cin,n);

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;
using ul = unsigned long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const int mod=1e9+7;


void printv(VI& v){
  REP(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vector<ll>& v){
  REP(i,v.size()) cout << v[i] << " ";
  cout << endl;
}

int vtotal(VI& v){
  int total=0;
  REP(i,v.size()) total+=v[i];
  return total;
}

int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
	
  //init(); // mint初期化

  int n;
  cin>>n;

  vector<ll> h;
  REP(i,n){
    ll a;cin>>a;
    h.push_back(a);
  }
  // cout<<LONG_MAX<<endl;

  string ans="Yes";
  REP(i,n){
    int index=n-i-1;
    if(index==0)break;
    int now=h[index];
    int before=h[index-1];
    if(before<=now){}
    else{
      before--;
      if(before>now){
        ans="No";
        break;
      }
      h[index-1]=before;
    }
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 1400
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;

int main(){
  int n;
  scanf("%d",&n);
  char s[2000];
  rep(i,n){
    scanf("%s",s);
    int len = strlen(s);
    char now = 0;
    rep(j,len){
      if(!now && s[j]=='0') continue;
      else if(s[j]=='0') {putchar(now); now = 0;}
      else if(s[j]=='1'){
        if(now=='.') now = ',';
        else if(now==',') now = '!';
        else if(now=='!') now = '?';
        else if(now=='?') now = ' ';
        else if(now==' ' || now==0) now = '.';
      }
      else if(s[j]=='2'){ if(now==99 || !now) now = 97; else now++;}
      else if(s[j]=='3'){ if(now==102 || !now) now = 100; else now++;}
      else if(s[j]=='4'){ if(now==105 || !now) now = 103; else now++;}
      else if(s[j]=='5'){ if(now==108 || !now) now = 106; else now++;}
      else if(s[j]=='6'){ if(now==111 || !now) now = 109; else now++;}
      else if(s[j]=='7'){ if(now==115 || !now) now = 112; else now++;}
      else if(s[j]=='8'){ if(now==118 || !now) now = 116; else now++;}
      else if(s[j]=='9'){ if(now==122 || !now) now = 119; else now++;}
    }
    putchar('\n');
  }


  return 0;

}

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

int64_t MOD;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = 1;
    fact[1] = 1;
    for(int i=2; i<=num; i++){
        fact[i] = fact[i-1] * i % MOD;
    }
}

void create_seq_inv_mod(int num){
    seq_inv[0] = 1;
    seq_inv[1] = 1;
    for(int i=2; i<=num; i++){
        seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
    }
}

void create_fact_inv_mod(int num){
    fact_inv[0] = 1;
    fact_inv[1] = 1;
    for(int i=2; i<=num; i++){
        fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
    }
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main(){
    int N;
    cin >> N >> MOD;

    create_mod_tables(10000);

    int64_t ans = 0;
    for(int i=1; i<N; i++){
        int64_t res = comb_mod(N, i);
        int j = N-i;
        
        int64_t same = i*(i-1)/2 + j*(j-1)/2;
        mul(res, power_mod(2, same));

        int64_t C = 0;
        for(int x=0; x<=i; x++){
            int64_t r = comb_mod(i, x);
            mul(r, power_mod(power_mod(2, i-x) - 1, j));
            add(C, x%2 ? MOD-r : r);
        }
        mul(res, C);
        add(ans, res);
    }
    cout << ans << endl;
}



Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;
#define ll int64_t
#define rep(i,n) for(int64_t i=0;i<n;++i)
#define P pair<ll,ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr int64_t INF=(1ll<<60);
constexpr int64_t mod=1000000007;
constexpr double pi=3.14159265358979323846;
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

    if(n==m) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <complex>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

bool used[1000002];

int main() {
  int K;
  cin >> K;

  int rem = 0;
  int cnt = 0;
  
  while (true) {
    cnt++;
    rem = rem * 10 + 7;
    if (rem < K) {
      continue;
    }

    int x = rem % K;
    if (x == 0) {
      cout << cnt << endl;
      return 0;
    }
    if (used[x]) {
      break;
    }
    used[x] = true;
    rem = x;
  }
  cout << -1 << endl;
}


Measured memory_bytes: 4540
while 1:
    ba = 0

    p = [0 for i in range(int(input()))]
    if len(p) == 0:break

    for i,v in enumerate(list(input())):
        p[i%len(p)] += 1
        if v == 'L':
            p[i%len(p)] += ba
            ba = 0
        elif v== 'S':
            ba += p[i%len(p)] 
            p[i%len(p)] = 0

    result = ''
    for v in sorted(p):
       result +=  '%d ' % v
    result += str(ba)
    print(result)

Measured memory_bytes: 6724
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
		
		int intArray[] = new int[N];

		for(int i = 0 ;i < N;i++){
			intArray[i] = sc.nextInt();
		}

		int cnt = 0;
		for(int i = 0 ;i < N-2;i++){
			if(intArray[i]<intArray[i+1]) {
				if(intArray[i+1]<intArray[i+2]) {
					cnt ++;
				}
				
			}else {
				if(intArray[i]>intArray[i+1]) {
					if(intArray[i+1]>intArray[i+2]) {
						cnt ++;
					}
				}
			}
		}

		System.out.println(cnt);

   		sc.close();
        return ;

    }
    
}



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

int main() {
	int N, A;
	cin >> N >> A;
	int x[53];
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
		sum += x[i];
	}
	long long dp[53][2550][53] = { 0 };
	dp[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k <= N; k++) {
			for (int j = 0; j <= 2500; j++) {
				if (j >= x[i]&&j>0) {
					dp[i + 1][j][k] = dp[i][j - x[i]][k - 1] + dp[i][j][k];
				}
				else {
					dp[i + 1][j][k] = dp[i][j][k];
				}
			}
		}
	}
	long long combi;
	combi = 0;
	int n = 0;
	n = sum / A;
	for (int i = 1; i <= N; i++) {
			combi += dp[N][i*A][i];
	}
	cout << combi;
	return 0;
}

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

int main() {
  long long N;
  cin >> N;
  long long H[100000];
  for (long long i = 0; i < N; i++) {
    cin >> H[i];
  }
  
  bool ans = true;
  
  for (long long i = N -1; i > 0; i--) {
    if (H[i-1] - H[i] > 1 ) {
      ans = false;
      break;
    }
    else if (H[i-1] - H[i] == 1) {
      H[i-1] -= 1;
    }
  }
  
  

  if (ans) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  
      
      
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define pld pair <ld, ld>
#define all(a) a.begin(), a.end()
#define vvl vector <vector <ll> >
#define cld complex <double>

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;

ll n, m, k, t, h;

ll st2[maxn];

ll ans = 0;

ll P[maxn];

ll mark[maxn];

vector <ll> to_clear;

void dfs2(ll v, bool left, ll product, ll last) {
    // cout << "DFS2 " << v << endl;
    ll nproduct = product * (v) % mod;
    if (left) {
        to_clear.pb(v);
        mark[v] += product;
        mark[v] %= mod;
    }
    else {
        ll dans = nproduct * (mark[v] - mark[last] * last % mod + mod) % mod;
        // cout << v << " DANS " << dans << endl;
        ans += dans;
        ans %= mod;
    }
    if (v == 1) {
        return;
    }
    dfs2(v / 2, left, nproduct, v);
}

void dfs1(ll v, bool left, ll product) {
    // cout << "V " << v << endl;
    ll nproduct = product * (v) % mod;
    if (v > n - m) {
        ll to = n - m + P[v - (n - m) - 1] + 1; 
        // cout << "FROM " << v << " TO " << to << endl;
        dfs2(to, left, nproduct, 0);
        return;
    }
    dfs1(2 * v, left, nproduct);
    dfs1(2 * v + 1, left, nproduct);
}

void work(ll v) {
    // cout << "WORK " << v << endl;
    ll q;
    dfs1(v * 2, 1, v);
    dfs1(v * 2 + 1, 0, 1);
    for (auto v : to_clear) {
        mark[v] = 0;
    }
    to_clear.clear();
}

int main() {
    pyshnapyshnakaa
    ll q, w, e, a, b, c;
    st2[0] = 1;
    for (q = 1; q < 63; q++) {
          st2[q] = st2[q - 1] * 2;
    }
    cin >> h;
    m = st2[h - 1];
    n = st2[h] - 1;
    for (q = 0; q < m; q++) {
        cin >> P[q];
        P[q]--;
    }
    for (q = 1; q <= n - m; q++) {
        work(q);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 22764
/**
*   Author : Krishna Purohit
*/

#include "bits/stdc++.h"
#define sync ios_base::sync_with_stdio(false)
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mod 10000000007
using namespace std;

ll t, n;

int main() {
    sync;
    cin >> n;
    string s;
    cin >> s;
    if(n & 1) {
        cout << "No" << endl;
        return 0;
    }
    else {
        bool yes = true;
        n /= 2;
        for(int i = 0; i < n; ++i) {
            if(s[i] != s[i+n]) {
                yes = false;
                break;
            }
        }
        if(yes) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int>v[MAXN];
int main()
{
	int n,m;
	cin >> n >> m;
	int a[m][2];
	for(int i = 0;i < m;i++){
		scanf("%d %d",&a[i][0],&a[i][1]);
		v[a[i][0]].push_back(a[i][1]);
	}
	for(int i = 1;i <= n;i++){
		sort(v[i].begin(),v[i].end());
	}
	vector<int>::iterator it;
	for(int i = 0;i < m;i++){
		it = find(v[a[i][0]].begin(),v[a[i][0]].end(),a[i][1]);
		printf("%06d%06d\n",a[i][0],upper_bound(v[a[i][0]].begin(), v[a[i][0]].end(), a[i][1]) - v[a[i][0]].begin());
	}
	return 0;
}


Measured memory_bytes: 7808
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

int main(void){
	int i,N,k=0;
	string S;
	cin >> N;
	cin >> S;

	for(i=0;i<N-2;i++){
		if(S.substr(i,3) == "ABC"){
			k++;
		}
	}
	cout << k << endl;
}

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

int main() {
	long int n,i,j;
	cin>>n;
	long int a[n][3];
	for(i=0;i<n;i++)
	{for(j=0;j<3;j++)
	cin>>a[i][j];
	}
	long int dp[n][3];
	for(i=0;i<3;i++)
	{dp[0][i]=a[0][i];
	}
	for(i=1;i<n;i++)
	{
	    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
	      dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
	        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+a[i][2];
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	return 0;
}

Measured memory_bytes: 4992
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long K = sc.nextLong();
        long res = 0;
        final long INF = (long)Math.pow(10, 9) + 7;
        for (long i = K; i <= N + 1; i++) {
            long min = (i - 1) * i / 2;
            long max = i * (N - i + 1) + (i - 1) * i / 2;
            res += max - min + 1;
        }
        System.out.println(res % INF);
        sc.close();
    }
}

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

int main(){
  int64_t x;
  int64_t y;
  int64_t a;
  int64_t b;
  int64_t c;
  cin >> x >> y >> a >> b >> c;
  priority_queue<int64_t> P;
  priority_queue<int64_t> Q;
  priority_queue<int64_t> R;
  
  int64_t k;
  for(int i=0; i<a; i++){
    cin >> k;
    P.push(k);
  }
  for(int i=0; i<b; i++){
    cin >> k;
    Q.push(k);
  }
  for(int i=0; i<c; i++){
    cin >> k;
    R.push(k);
  }
  R.push(-1);
  
  //cout << Q.top() << endl;
  
  int64_t ans=0;
  int64_t cnt=x+y;
  
  //cout << cnt << endl;
  
  while(cnt != 0){
    int64_t s=0;
    int64_t t=0;
    int64_t u=0;
    
    if(x>0){s = P.top();}
    if(y>0){t = Q.top();}
    u = R.top();
    int64_t W = max(max(s,t),u);
    //cout << W << endl;
    ans += W;
    //ans += max(max(s,t),u);
    cnt--;
    
    if(W==s){
      x--;
      P.pop();
    }
    else if(W==t){
      y--;
      Q.pop();
    }
    else{
      R.pop();
    }
  
  }
  cout << ans << endl;
  

}


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
int dp[maxn][20];
int x[maxn];

int main(){
    int N, L, Q, a, b;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        scanf("%d", &x[i]);
    }
    scanf("%d", &L);
    x[0] = x[1];
    for(int i = 1, l = 0; i <= N; i++){
        while(x[i] - x[l] > L) l++;
        dp[i][0] = l;
        for(int j = 1; j < 20; j++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    scanf("%d", &Q);
    while(Q--){
        scanf("%d%d", &a, &b);
        if(a < b) swap(a, b);
        int ans = 0;
        for(int d = 19; d >= 0; d--){
            if(dp[a][d] > b){
                ans += (1 << d);
                a = dp[a][d];
            }
        }
        printf("%d\n", ans + 1);
    }
    return 0;
}


Measured memory_bytes: 8960
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    ll x; cin>>x;
    ll ans = 0;
    ll y = floor(x/500);
    ll z = floor(x%500/5);
    
    ans = y * 1000 + z * 5;
    
    cout << ans << ln;
    return 0;
 }

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

const int maxn = 110, maxm = 1e5 + 10, P = 1e9 + 7;
int n, k, s[maxm], f[maxn][maxm];

int main() {
	scanf("%d %d", &n, &k), f[0][0] = 1;
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x), s[0] = f[i - 1][0];
		for (int j = 1; j <= k; j++) {
			s[j] = (s[j - 1] + f[i - 1][j]) % P;
		}
		for (int j = 0; j <= k; j++) {
			f[i][j] = (s[j] - (j - x > 0 ? s[j - x - 1] : 0) + P) % P;
		}
	}
	printf("%d", f[n][k]);
	return 0;
}

Measured memory_bytes: 43264
#include <stdio.h>

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define N 200010
#define MAX 1000000000000000000

#include <stdio.h>

int main (void) {
    char n[4];
    int i;

    scanf("%s", n);

    for (i = 0; i < 4; i++) {
        if (n[i] == '7') {
            puts("Yes");
            return 0;
        }
    }

    puts("No");

    return 0;
}



Measured memory_bytes: 1644
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,k,a[2010],ans = 0;
	cin >> n >> k;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++){
		for(int j = i + 1;j < n;j++){
			if(a[i] > a[j]) (ans += k * (k + 1) / 2) %= MOD;
			else if(a[i] < a[j]) (ans += k * (k - 1) / 2) %= MOD;
		}
	}
	cout << ans << endl;
}

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

int main(){
  long long n,d;
  cin >> n >> d;
  long long ans=0;
  long long x,y;
  
  for(int i=0;i<n;i++){
    cin >> x >> y;
    if(x*x+y*y<=d*d) ans++;
  }
  cout << ans << endl;
}



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

int main(){
	int n, cnt = 0, flag;
	vector<int> A(100);
    cin >> n;
	for(int i = 0; i < n; i++) cin >> A[i];

	flag = 1;
	while(flag){
		flag = 0;
        for(int i = n-1; i > 0; i--)
        {
            if (A[i] < A[i-1]) {
                swap(A[i], A[i-1]);
                flag = 1;
                cnt++;
            }
        }
	}

    for(int i = 0; i < n; i++)
    {
        if(i > 0) cout << ' ';
        cout << A[i];
    }

    cout << endl << cnt << endl;
    

	
}


Measured memory_bytes: 3096
#include <stdio.h>

int main() {
  int N, K, R, S, P;
  char T[100000];
  char* ptr;
  int point;
 
  scanf("%d %d", &N, &K);
  scanf("%d %d %d", &R, &S, &P);
  scanf("%s", T);
 
  ptr = T;
  
  for(int i=0; i<N; i++){
    switch(*ptr) {
    	case 'r':
      		if(i>=K && *(ptr-K) == 'r'){
              	T[i] = 'n';
              	break;
            }
      		point += P;
        	break;
      	case 's':
        	if(i>=K && *(ptr-K) == 's'){
              	T[i] = 'n';
      			break;	
            }
            point += R;
        	break;
      	case 'p':
        	if(i>=K && *(ptr-K) == 'p'){
              	T[i] = 'n';
      			break;	
            }
            point += S;
        	break;
  	}
    ptr++;
  }
  
  printf("%d", point);
  
  return 0;
}

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

long double factorial ( int x )
{
  if ( x == 0 ) return 1;
  return x * factorial( x-1 );
}

int main()
{
  while (true)
  {
    int n;      //  段数
    cin >> n;
    if ( n == 0 ) break;

    long int pattern = 0;

    for (int a=0; a <= n/3; a++)
    {
      for (int b=0; b <= n/2; b++)
      {
        for (int c=0; c <=n; c++)
        {
          if ( 3*a + 2*b + c == n )
          {
            pattern += factorial( a+b+c ) / 
               factorial(a) / factorial(b) / factorial(c) ;
          }
        }
      }
    }

    long int day = pattern / 10 + ( pattern%10 == 0 ? 0 : 1 );
    long int year = day / 365 + ( day%365 == 0 ? 0 : 1 );
    cout << year << endl;
  }
}

Measured memory_bytes: 1160
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

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

int main() {
    int a,b,c,x;
    cin >> a >> b >> c >> x;

    int r = 0;
    REP(i, a+1) {
        REP(j, b+1) {
            REP(k, c+1) {
                if (500*i+100*j+50*k == x) r++;
            }
        }
    }

    cout << r << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> E;
const LL MOD = 1000000007LL;
int sum[2000][2000];
int cnt(int y1, int x1, int y2, int x2) {
	int ret = sum[y2][x2];
	if (x1 > 0) ret -= sum[y2][x1 - 1];
	if (y1 > 0) ret -= sum[y1 - 1][x2];
	if (x1 > 0 && y1 > 0) ret += sum[y1 - 1][x1 - 1];
	return ret;
}
int main() {
	int N, K;
	cin >> N >> K;
	vector<P> v;
	for (int i = 0; i < N; i++) {
		int x, y;
		string c;
		cin >> x >> y >> c;
		if (c == "W") x += K;
		x %= 2 * K;
		y %= 2 * K;
		sum[y][x]++;
	}
	for (int i = 0; i < 2*K; i++) {
		for (int j = 1; j < 2 * K; j++) sum[i][j] += sum[i][j - 1];
	}
	for (int i = 1; i < 2*K; i++) {
		for (int j = 0; j < 2 * K; j++) sum[i][j] += sum[i - 1][j];
	}
	int ans = 0;
	for (int i = 0; i <= K; i++) {
		for (int j = 0; j <= K; j++) {
			int now = cnt(i, j, i + K - 1, j + K - 1);
			if (i > 0 && j > 0) now += cnt(0, 0, i - 1, j - 1);
			if (j > 0 && i + K < 2 * K) now += cnt(i + K, 0, 2 * K - 1, j - 1);
			if (j + K < 2 * K && i>0) now += cnt(0, j + K, i - 1, 2 * K - 1);
			if (j + K < 2 * K && i + K < 2 * K) now += cnt(i + K, j + K, 2 * K - 1, 2 * K - 1);
			ans = max(ans, max(now, N - now));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 15872
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;

struct UnionFind {
    int node[110];
    UnionFind() {
        memset(node, -1, sizeof(node));
    }

    int find(int x) {
        return node[x] < 0 ? x : find(node[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(size(x) < size(y)) swap(x, y);
        node[x] += node[y];
        node[y] = x;
    }

    int size(int x) {
        return -node[x];
    }
};

struct Elem {
    int from, to;
    double d;
    bool operator<(const Elem &e) const {
        return d < e.d;
    }
};

const double EPS = 1e-8;

double coor[110][3], r[110];
double dist(int p, int q) {
    double val = 0;
    for(int i=0; i<3; i++) {
        double diff = coor[p][i] - coor[q][i];
        val += diff * diff;
    }
    return max(0.0, sqrt(val) - r[p] - r[q]);
}

int main() {
    int N;
    while(1) {
        scanf("%d", &N);
        if(N == 0) break;

        for(int i=0; i<N; i++) {
            scanf("%lf%lf%lf%lf", &coor[i][0], &coor[i][1], &coor[i][2], &r[i]);
        }

        UnionFind uf;
        vector<Elem> lines;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(i == j) continue;
                double dist_ij = dist(i, j);
                if(dist_ij < EPS) {
                    uf.unite(i, j);
                    continue;
                }
                lines.push_back(Elem{i, j, dist_ij});
            }
        }
        sort(lines.begin(), lines.end());

        double ans = 0.0;
        for(auto e : lines) {
            int s = e.from, t = e.to;
            double cost = e.d;
            if(uf.same(s, t)) continue;
            uf.unite(s, t);
            ans += cost;
        }
        printf("%.3f\n", ans);
    }
    return 0;
}

Measured memory_bytes: 2932