akhauriyash/Code-Regression huggingface dataset:
S=input()+"R"
n=len(S)-1
ans=[0]*n
r=0
l=0
t=0
s=0
for i in range(n):
    if S[i]=="R":
        r+=1
        if S[i+1]=="L":
            t=i
    else:
        if S[i+1]=="R":
            e=o=(i-s+1)//2
            if (i-s+1)%2:
                e+=int(i%2==0)
                o+=int(i%2==1)
            if t%2:
                ans[t]=o
                ans[t+1]=e
            else:
                ans[t]=e
                ans[t+1]=o
            s=i+1
        else:
            l+=1
print(" ".join(map(str,ans)))

Measured memory_bytes: 10484
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,a[N],cnt[N],d;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        d=max(d,a[i]);
        cnt[a[i]]++;
    }
    int Min=(d+1)/2;
    for (int i=1;i<Min;i++)
        if (cnt[i]) return puts("Impossible"),0;
    if (d&1){
        for (int i=Min;i<=d;i++)
            if (cnt[i]<2) return puts("Impossible"),0;
        if (cnt[Min]!=2) return puts("Impossible"),0;
        return puts("Possible"),0;
    }
    else{
        for (int i=Min+1;i<=d;i++)
            if (cnt[i]<2) return puts("Impossible"),0;
        if (cnt[Min]!=1) return puts("Impossible"),0;
        return puts("Possible"),0;
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.System.in;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        int N = Integer.parseInt(reader.readLine());
        String[] inputs = reader.readLine().split(" ");
        boolean[] colors = new boolean[8];
        int above3200 = 0;
        for (int i = 0; i < N; i++) {
            int rate = Integer.parseInt(inputs[i]);
            if(rate <= 399) {
                colors[0] = true;
            } else if (rate <= 799) {
                colors[1] = true;
            } else if (rate <= 1199) {
                colors[2] = true;
            } else if (rate <= 1599) {
                colors[3] = true;
            } else if (rate <= 1999) {
                colors[4] = true;
            } else if (rate <= 2399) {
                colors[5] = true;
            } else if (rate <= 2799) {
                colors[6] = true;
            } else if (rate <= 3199) {
                colors[7] = true;
            } else {
                above3200 +=1;
            }
        }

        int count = 0;
        for (int i = 0; i < 8; i++) {
            if(colors[i]) {
                count += 1;
            }
        }
        int min = count;
        if(count == 0 && above3200 > 0) {
            min += 1;
        }
        int max = count + above3200;
        System.out.println(min + " " + max);
    }
}

Measured memory_bytes: 21204
using System;

class Program
{
	static void Main()
    {
     	double X = double.Parse(Console.ReadLine());
      	double now = 100;
      	long ans = 0;

		while(now < X){
        	now = now * 1.01;
          	now =  Math.Floor(now);
          	ans++;
        }
      	Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27560
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i < b; i++)
typedef long long ll;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  rep(i, n) cin >> a.at(i);
  rep(i, n){
    b.at(a.at(i) - 1) = i + 1;
  }
  rep(i, n) cout << b.at(i) << ' ';
  cout << endl;
}

Measured memory_bytes: 1664
#2行の文字列を受け取る
while True:
    str1 = input()
    if str1 == ".":
        break

    str2 = input()
#完全一致か判定する→「完全一致なら：ＸＸＸｘとだす」
    if str1 == str2:
        print("IDENTICAL")
        continue

#完全一致じゃない場合は→""でsplitする→頭が"ならば、奇数番目、頭が"じゃなければ、偶数番目にかこまれているやつはくる
        
    str1 = str1.split("\"")
    str2 = str2.split("\"")
    if not len(str1)==len(str2):
        print("DIFFERENT")
        continue
    
#""で囲まれていない場所が違っていたら、そもそもdiffrentをだす
    flg = 0
    for i in range(0,len(str1),2):
        if not str1[i] == str2[i]:
            flg = 1
            print("DIFFERENT")
            break
    if flg == 1:
        continue
    

#""で囲まれている場所を確認し、相違が1つだけならXXXXXを、2つ以上あればdiffrentをだす
    count = 0
    for i in range(1,len(str1),2):
        if not str1[i] == str2[i]: count +=1
        if count >= 2:
            break
    if count == 1:
        print("CLOSE")
    else:
        print("DIFFERENT")


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

int main() {
	long long n,k;
	cin >> n >> k;
	vector<pair<long long,long long>> c(n);
	for(int i=0;i<n;i++)
	{
		long long a,b;
		cin >> a >> b;
		c[i] = make_pair(a,b);
	}
	sort(c.begin(),c.end());
	long long d =0,kk;
	for(int i=0;i<n;i++)
	{
		d += c[i].second;
		if(d >= k)
		{
			kk = c[i].first;
			break;
		}
	}
    cout << kk << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<double> VL;
typedef vector<string> VS;
typedef vector<PLL> VP;
typedef vector<ll> VLL;
const static int INF = 1000000000;
const static int MOD = 1000000007;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "
//charを整数に
int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; }
// 累積和 for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; 
void cum_sum(int N,vector<double> a, vector<double> &s){ for(int i=0; i<N; i++){ s[i+1]=s[i]+a[i];}}
//ユークリッドの控除法
ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
//最小公倍数
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}
//空白文字も入力 getline(cin, S);
//桁数指定 setprecision

int main()
{
    int N;
    string S,T;
    cin >> S >> T;
    VI A(N);
    rep(i,S.size()){
        if(S[i]!=T[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> C(N);
  vector<vector<int>> A(N, vector<int>(M));
  rep(i, N) {
    cin >> C[i];
    rep(j,M) {
      cin >> A[i][j];
    }
  }

  vector<int> V(N);
  rep(i, N) V[i] = i;

  int ans = -1;

  for(int bit=0; bit <(1<<N); ++bit) {
    vector<int> S;
    for(int i=0; i<N; ++i) {
      if(bit & (1<<i)) {
        S.push_back(i);
      }
    }
    vector<int> tmp(M, 0);
    int c_tmp = 0;
    for(int i:S) {
      c_tmp += C[i];
      rep(m,M) { tmp[m] += A[i][m]; }
    }
    bool b = true;
    for(auto t:tmp) {
      if(t < X) b = false;
    }
    if(b) {
      if(ans == -1) ans = c_tmp;
      else ans = min(c_tmp, ans);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int INF = 1000000;
int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++){
    cin >> P[i];
  }
  int M = INF;
  int count = 0;
  for (int i = 0; i < N; i++){
    if (P[i] < M){
      M = P[i];
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 1152
N=1001
A=[[]]*N
x=1.0
y=0.0
for i in range(1,N):
    A[i]=[x,y]
    tmp=i**.5
    x,y=x-y/tmp,y+x/tmp
 
while 1:
    n = input()
    if n==-1:break
    a,b=A[n]
    print a,b

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string S;
            string T;

            string input = Console.ReadLine();
            string input2 = Console.ReadLine();
            string U = Console.ReadLine();

            S = input.Split(' ')[0];
            T = input.Split(' ')[1];

            int A;
            int B;

            A = int.Parse(input2.Split(' ')[0]);
            B = int.Parse(input2.Split(' ')[1]);

            if(S == U)
            {
                A--;
            }

            if(T == U)
            {
                B--;
            }

            Console.WriteLine("{0} {1}", A, B);

        }
    }
}


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

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template <typename Head> void dump(Head &&head) {
  cerr << head;
  dump();
}
template <typename Head, typename... Tail>
void dump(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  dump(forward<Tail>(tail)...);
}
#define debug(...)                                                             \
  do {                                                                         \
    cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = ";                        \
    dump(__VA_ARGS__);                                                         \
  } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template <typename T> struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T> using Edges = vector<edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T> using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////

const ll inf = 1LL << 60;
const string yes = "Yes";
const string no = "No";

int main() {
  ll d; cin >> d;
  ll t; cin >> t;
  ll s; cin >> s;
  if (d <= t*s) cout << yes << endl;
  else cout << no << endl;

  return 0;
}


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

int main()
{
	string s;
	int k;
	cin>>k>>s;
	if(k>=s.size())
	{
		cout<<s<<endl;
	}
	else
	{
		for(size_t i = 0; i<k; i++)
		{
			cout<<s[i];
		}
		cout<<"..."<<endl;
	}
	return 0;
}

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

int main() {
    int n; cin >> n;
    vector<long long> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) a[i+1] += a[i];
    vector< vector<long long> > dp(n+1, vector<long long>(n+1, 0));
    for (int k = 2; k <= n; k++) {
        for (int i = 0; i < n; i++) {
            if (i+k > n) continue;
            long long tmp = 1e18;
            for (int j = 1; j < k; j++) {
                tmp = min(dp[i][i+j]+dp[i+j][i+k], tmp);
            }
            dp[i][i+k] = tmp + (a[i+k]-a[i]);
        }
    }
    cout << dp[0][n] << endl;
    return 0;
}

Measured memory_bytes: 1536
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	int N, M, X;
	cin >> N >> M >> X;
	int sum = 0;
	int A;
	rep(i, 0, M)
	{
		cin >> A;
		if (A < X)
		{
			sum++;
		}
	}

	cout << min(sum, M - sum) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i, n) for (ll i=0;i<(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
//using ll=long long;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;

const long double PI=3.14159265358979323846;

ll h,w;
ll ans;
//vector<char> masu;

template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}


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

  vector<ll> p(a);
  vector<ll> q(b);
  vector<ll> r;
  
  rep(i, a){
    cin>>p[i];
  }
  rep(i, b){
    cin>>q[i];
  }
  ll tmp;
  rep(i, c){
    cin>>tmp;
    r.push_back(tmp);
  }
  sort(ALL(p));
  sort(ALL(q));
  sort(ALL(r));
  reverse(ALL(p));
  reverse(ALL(q));
  //reverse(ALL(r));

  rep(i, x){
    r.push_back(p[i]);
  }
  rep(i, y){
    r.push_back(q[i]);
  }

  sort(ALL(r));
  reverse(ALL(r));

  ll ans = accumulate(r.begin(), r.begin()+x+y, 0LL); 
  
  cout<< ans <<endl;
}


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

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define len(s) s.length()
#define forp(i,a,b) for( i=a;i<=b;i++)
#define FOR(tt,a,b) for(int tt=a;tt<=b;tt++)
#define rep(i,n)    for( i=0;i<n;i++)
#define ren(i,n)    for( i=n-1;i>=0;i--)
#define forn(i,a,b) for( i=a;i>=b;i--)
#define all(v) v.begin(),v.end()
#define b(v) v.begin()
#define e(v) v.end()
#define mem(n,m) memset(n,m,sizeof(n))
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vii vector<int>
#define vll vector<long long>
#define gl(cin,s)  getline(cin,s);
#define bitc(n) __builtin_popcountll(n)
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 

#define boost ios_base::sync_with_stdio(0)
#define MOD 1000000007
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define SIZE 100001

typedef long long  ll;
typedef unsigned long long ull;
typedef long double  ldo;
typedef double  db ;
using namespace std;
int main()
{  	
	/* #ifndef ONLINE_JUDGE
	freopen(fi, "r", stdin);
	#endif */
	//freopen("route.in","r",stdin);
	//freopen("route.out","w",stdout);
	//cin.ignore();
	//cin.clear();
	boost;
	//cin.tie(0);
	//cout<<"Case #"<<tt<<": ";
	ll a,b,x;
	cin>>a>>b>>x;
	ll temp = b/x;
	ll temp2 = a/x;
	if(a%x==0)
	temp2--;
	cout<<temp-temp2<<endl;
	return 0;
}

Measured memory_bytes: 256
def solve():
    N,W = map(int,input().split())
    weight = []
    value = []
    for i in range(N):
        w, v = map(int,input().split())
        weight.append(w)
        value.append(v)
    
    dp = [[0] * (W+1) for i in range(N+1)]

    for i in range(1,N+1):
        for w in range(W+1):
            if w - weight[i-1] < 0:
                dp[i][w] = max(dp[i][w], dp[i-1][w])
            else:
                dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i-1]] + value[i-1])
                dp[i][w] = max(dp[i][w], dp[i-1][w])
    
    print(max(dp[-1]))

if __name__ == '__main__':
    solve()

Measured memory_bytes: 118768
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(ALL(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;
vector<int> g[N];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a].PB(b);
        g[b].PB(a);
    }
    for(auto &v : g[1]){
        for(auto &x: g[v]){
            if(x == n){
                cout << "POSSIBLE";
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

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


#define long long long int

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef pair<int, int> pi;


int main() {


    int n;
    cin >> n;
    int count = 0;
    for (int i = 1; i <= n / 2; ++i) {
        if (i != n - i) {
            count++;
        }
    }
    cout << count;
    return 0;
}

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

class UnionFind {
  // まとめる 判定 サイズを知る
 public:
  // Aから見た親の番号を格納する。rootだったら-1*その集合のサイズ。
  vector<int> Parent;

  // 初期化
  UnionFind(int N) {
    Parent = vector<int>(N, -1);
  }

  // Aのrootを調べる
  int root(int A) {
    if (Parent[A] < 0) return A;  // マイナスならそれはroot
    return Parent[A] = root(Parent[A]);
  }

  // rootの値をプラスに戻して返す(サイズ)
  int size(int A) {
    return -Parent[root(A)];
  }

  // くっつける関数
  bool connect(int A, int B) {
    // AとBのroot同士をくっつける
    A = root(A);  // ここのAは、"rootの場所"の意味
    B = root(B);
    if (A == B) return false;  // 既にくっついている
    if (size(A) < size(B))
      swap(A, B);              // 大きい方にくっつけるために中身交換
    Parent[A] += Parent[B];  // 中身更新
    Parent[B] = A;
    return true;
  }
};

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

  vector<ll> a(m), b(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }

  UnionFind Island(n);
  vector<ll> ans(m);
  ans[m - 1] = (ll)n * (n - 1) / 2;

  // 何もない状態からつなげていったとき、不便度は双方に繋がってる島の積の数分減る
  for (int i = m - 1; i >= 1; i--) {
    if (Island.root(a[i]) != Island.root(b[i])) {
      ans[i - 1] = ans[i] - (ll)Island.size(a[i]) * Island.size(b[i]);
    } else {
      ans[i - 1] = ans[i];
    }
    Island.connect(a[i], b[i]);
  }

  for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, w;
	cin >> h >> w;
	vector<string> s(h);
	rep(i, h) cin >> s[i];
	vector<vector<int>> H_(h, vector<int>(w));
	vector<vector<int>> W_(h, vector<int>(w));
	rep(j, w) {
		int cnt = 0;
		rep(i, h) {
			if (s[i][j] == '.') cnt++;
			if (s[i][j] == '#') {
				if (i != 0) H_[i - 1][j] = cnt;
				cnt = 0;
			}
			if (i == h - 1) {
				if (s[i][j] != '#') H_[i][j] = cnt;
			}
		}
		int now = -1;
		for (int i = h - 1; i >= 0; --i) {
			if (now == -1 && s[i][j] != '#') now = H_[i][j];
			else {
				if (s[i][j] == '.') {
					H_[i][j] = now;
				}
				else {
					now = -1;
				}
			}
		}
	}
	rep(i, h) {
		int cnt = 0;
		rep(j, w) {
			if (s[i][j] == '.') cnt++;
			if (s[i][j] == '#') {
				if (j != 0) W_[i][j - 1] = cnt;
				cnt = 0;
			}
			if (j == w - 1) {
				if (s[i][j] != '#') W_[i][j] = cnt;
			}
		}
		int now = -1;
		for (int j = w - 1; j >= 0; --j) {
			if (now == -1 && s[i][j] != '#') now = W_[i][j];
			else {
				if (s[i][j] == '.') {
					W_[i][j] = now;
				}
				else {
					now = -1;
				}
			}
		}
	}
	/*rep(i, h) {
		rep(j, w) cout << H_[i][j] << ' ';
		cout << endl;
	}
	cout << endl;
	rep(i, h) {
		rep(j, w) cout << W_[i][j] << ' ';
		cout << endl;
	}*/
	int ans = 0;
	rep(i, h)rep(j, w) maxs(ans, W_[i][j] + H_[i][j] - 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 38796
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;

void YES(bool ok){
    cout << (ok ? "Yes" : "No") << endl;
}
int main(){
    ll n,m; cin >> n >> m;
    vector<ll> a(n);
    ll sum = 0;
    rep(i,n) {
        cin >> a[i];
        sum += a[i];
    }
    sort(all(a), greater<ll>());
    bool ok = true;
    rep(i,m){
        if(a[i] * 4 * m < sum)ok = false;
    }

    YES(ok);
}

Measured memory_bytes: 256
import sys
import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b = map(int, input().split())
s = input().split("-")

if len(s) == 2 and len(s[0]) == a and len(s[1]) == b:
    print('Yes')
    sys.exit()
else: print('No')

Measured memory_bytes: 9336
def d_widespread(N, A, B, H):
    from math import ceil
    lower_limit = 0
    upper_limit = max(H) // B + 1  # 多くともこの回数だけ魔法を使えば全滅できる

    def can_defeat(t):
        # t回で魔物を全滅させられるか
        # Bt以下の体力の魔物は魔法の巻き添えで倒す(直接狙う必要がない)
        time_defeat_all = sum([ceil((h - B * t) / (A - B)) for h in H if h > B * t])
        return time_defeat_all <= t

    while upper_limit - lower_limit > 1:
        mid = (lower_limit + upper_limit) // 2
        if can_defeat(mid):
            upper_limit = mid
        else:
            lower_limit = mid
    return upper_limit

N, A, B = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(d_widespread(N, A, B, H))

Measured memory_bytes: 11060
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	int d=0;
	for(int i=a;i>=1;i--){
		if(a%i==0&&b%i==0){
			c--;
			if(c==0){
				cout<<i<<endl;
				return 0;
			}
		}
	}
}


Measured memory_bytes: 256
import java.util.Scanner

object Main {

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    var n = sc.nextInt
    while (n != 0) {
      val dict = (0 until n).map(_ => (sc.next, sc.next)).toMap
      (0 until sc.nextInt).foreach(_ => {
        val s = sc.next
        print(dict.getOrElse(s, s))
      })
      println()

      n = sc.nextInt
    }
    sc.close()
  }
}

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

using namespace std;

int N, CusPos;
vector<int> Square;

void show() {

	cout << Square[0];
	for (int i = 1; i < CusPos; ++i) {
		cout << " " << Square[i];
	}
	cout << endl;
}

void solve(int curSum, int n) {

	if (curSum == N) {
		show();
		return;
	}
	for (int i = n; i > 0; --i) {
		if (curSum + i <= N) {
			Square[CusPos++] = i;
			solve(curSum + i, i);
			--CusPos;
		}
	}
}

int main() {

	while (cin >> N, N) {
		Square.resize(N);
		fill(Square.begin(), Square.end(), 0);
		CusPos = 0;
		solve(0, N);
	}
	
	return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MOD=1e9+7;
void solve()
{
	char c;
	cin>>c;
	if(islower(c)) cout<<"a\n";
	else cout<<"A\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3604
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][] a= new int[10][10];
  
   for(int i=1; i<=n; i++){
    String i1= String.valueOf(i);
    a[Integer.parseInt(i1.substring(0,1))][i%10]+=1;
   }
  
  int ans=0;
  
  for(int c=1; c<=9; c++){
   for(int d=1; d<=9; d++){
    ans+=a[c][d]*a[d][c];
   }
  }
    
    
    
    System.out.println(ans);
   
    }
}


Measured memory_bytes: 39444
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

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

    int H, W;
    cin >> H >> W;
    int c[10][10];
    for(int i=0; i<10; i++)
        for(int j=0; j<10; j++)
            cin >> c[i][j];

    for(int k=0; k<10; k++)
        for(int i=0; i<10; i++)
            for(int j=0; j<10; j++)
                c[i][j] = min(c[i][j], c[i][k]+c[k][j]);

    vector<vector<int>> A(H, vector<int>(W, 0));
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            cin >> A[i][j];

    int ans = 0;
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            if(A[i][j] != -1)
                ans += c[A[i][j]][1];
    cout << ans << endl;
    return 0;
}

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

int main(){
  int h1,h2,m1,m2,t, k,ans;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  ans = (h2 - h1) * 60 + (m2 - m1) - k;
  cout << ans;
}

Measured memory_bytes: 3632
#include <cstdio>

using namespace std;

const int MAX_N = 100;
int N;
int A[MAX_N];

void insertionSort(int *a, int n);

void show(int *a, int n) {
	for (int i = 0; i < n; i++) {
		printf("%d", *(a + i));
		if (i != n - 1) printf(" ");
	}
	printf("\n");
}

void solve() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", A + i);
	}
	insertionSort(A, N);
}

int main() {
	solve();
}

void insertionSort(int *a, int n) {
	int v;

	show(a, N);

	for (int i = 1; i <= n - 1; i++) {
		v = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			j--;
			a[j + 1] = v;
		}
		show(a, N);
	}
}

Measured memory_bytes: 2680
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
        }
        int min = 0;
        int mid = 0;
        int max = 0;

        for (int i = 0; i < n; i++) {
            if (p[i] <= a) {
                min++;
            } else if (p[i] <= b) {
                mid++;
            } else {
                max++;
            }
        }

        int ans = min;

        if (mid < ans) {
            ans = mid;
        }
        if (max < ans) {
            ans = max;
        }

        System.out.println(ans);
    }

}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a,a+n);
  
  int ans=0;
  if(n==2){
      cout<<a[1]-a[0]<<endl;
      cout<<a[1]<<" "<<a[0]<<endl;
  }
  else{
  if(a[0]<=0&&a[n-1]>=0){
    for(int i=0;i<n;i++) ans+=abs(a[i]); 
    cout<<ans<<endl;
    
    for(int i=1;i<n;i++){
      if(i!=n-1){
      if(a[i]>0){
        cout<<a[0]<<" "<<a[i]<<endl;
        a[0]-=a[i];
      }
      else{
        cout<<a[n-1]<<" "<<a[i]<<endl;
        a[n-1]-=a[i];
      }
      }
      else{
        cout<<a[n-1]<<" "<<a[0]<<endl;
      }
    }
    
  }
  else if(a[0]>0){
    for(int i=1;i<n;i++) ans+=a[i];
    cout<<ans-a[0]<<endl;
    
    cout<<a[0]<<" "<<a[n-1]<<endl;
    a[0]-=a[n-1];
    for(int i=1;i<n-2;i++){
      cout<<a[0]<<" "<<a[i]<<endl;
      a[0]-=a[i];
    }
    cout<<a[n-2]<<" "<<a[0]<<endl;
    
  }
  else{
    reverse(a,a+n);
    for(int i=1;i<n;i++) ans-=a[i];
    cout<<ans+a[0]<<endl;
    
    cout<<a[0]<<" "<<a[n-1]<<endl;
    a[0]-=a[n-1];
    for(int i=1;i<n-1;i++){
      cout<<a[0]<<" "<<a[i]<<endl;
      a[0]-=a[i];
    }
    
  }
  }
}


Measured memory_bytes: 2304
ab=[]
ba=[]
fullpath=[]
for i in range(3):
    ab.append(list(map(int,input().split())))
for i in range(3):
    ba.append(list(reversed(ab[i])))
fullpath=ab+ba
fullpath1=[]
for i in range(len(fullpath)):
    fullpath1.append(fullpath[i][0])
count=[]
for i in range(1,5):
    count.append(fullpath1.count(i))
if count.count(1)==2 and count.count(2)==2:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 9072
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define MOD 1000000007
 
const int dx_4[]={1,0,-1,0}, dy_4[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

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

	int h, w, a[500][500];
	vector<int> x, y, xx, yy;
	int n = 0;

	cin >> h >> w;
	REP(i, h){
		REP(j, w) cin >> a[i][j];
	}

	REP(i, h){
		REP(j, w-1){
			if(a[i][j] % 2 == 1){
				a[i][j]--;
				a[i][j+1]++;
				n++;
				x.pb(i+1);	y.pb(j+1);	xx.pb(i+1);	yy.pb(j+2);
			}
		}
	}

	REP(i, h-1){
		if(a[i][w-1] % 2 == 1){
			a[i][w-1]--;
			a[i+1][w-1]++;
			n++;
			x.pb(i+1);	y.pb(w);	xx.pb(i+2);	yy.pb(w);
		}
	}

	cout << n << endl;
	REP(i, n){
		cout << x[i] << " " << y[i] << " " << xx[i] << " " << yy[i] << endl;
	}
	rtn 0;
}

Measured memory_bytes: 5220
#include<stdio.h>
int main()
{
	int n,k,d,a,i,j,cnt,flg[101]={0};
	scanf("%d %d",&n,&k);
	for(i=0;i<k;i++){
		scanf("%d",&d);
		for(j=0;j<d;j++){
			scanf("%d",&a);
			flg[a]=1;
		}
	}
	for(i=1;i<=n;i++){
		if(flg[i]==0){
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 1704
N,M,Q=map(int,input().split())
R=[list(map(int,input().split())) for i in range(Q)]
S=[1]*N#1がNこ入った配列　
 
def dfs(d):
    if d==N-1:
        t=0
        for a,b,c,d in R:
            if S[b-1]-S[a-1]==c:
                t+=d
        return t
    else:
        m=0
        for i in range(S[d],M+1):
            S[d+1]=i
            m=max(m,dfs(d+1))
        return m

print(dfs(0))

Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

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

Measured memory_bytes: 3592
#!python3

import math


def LI():
    return list(map(int, input().split()))

# input
A, B, H, M = LI()


def main():
    t = abs((30 * H + 0.5 * M) - 6 * M)
    if t > 180:
        t = 360 - t
    t = math.radians(t)
    x2 = (A ** 2 + B ** 2) - (2 * A * B * math.cos(t))
    ans = x2 ** 0.5
    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

#define EPS 1e-10
#define equal(a,b) (fabs(a-b) < EPS)
#define lt(a,b) (a-b < -EPS)

struct Point{
  double x,y;

  Point(){}
  Point(double x,double y) : x(x),y(y) {}

  Point operator + (const Point &p)const{ return Point(x+p.x,y+p.y); }
  Point operator - (const Point &p)const{ return Point(x-p.x,y-p.y); }
  Point operator * (const double &k)const{ return Point(x*k,y*k); }
  Point operator / (const double &k)const{ return Point(x/k,y/k); }
  bool operator < (const Point &p)const{ return x != p.x ? x < p.x : y < p.y; }
};

double dot(const Point &a,const Point &b){ return a.x*b.x+a.y*b.y; }
double cross(const Point &a,const Point &b){ return a.x*b.y - b.x*a.y; }
double norm(const Point &p){ return dot(p,p); }
double abs(const Point &p){ return sqrt(norm(p)); }

istream &operator >> (istream &is,Point &p){ 
  return is >> p.x >> p.y;
}

typedef Point Vector;

struct Line{
  Point s,t;
  Line(){}
  Line(Point s,Point t) : s(s),t(t) {}
};

bool isIntersectLL(const Line &a,const Line &b){
  return abs(cross(a.t-a.s,b.t-b.s)) > EPS
    || abs(cross(a.t-a.s,b.t-b.s)) < EPS;
}

Point crosspointLL(const Line &a,const Line &b){
  Vector va = a.t-a.s, vb = b.t-b.s;
  double d = cross(vb,va);
  return a.s+va*cross(vb,b.t-a.s)*(1.0/d);
}

int main(){
  int N;
  while(cin >> N,N){
    vector<Line> l(N);
    for(int i = 0 ; i < N ; i++){
      cin >> l[i].s >> l[i].t;
    }
    int div = 1;
    for(int i = 0 ; i < N ; i++){
      int cp = 0;
      vector<Point> used;
      for(int j = 0 ; j < i ; j++){
        if(isIntersectLL(l[i],l[j])){
          Point p = crosspointLL(l[i],l[j]);
          bool f = false;
          for(int k = 0 ; k < (int)used.size() ; k++){
            Point q = used[k];
            if(equal(p.x,q.x) && equal(p.y,q.y)){
              f = true;
              break;
            }
          }
          if(f){ continue; }
          used.push_back(p);
          if(lt(-100,p.x) && lt(p.x,100) &&
             lt(-100,p.y) && lt(p.y,100)){
            cp++;
          }
        }
      }
      div += cp+1;
    }
    cout << div << endl;
  }
  return 0;
}

Measured memory_bytes: 1240
import Data.Char

solve :: String -> String -> Int
solve w t = count w $ words t

count :: (Eq a) => a -> [a] -> Int
count needle list = foldl (\acc x -> if x == needle then acc + 1 else acc) 0 list

main = do
	w <- fmap (map toLower) getLine
	t <- fmap (map toLower) getContents
	putStrLn $ show $ solve w t

Measured memory_bytes: 3692
# D - Lunlun Number

K = int(input())
stack = [1, 2, 3, 4, 5, 6, 7, 8, 9]
i = 0
while len(stack) < K:
    first = int(str(stack[i])[-1:])
    if first == 0:
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))
    elif first == 9:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
    else:
        stack.append(int(str(stack[i]) + str(first - 1)))
        stack.append(int(str(stack[i]) + str(first)))
        stack.append(int(str(stack[i]) + str(first + 1)))        
    i += 1

print(stack[K - 1])

Measured memory_bytes: 7004
#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,m;
char str[111];
L a[33];

int main()
{
	scanf("%lld %lld",&n,&m);
	L i,j;
	for(i=0;i<n;i++)
	{
		scanf("%s",str);
		for(j=0;j<m;j++)
		{
			a[str[j]-'a']++;
		}
	}
		L cnt1=0,cnt2=0,cnt3=0;
		for(i=0;i<26;i++)
		{
			if(a[i]%4==1) cnt1++;
			if(a[i]%4==2) cnt2++;
			if(a[i]%4==3) cnt3++;
		}
	if(n%2==0&&m%2==0)
	{
		if(cnt1||cnt2||cnt3) puts("No");
		else puts("Yes");
	}
	else if(n%2==0)
	{
		if(cnt2<=n/2&&!cnt1&&!cnt3) puts("Yes");
		else puts("No");
	}
	else if(m%2==0)
	{
		if(cnt2<=m/2&&!cnt1&&!cnt3) puts("Yes");
		else puts("No");
	}
	else
	{
			cnt2+=cnt3;
			cnt1+=cnt3;
		if(cnt1==1&&cnt2<=(n+m-2)/2) puts("Yes");
		else puts("No");
	}
}

Measured memory_bytes: 256
#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);
    
    int a, b; cin >> a >> b;
    int ans = 0;
    
    rep(i,100){
        if(1+i*(a-1) >= b){
            cout << i << ln;
            return 0;
        }
    }
    
    return 0;
 }

Measured memory_bytes: 256
s = input()
n = len(s)
s += 'E'
count = [0]*n
a = 1
for i in range(n):
  if s[i] == s[i+1]:
    a += 1
  else:
    if s[i] == 'R':
      count[i] += a-a//2
      count[i+1] += a//2
    else:
      count[i+1-a] += a-a//2
      count[i-a] += a//2
    a=1  
print(' '.join(map(str, count)))

Measured memory_bytes: 10484
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<list>
using namespace std;

typedef long long ll;

#define MOD 1000000007

class Comb{
public:
  ll *fac,*finv,*inv;
//public:
  Comb(){
    fac = new ll[1000000];
    finv = new ll[1000000];
    inv = new ll[1000000];
    fac[0] = 1;
    for(int i=1;i<1000000;i++){
      fac[i] = i*fac[i-1];
      fac[i] %= MOD;
    }
    inv[1] = 1;
    for(int i=2;i<1000000;i++){
      inv[i] = MOD-inv[MOD%i]*(MOD/i)%MOD;
    }
    finv[0] = 1;
    for(int i=1;i<1000000;i++){
      finv[i] = inv[i]*finv[i-1];
      finv[i] %= MOD;
    }
  }
  ll calc(ll n,ll k){
    ll c = fac[n];
    c *= finv[k];c %= MOD;
    c *= finv[n-k];c %= MOD;
    return c;
  }
};

ll gcd(ll x,ll y){
  if(x%y == 0) return y;
  else return gcd(y,x%y);
}

ll dfs(ll n){
  if(n == 1) return 2;
  ll k = n/2;
  ll temp = dfs(k);
  ll ans = temp;
  ans *= temp;
  ans %= MOD;
  if(n%2 != 0) ans *= 2;
  return ans%MOD;
}
int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll ans = dfs(n);
  ll temp = 1;
  Comb comb;
  for(ll i=0;i<a;i++){
    temp *= n-i;
    temp %= MOD;
  }
  temp *= comb.finv[a];
  temp %= MOD;
  ans -= temp;
  temp = 1;
  for(ll i=0;i<b;i++){
    temp *= n-i;
    temp %= MOD;
  }
  temp *= comb.finv[b];
  temp %= MOD;
  ans -= temp;
  ans %= MOD;
  ans -= 1;
  ans %= MOD;
  ans += 2*MOD;
  ans %= MOD;
  cout << ans << endl;
  
}


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

#define inf 0x3f3f3f3f
#define endl '\n'
typedef long long ll;

int n;
ll peso;
ll dp[102][100005], w[100005], v[100005];

ll f(int i, ll p){
  //cout << i << " "  << p << endl;
  if(i==0 || p<=0) return 0;
  if(w[i]>p) return dp[i][p]=f(i-1, p);
  if(dp[i][p]!=-1) return dp[i][p];
  return dp[i][p]=max(f(i-1, p), f(i-1, p-w[i]) + v[i]);
}
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> peso;
  for(int i=1; i<=n; i++) cin >> w[i] >> v[i];
  for(int i=1; i<=100; i++){
    for(int j=1; j<=100000; j++){
      dp[i][j]=-1;
    }
  }
  cout << f(n, peso) << endl;
}

Measured memory_bytes: 78720
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int m, k;
    cin >> m >> k;
    if (k >= (1 << m))
    {
        cout << "-1\n";
        return 0;
    }

    vs32 cand;
    if (k == 1)
    {
        if (m == 1)
        {
            cout << "-1\n";
            return 0;
        }
        cand.push_back(2);
        cand.push_back(3);
    }
    else
    {
        int temp = k;
        int cnt = 0;
        while (temp)
        {
            if (temp & 1)
            {
                if (k == (1 << cnt))
                {
                    cand.push_back((1 << cnt) + (1 << (cnt - 1)));
                    cand.push_back(1 << (cnt - 1));
                    break;
                }
                else
                {
                    cand.push_back(1 << cnt);
                }
            }
            ++cnt;
            temp >>= 1;
        }
    }

    vs32 ans(1 << (m + 1));
    vs32 cand2;
    rep (i, 1 << m)
    {
        bool flag = true;
        rep (j, cand.size()) if (i == cand[j] || i == k) flag = false;
        if (flag) cand2.push_back(i);
    }

    int idx = 0;
    for (auto it = cand2.rbegin(); it < cand2.rend(); ++it)
    {
        ans[idx++] = *it;
    }
    for (auto it = cand.rbegin(); it < cand.rend(); ++it)
    {
        ans[idx++] = *it;
    }
    for (auto it = cand2.begin(); it < cand2.end(); ++it)
    {
        ans[idx++] = *it;
    }
    ans[idx++] = k;
    for (auto it = cand.begin(); it < cand.end(); ++it)
    {
        ans[idx++] = *it;
    }
    ans[idx++] = k;

    rep (i, ans.size())
    {
        if (i > 0) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
    return 0;
}



Measured memory_bytes: 3448
#include<iostream>
#include<cstdio>
#include<cstring>
template<typename T>inline void check_min(T a,T &b){if(a<b)b=a;}
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace bf
{
	typedef long long ll;
	const int N=100010;
	const ll INF=214748364700000ll;
	struct Increasing_queue
	{
		ll dl[N];
		int pos[N];
		int head,tail;
		void init(){head=0,tail=1;}
		void insert(ll x,int p)
		{
			while(head>=tail && dl[head]>=x)head--;
			dl[++head]=x;
			pos[head]=p;
		}
		void del(int p)
		{
			while(head>=tail && pos[tail]<=p)tail++;
		}
		ll query(){return head>=tail?dl[tail]:INF;}
	}d;
	int a[N],b[N];
	ll f[N],tmp;
	int n,m;
	void initialize()
	{
		read(n),read(a[n]),read(m);
		for(int i=0;i<n;i++)
			read(a[i]);
		for(int i=1;i<=n;i++)
			b[i]=a[i]-a[i-1];
	}
	inline ll get_dis(int i,int j){return a[j]-b[j]-a[i];}
//	inline ll calc(int i,int j)
//	{
//		ll dis=get_dis(i,j),ret=dis*3+b[j];
//		ret+=std::max(0ll,m-dis*2);
//		return ret;
//	}
	void solve()
	{
		initialize();

		d.init(),tmp=INF;
		f[0]=a[0],d.insert(f[0]-a[0],0);
		int ind=0;

		for(int i=1;i<=n;i++)
		{
			for(;ind<i && get_dis(ind,i)*2>m;ind++)
				d.del(ind),check_min(f[ind]-3ll*a[ind],tmp);

			f[i]=d.query()+a[i]+m;
			check_min(tmp+3ll*a[i]-2ll*b[i],f[i]);

			d.insert(f[i]-a[i],i);
		}
		printf("%lld\n",f[n]);
	}
}
int main()
{
	bf::solve();
	return 0;
}


Measured memory_bytes: 3072
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



N,K = map(int, sys.stdin.readline().rstrip().split())
An = list(map(int, sys.stdin.readline().rstrip().split()))

amap = {}
for a in An:
  if a not in amap:
    amap[a] = 1
  else:
    amap[a] += 1

nl = []
for i in list(amap.values()):
  nl.append(i)
nl = sorted(nl)

print(sum(nl[:-K]))

Measured memory_bytes: 98508
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

ll dp[100001];
ll mod = 1e9 + 7;
int v[100001];
int N, K;
vector<int> E[100001];
ll kotae;

void dfs(int A, int B, int C) {
	if (v[A]) return;
	v[A] = 1;
	int k = K - C - B - 1;
	if (C == -1) k = K;
	if (k < 0) k = 0;
	kotae = kotae * k % mod;
	int b = 0;
	for (int p : E[A]) {
		if (v[p] == 0) {
			if (C == -1) dfs(p, b, 0);
			else dfs(p, b, 1);
			b++;
		}
	}

}

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


	cin >> N >> K;
	rep(i, N - 1) {
		int a, b;
		cin >> a >> b;
		E[a].pb(b);
		E[b].pb(a);
	}
	kotae = 1;
	dfs(1, 0, -1);
	co(kotae);


	Would you please return 0;
}

Measured memory_bytes: 9600